A categorical characterization of strong Steiner ω-categories

Strong Steiner ω-categories are a class of ω-categories that admit algebraic models in the form of chain complexes, whose formalism allows for several explicit computations. The conditions defining strong Steiner ω-categories are traditionally expressed in terms of the associated chain complex, making them somewhat disconnected from the ω-categorical intuition. The purpose of this paper is to characterize this class as the class of ω-categories generated by polygraphs that satisfy a loop-freeness condition that does not make explicit use of the associated chain complex and instead relies on the categorical features of ω-categories.     

Obstructions to shellability, partitionability, and sequential Cohen-Macaulayness

For a property P of simplicial complexes, a simplicial complex Γ is an obstruction to P if Γ itself does not satisfy P but all of its proper restrictions satisfy P. In this paper, we determine all obstructions to shellability of dimension ?2, refining the previous work by Wachs. As a consequence we obtain that the set of obstructions to shellability, that to partitionability and that to sequential Cohen-Macaulayness all coincide for dimensions ?2. We also show that these three sets of obstructions coincide in the class of flag complexes. These results show that the three properties, hereditary-shellability, hereditary-partitionability, and hereditary-sequential Cohen-Macaulayness are equivalent for these classes.     

Some remarks on projective generators and injective cogenerators

In this paper,we give a relationship between projective generators(resp.,injective cogenerators) in the category of R-modules and the counterparts in the category of complexes of R-modules.As a consequence,we get that complexes of W-Gorenstein modules are actually W-Gorenstein complexes whenever W is a subcategory of R-modules satisfying W⊥W,where W is the subcategory of exact complexes with all cycles in W.We also study when all cycles of a W-Gorenstein complexes are W-Gorenstein modules.     

Tchebyshev triangulations of stable simplicial complexes

We generalize the notion of the Tchebyshev transform of a graded poset to a triangulation of an arbitrary simplicial complex in such a way that, at the level of the associated F-polynomials j_∑fj−1(j(x−1)/2), the triangulation induces taking the Tchebyshev transform of the first kind. We also present a related multiset of simplicial complexes whose association induces taking the Tchebyshev transform of the second kind. Using the reverse implication of a theorem by Schelin we observe that the Tchebyshev transforms of Schur stable polynomials with real coefficients have interlaced real roots in the interval (−1,1), and present ways to construct simplicial complexes with Schur stable F-polynomials. We show that the order complex of a Boolean algebra is Schur stable. Using and expanding the recently discovered relation between the derivative polynomials for tangent and secant and the Tchebyshev polynomials we prove that the roots of the corresponding pairs of derivative polynomials are all pure imaginary, of modulus at most one, and interlaced.     

Approximate extension property of mappings

The extension problem is to determine the extendability of a mapping defined on a closed subset of a space into a nice space such as a CW complex over the whole space. In this paper, we consider the extension problem when the codomains are general spaces. We take a shape theoretic approach to generalize the extension theory so that the codomains are allowed to be general spaces. We extend the notion of extension type which has been defined for the class of CW complexes and introduce the notion of approximate extension type which is defined for general spaces. We define approximate extension dimension analogously to extension dimension, replacing the class of CW complexes by the class of finitistic separable metrizable spaces. For every metrizable space X, we show the existence of approximate extension dimension of X.     

Chain homotopies for object topological representations

This paper presents a set of tools to compute topological information of simplicial complexes, tools that are applicable to extract topological information from digital pictures. A simplicial complex is encoded in a (non-unique) algebraic-topological format called AM-model. An AM-model for a given object K is determined by a concrete chain homotopy and it provides, in particular, integer (co)homology generators of K and representative (co)cycles of these generators. An algorithm for computing an AM-model and the cohomological invariant HB1 (derived from the rank of the cohomology ring) with integer coefficients for a finite simplicial complex in any dimension is designed here, extending the work done in [R. González-Díaz, P. Real, On the cohomology of 3D digital images, Discrete Appl. Math. 147 (2005) 245-263] in which the ground ring was a field. The concept of generators which are “nicely” representative is also presented. Moreover, we extend the definition of AM-models to 3D binary digital images and we design algorithms to update the AM-model information after voxel set operations (union, intersection, difference and inverse).     

