Linear colorings of simplicial complexes and collapsing

A vertex coloring of a simplicial complex Δ is called a linear coloring if it satisfies the property that for every pair of facets (F₁,F₂) of Δ, there exists no pair of vertices (v₁,v₂) with the same color such that v₁∈F₁?F₂ and v₂∈F₂?F₁. The linear chromatic numberlchr(Δ) of Δ is defined as the minimum integer k such that Δ has a linear coloring with k colors. We show that if Δ is a simplicial complex with lchr(Δ)=k, then it has a subcomplex Δ^′ with k vertices such that Δ is simple homotopy equivalent to Δ^′. As a corollary, we obtain that lchr(Δ)?Homdim(Δ)+2. We also show in the case of linearly colored simplicial complexes, the usual assignment of a simplicial complex to a multicomplex has an inverse. Finally, we show that the chromatic number of a simple graph is bounded from above by the linear chromatic number of its neighborhood complex.     

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.     

Decompositions of two-dimensional simplicial complexes

We show that the class of Cohen-Macaulay complexes, that of complexes with constructible subdivisions, and that of complexes with shellable subdivisions differ from each other in every dimension d?2. Further, we give a characterization of two-dimensional simplicial complexes with shellable subdivisions, and show also that they are constructible.     

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).     

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     

Simplicial collapsibility,discrete Morse theory,and the geometry of nonpositively curved simplicial complexes

Understanding the conditions under which a simplicial complex collapses is a central issue in many problems in topology and combinatorics. Let K be a finite simplicial complex of dimension three or less endowed with the piecewise Euclidean geometry given by declaring edges to have unit length, and satisfying the property that every 2-simplex is a face of at most two 3-simplices in K. Our main result is that if |K| is nonpositively curved [in the sense of CAT(0)] then K simplicially collapses to a point. The main tool used in the proof is Forman’s discrete Morse theory, a combinatorial analog of the classical smooth theory developed in the 1920s. A key ingredient in our proof is a combinatorial analog of the fact that a minimal surface in has nonpositive Gauss curvature.      

Intersections of Leray complexes and regularity of monomial ideals

For a simplicial complex X and a field K, let .It is shown that if X,Y are complexes on the same vertex set, then for k?0

     

On the reliability roots of simplicial complexes and matroids

Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ fail independently with probability $q\in [0,1]$. The all-terminal reliability of $G$ is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in $q$, and it was conjectured that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when the roots fall inside the closed unit disk. We show that such is the case for matroids of rank 3 and paving matroids of rank 4. We also prove that the reliability roots of shellable complexes are dense in the complex plane, and that the real reliability roots of any matroid lie in $[?1,0)\cup \left\{1\right\}$. Finally, we also show that the reliability roots of thickenings of the Fano matroid can lie outside the unit disk.     

On the vanishing of homology in random Čech complexes

We compute the homology of random ?ech complexes over a homogeneous Poisson process on the d‐dimensional torus, and show that there are, coarsely, two phase transitions. The first transition is analogous to the Erd?s ‐Rényi phase transition, where the ?ech complex becomes connected. The second transition is where all the other homology groups are computed correctly (almost simultaneously). Our calculations also suggest a finer measurement of scales, where there is a further refinement to this picture and separation between different homology groups. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 14–51, 2017     

Matchings in simplicial complexes, circuits and toric varieties

Using a generalized notion of matching in a simplicial complex and circuits of vector configurations, we compute lower bounds for the minimum number of generators, the binomial arithmetical rank and the A-homogeneous arithmetical rank of a lattice ideal. Prime lattice ideals are toric ideals, i.e. the defining ideals of toric varieties.     

An A ∞ structure on simplicial complexes

We consider a discrete (finite-difference) analogue of differential forms defined on simplicial complexes, in particular, on triangulations of smooth manifolds. Various operations are explicitly defined on these forms including the exterior differential d and the exterior product ∧. The exterior product is nonassociative but satisfies a more general relation, the so-called A _∞ structure. This structure includes an infinite set of operations constrained by the nilpotency relation (d + ∧ + m + …)ⁿ = 0 of the second degree, n = 2. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 156, No. 1, pp. 3–37, July, 2008.     

Stanley decompositions and partitionable simplicial complexes

We study Stanley decompositions and show that Stanley’s conjecture on Stanley decompositions implies his conjecture on partitionable Cohen–Macaulay simplicial complexes. We also prove these conjectures for all Cohen–Macaulay monomial ideals of codimension 2 and all Gorenstein monomial ideals of codimension 3. Dedicated to Takayuki Hibi on the occasion of his fiftieth birthday.     

单纯广群的准层和同伦纤维

显示了在设置C上的单纯广群的准层的范畴是个封闭模型范畴.证明了在一个单纯广群的准层G上的单纯函子X是局部弱等价于同伦纤维.     

Vanishing of cohomology groups of random simplicial complexes

We consider k‐dimensional random simplicial complexes generated from the binomial random (k + 1)‐uniform hypergraph by taking the downward‐closure. For 1 ≤ j ≤ k ? 1, we determine when all cohomology groups with coefficients in from dimension one up to j vanish and the zero‐th cohomology group is isomorphic to . This property is not deterministically monotone for this model, but nevertheless we show that it has a single sharp threshold. Moreover we prove a hitting time result, relating the vanishing of these cohomology groups to the disappearance of the last minimal obstruction. We also study the asymptotic distribution of the dimension of the j‐th cohomology group inside the critical window. As a corollary, we deduce a hitting time result for a different model of random simplicial complexes introduced by Linial and Meshulam, previously only known for dimension two.     

On Quillen?s Theorem A for posets

A theorem of McCord of 1966 and Quillen?s Theorem A of 1973 provide sufficient conditions for a map between two posets to be a homotopy equivalence at the level of complexes. We give an alternative elementary proof of this result and we deduce also a stronger statement: under the hypotheses of the theorem, the map is not only a homotopy equivalence but a simple homotopy equivalence. This leads then to stronger formulations of the simplicial version of Quillen?s Theorem A, the Nerve Lemma and other known results. In particular we establish a conjecture of Kozlov on the simple homotopy type of the crosscut complex and we improve a well-known result of Cohen on contractible mappings.     

Fundamental groupoids for simplicial objects in Mal'tsev categories

We show that the category of internal groupoids in an exact Mal'tsev category is reflective, and, moreover, a Birkhoff subcategory of the category of simplicial objects. We then characterize the central extensions of the corresponding Galois structure, and show that regular epimorphisms admit a relative monotone-light factorization system in the sense of Chikhladze. We also draw some comparison with Kan complexes. By comparing the reflections of simplicial objects and reflexive graphs into groupoids, we exhibit a connection with weighted commutators (as defined by Gran, Janelidze and Ursini).