On the divergence of polynomial interpolation

Consider a triangular interpolation scheme on a continuous piecewise C¹ curve of the complex plane, and let Γ be the closure of this triangular scheme. Given a meromorphic function f with no singularities on Γ, we are interested in the region of convergence of the sequence of interpolating polynomials to the function f. In particular, we focus on the case in which Γ is not fully contained in the interior of the region of convergence defined by the standard logarithmic potential. Let us call Γ_out the subset of Γ outside of the convergence region.In the paper we show that the sequence of interpolating polynomials, {P_n}_n, is divergent on all the points of Γ_out, except on a set of zero Lebesgue measure. Moreover, the structure of the set of divergence is also discussed: the subset of values z for which there exists a partial sequence of {P_n(z)}_n that converges to f(z) has zero Hausdorff dimension (so it also has zero Lebesgue measure), while the subset of values for which all the partials are divergent has full Lebesgue measure.The classical Runge example is also considered. In this case we show that, for all z in the part of the interval (−5,5) outside the region of convergence, the sequence {P_n(z)}_n is divergent.     

Subword complexes, cluster complexes, and generalized multi-associahedra

In this paper, we use subword complexes to provide a uniform approach to finite-type cluster complexes and multi-associahedra. We introduce, for any finite Coxeter group and any nonnegative integer k, a spherical subword complex called multi-cluster complex. For k=1, we show that this subword complex is isomorphic to the cluster complex of the given type. We show that multi-cluster complexes of types A and B coincide with known simplicial complexes, namely with the simplicial complexes of multi-triangulations and centrally symmetric multi-triangulations, respectively. Furthermore, we show that the multi-cluster complex is universal in the sense that every spherical subword complex can be realized as a link of a face of the multi-cluster complex.     

New parameters of subsets in polynomial association schemes

We define new parameters, a zero interval and a dual zero interval, of subsets in P- or Q-polynomial association schemes. A zero interval of a subset in a P-polynomial association scheme is a successive interval index for which the inner distribution vanishes, and a dual zero interval of a subset in a Q-polynomial association scheme is a successive interval index for which the dual inner distribution vanishes. We derive bounds of the lengths of a zero interval and a dual zero interval using the degree and dual degree respectively, and show that a subset in a P-polynomial association scheme (resp. a Q-polynomial association scheme) having a large length of a zero interval (resp. a dual zero interval) induces a completely regular code (resp. a Q-polynomial association scheme). Moreover, we consider the spherical analogue of a dual zero interval.     

Sixteen topological types in βω−ω

In this paper we describe sixteen topological types in βω?ω. Among others, we show that there is a weak P-point x ∈ βω?ω which is a limit point of some ccc subset of βω?ω?{x} and that there is a point y ∈ βω?ω which is a limit point of some countable subset of βω?ω?{y} but not of any countable discrete subset of βω?ω?{y}.     

Extended formulations for matroid polytopes through randomized protocols

The hitting number of a polytope P is the smallest size of a subset of vertices of P such that every facet of P has a vertex in the subset. We show that, if P is the base polytope of any matroid, then P admits an extended formulation of linear size on the hitting number of P. Our results generalize those of the spanning tree polytope given by Martin and Wong, and extend to polymatroids.     

Chain Blockers and Convoluted Catalan Numbers

We give new interpretations of Catalan and convoluted Catalan numbers in terms of trees and chain blockers. For a poset P we say that a subset A ? P is a chain blocker if it is an inclusionwise minimal subset of P that contains at least one element from every maximal chain. In particular, we study the set of chain blockers for the class of posets P = C _a × C _b where C _i is the chain 1 < ? < i. We show that subclasses of these chain blockers are counted by Catalan and convoluted Catalan numbers.     

Vietoris–Rips complexes also provide topologically correct reconstructions of sampled shapes

Given a point set that samples a shape, we formulate conditions under which the Rips complex of the point set at some scale reflects the homotopy type of the shape. For this, we associate with each compact set X of ${\mathbb{R}}^n$ two real-valued functions $c_X$ and $h_X$ defined on ${\mathbb{R}}_{+}$ which provide two measures of how much the set X fails to be convex at a given scale. First, we show that, when P is a finite point set, an upper bound on $c_P(t)$ entails that the Rips complex of P at scale r collapses to the ?ech complex of P at scale r for some suitable values of the parameters t and r. Second, we prove that, when P samples a compact set X, an upper bound on $h_X$ over some interval guarantees a topologically correct reconstruction of the shape X either with a ?ech complex of P or with a Rips complex of P. Regarding the reconstruction with ?ech complexes, our work compares well with previous approaches when X is a smooth set and surprisingly enough, even improves constants when X has a positive μ-reach. Most importantly, our work shows that Rips complexes can also be used to provide shape reconstructions having the correct homotopy type. This may be of some computational interest in high dimensions.     

Matroid representation of clique complexes

In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any k>0, we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be n-1. Other related investigations are also given.     

Overlaps help: Improved bounds for group testing with interval queries

Given a finite ordered set of items and an unknown distinguished subset P of up to p positive elements, identify the items in P by asking the least number of queries of the type ‘‘does the subset Q intersect P?”, where Q is a subset of consecutive elements of {1,2,…,n}. This problem arises, e.g., in computational biology, in a particular method for determining splice sites in genes. We consider time-efficient algorithms where queries are arranged in a fixed number s of stages: In each stage, queries are performed in parallel. In a recent bioinformatics paper, we proved optimality (subject to lower-order terms) with respect to the number of queries, of some strategies for the special cases p=1 or s=2. Exploiting new ideas, we are now able to provide improved lower bounds for any p?2 and s?3 and improved upper bounds for larger s. Most notably, our new bounds converge as s grows. Our new query scheme uses overlapping query intervals within a stage, which is effective for large enough s. This contrasts with our previous results for s?2 where optimal strategies were implemented by disjoint queries. The main open problem is whether overlaps help already in the case of small s?3. Anyway, the remaining gaps between the current upper and lower bounds for any fixed s?3 amount to small constant factors in the main term. The paper ends with a discussion of practical implications in the case that the positive elements are well separated.     

Reguläre Inzidenzkomplexe II

The concept of regular incidence complexes generalizes the notion of regular polyhedra in a combinatorial and grouptheoretical sense. A regular (incidence) complex K is a special type of partially ordered structure with regularity defined by the flag-transitivity of its group A(K) of automorphisms. The structure of a regular complex K can be characterized by certain sets of generators and ‘relations’ of its group. The barycentric subdivision of K leads to a simplicial complex, from which K can be rebuilt by fitting together faces. Moreover, we characterize the groups that act flag-transitively on regular complexes. Thus we have a correspondence between regular complexes on the one hand and certain groups on the other hand. Especially, this principle is used to give a geometric representation for an important class of regular complexes, the so-called regular incidence polytopes. There are certain universal incidence polytopes associated to Coxeter groups with linear diagram, from which each regular incidence polytope can be deduced by identifying faces. These incidence polytopes admit a geometric representation in the real space by convex cones.     

H.O. Foulkes (1907–1977)

Two general kinds of subsets of a partially ordered set P are always retracts of P: (1) every maximal chain of P is a retract; (2) in P, every isometric, spanning subset of length one with no crowns is a retract. It follows that in a partially ordered set P with the fixed point property, every maximal chain of P is complete and every isometric, spanning fence of P is finite.     

Integration of complex polynomial differential equations in higher dimension,a first step: Lie transverse structure

We prove that a one-dimensional holomorphic foliationswith generic singularities on a complex projective space ?P ^m+1, m ≥ 2, exhibiting a Lie group transverse structure in some Zariski open subset, is logarithmic. That is, it is given by a system of m closed rational one-forms with simple poles. The foliation is given by a linear vector field in some affine space ? ^m+1 ? ?P ^m+1 if, and only if, it exhibits only one singularity in this affine space. An application to foliations invariant under Lie group transverse actions is given.     

Random walks on simplicial complexes and harmonics

In this paper, we introduce a class of random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d, a random walk with an absorbing state is defined which relates to the spectrum of the k‐dimensional Laplacian for 1 ≤ k ≤ d. We study an example of random walks on simplicial complexes in the context of a semi‐supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 379–405, 2016