On subdivisions of simplicial complexes: Characterizing localh-vectors

A well-known combinatorial invariant of simplicial complexes is theh-vector, which has been the subject of much combinatorial research. This paper deals withlocal h-vectors, recently defined by Stanley as a tool for studyingh-vectors of simplicial subdivisions. The face-vector of any simplicial complex can only increase when the complex is subdivided; how does theh-vector change? Motivated by this question, Stanley derived certain useful properties of localh-vectors. In this paper we use mainly geometric arguments to show that these properties characterize localh-vectors, andregular localh-vectors.     

Cubical Subdivisions and Local h-Vectors

Face numbers of triangulations of simplicial complexes were studied by Stanley by use of his concept of a local h-vector. It is shown that a parallel theory exists for cubical subdivisions of cubical complexes, in which the role of the h-vector of a simplicial complex is played by the (short or long) cubical h-vector of a cubical complex, defined by Adin, and the role of the local h-vector of a triangulation of a simplex is played by the (short or long) cubical local h-vector of a cubical subdivision of a cube. The cubical local h-vectors are defined in this paper and are shown to share many of the properties of their simplicial counterparts. Generalizations to subdivisions of locally Eulerian posets are also discussed.     

Pure O-Sequences and Matroid h-Vectors

We study Stanley’s long-standing conjecture that the h-vectors of matroid simplicial complexes are pure O-sequences. Our method consists of a new and more abstract approach, which shifts the focus from working on constructing suitable artinian level monomial ideals, as often done in the past, to the study of properties of pure O-sequences. We propose a conjecture on pure O-sequences and settle it in small socle degrees. This allows us to prove Stanley’s conjecture for all matroids of rank 3. At the end of the paper, using our method, we discuss a first possible approach to Stanley’s conjecture in full generality. Our technical work on pure O-sequences also uses very recent results of the third author and collaborators.     

On the Stanley ring of cubical complex

We investigate the properties of the Stanley ring of a cubical complex, a cubical analogue of the Stanley-Reisner ring of a simplicial complex. We compute its Hilbert series in terms of thef-vector, and prove that by taking the initial ideal of the defining relations, with respect to the reverse lexicographic order, we obtain the defining relations of the Stanley-Reisner ring of the triangulation via “pulling the vertices” of the cubical complex. Applying an old idea of Hochster we see that this ring is Cohen-Macaulay when the complex is shellable, and we show that its defining ideal is generated by quadrics when the complex is also a subcomplex of the boundary complex of a convex cubical polytope. We present a cubical analogue of balanced Cohen-Macaulay simplicial complexes: the class of edge-orientable shellable cubical complexes. Using Stanley's results about balanced Cohen-Macaulay simplicial complexes and the degree two homogeneous generating system of the defining ideal, we obtain an infinite set of examples for a conjecture of Eisenbud, Green, and Harris. This conjecture says that theh-vector of a polynomial ring inn variables modulo an ideal which has ann-element homogeneous system of parameters of degree two, is thef-vector of a simplicial complex.     

On <Emphasis Type="Italic">γ</Emphasis>-Vectors Satisfying the Kruskal–Katona Inequalities

We present examples of flag homology spheres whose γ-vectors satisfy the Kruskal–Katona inequalities. This includes several families of well-studied simplicial complexes, including Coxeter complexes and the simplicial complexes dual to the associahedron and to the cyclohedron. In these cases, we construct explicit flag simplicial complexes whose f-vectors are the γ-vectors in question, and so a result of Frohmader shows that the γ-vectors satisfy not only the Kruskal–Katona inequalities but also the stronger Frankl–Füredi–Kalai inequalities. In another direction, we show that if a flag (d−1)-sphere has at most 2d+3 vertices its γ-vector satisfies the Frankl–Füredi–Kalai inequalities. We conjecture that if Δ is a flag homology sphere then γ(Δ) satisfies the Kruskal–Katona, and further, the Frankl–Füredi–Kalai inequalities. This conjecture is a significant refinement of Gal’s conjecture, which asserts that such γ-vectors are nonnegative.     

<Emphasis Type="Italic">f</Emphasis>-vectors of simplicial posets that are balls

Results of R. Stanley and M. Masuda completely characterize the h-vectors of simplicial posets whose order complexes are spheres. In this paper we examine the corresponding question in the case where the order complex is a ball. Using the face rings of these posets, we develop a series of new conditions on their h-vectors. We also present new methods for constructing poset balls with specific h-vectors. Combining this work with a new result of S. Murai we are able to give a complete characterization of the h-vectors of simplicial poset balls in all even dimensions, as well as odd dimensions less than or equal to five.     

Special simplices and Gorenstein toric rings

Athanasiadis [Ehrhart polynomials, simplicial polytopes, magic squares and a conjecture of Stanley, J. Reine Angew. Math., to appear.] studies an effective technique to show that Gorenstein sequences coming from compressed polytopes are unimodal. In the present paper we will use such the technique to find a rich class of Gorenstein toric rings with unimodal h-vectors arising from finite graphs.     

h-Vectors of matroids and logarithmic concavity

Let M be a matroid on E, representable over a field of characteristic zero. We show that h-vectors of the following simplicial complexes are log-concave:

1.

The matroid complex of independent subsets of E.     

On face numbers of manifolds with symmetry

Necessary conditions on the face numbers of Cohen-Macaulay simplicial complexes admitting a proper action of the cyclic group of a prime order are given. This result is extended further to necessary conditions on the face numbers and the Betti numbers of Buchsbaum simplicial complexes with a proper -action. Adin's upper bounds on the face numbers of Cohen-Macaulay complexes with symmetry are shown to hold for all (d−1)-dimensional Buchsbaum complexes with symmetry on n?3d−2 vertices. A generalization of Kühnel's conjecture on the Euler characteristic of 2k-dimensional manifolds and Sparla's analog of this conjecture for centrally symmetric 2k-manifolds are verified for all 2k-manifolds on n?6k+3 vertices. Connections to the Upper Bound Theorem are discussed and its new version for centrally symmetric manifolds is established.     

Multicomplexes and polynomials with real zeros

We show that each polynomial a(z)=1+a₁z+?+a_dz^d in N[z] having only real zeros is the f-polynomial of a multicomplex. It follows that a(z) is also the h-polynomial of a Cohen-Macaulay ring and is the g-polynomial of a simplicial polytope. We conjecture that a(z) is also the f-polynomial of a simplicial complex and show that the multicomplex result implies this in the special case that the zeros of a(z) belong to the real interval [-1,0). We also show that for fixed d the conjecture can fail for at most finitely many polynomials having the required form.     

Balanced subdivision and enumeration in balanced spheres

We study here the affine space generated by the extendedf-vectors of simplicial homology (d – 1)-spheres which are balanced of a given type. This space is determined, and its dimension is computed, by deriving a balanced version of the Dehn-Sommerville equations and exhibiting a set of balanced polytopes whose extendedf-vectors span it. To this end, a unique minimal complex of a given type is defined, along with a balanced version of stellar subdivision, and such a subdivision of a face in a minimal complex is realized as the boundary complex of a balanced polytope. For these complexes, we obtain an explicit computation of their extendedh-vectors, and, implicitly,f-vectors.Supported in part by NSF Grant DMS-8403225.     

Iterated homology and decompositions of simplicial complexes

Kalai has conjectured that a simplicial complex can be partitioned into Boolean algebras at least as roughly, as a shifting-preserving collapse sequence of its algebraically shifted complex. In particular, then, a simplicial complex could (conjecturally) be partitioned into Boolean intervals whose sizes are indexed by its iterated Betti numbers, a generalization of ordinary homology Betti numbers. This would imply a long-standing conjecture made (separately) by Garsia and Stanley concerning partitions of Cohen-Macaulay complexes into Boolean intervals. We prove a relaxation of Kalai’s conjecture, showing that a simplicial complex can be partitioned into recursively defined spanning trees of Boolean intervals indexed by its iterated Betti numbers.     

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.     

Enriched homology and cohomology modules of simiplicial complexes

For a simplicial complex Δ on {1, 2,…, n} we define enriched homology and cohomology modules. They are graded modules over k[x ₁,…, x _n ] whose ranks are equal to the dimensions of the reduced homology and cohomology groups. We characterize Cohen-Macaulay, l-Cohen-Macaulay, Buchsbaum, and Gorenstein^* complexes Δ, and also orientable homology manifolds in terms of the enriched modules. We introduce the notion of girth for simplicial complexes and make a conjecture relating the girth to invariants of the simplicial complex. We also put strong vanishing conditions on the enriched homology modules and describe the simplicial complexes we then get. They are block designs and include Steiner systems S(c, d, n) and cyclic polytopes of even dimension. This paper is to a large extent a complete rewriting of a previous preprint, “Hierarchies of simplicial complexes via the BGG-correspondence”. Also Propositions 1.7 and 3.1 have been generalized to cell complexes in [11].     

Shellable graphs and sequentially Cohen-Macaulay bipartite graphs

Associated to a simple undirected graph G is a simplicial complex ΔG whose faces correspond to the independent sets of G. We call a graph G shellable if ΔG is a shellable simplicial complex in the non-pure sense of Björner-Wachs. We are then interested in determining what families of graphs have the property that G is shellable. We show that all chordal graphs are shellable. Furthermore, we classify all the shellable bipartite graphs; they are precisely the sequentially Cohen-Macaulay bipartite graphs. We also give a recursive procedure to verify if a bipartite graph is shellable. Because shellable implies that the associated Stanley-Reisner ring is sequentially Cohen-Macaulay, our results complement and extend recent work on the problem of determining when the edge ideal of a graph is (sequentially) Cohen-Macaulay. We also give a new proof for a result of Faridi on the sequentially Cohen-Macaulayness of simplicial forests.     

Strongly Signable and Partitionable Posets

The class ofStrongly Signablepartially ordered sets is introduced and studied. It is show that strong signability, reminiscent of Björner–Wachs' recursive coatom orderability, provides a useful and broad sufficient condition for a poset to be dual CR and hence partitionable. The flagh-vectors of strongly signable posets are therefore non-negative. It is proved that recursively shellable posets, polyhedral fans, and face lattices of partitionable simplicial complexes are all strongly signable, and it is conjectured that all spherical posets are. It is concluded that the barycentric subdivision of a partitionable complex is again partitionable, and an algorithm for producing a partitioning of the subdivision from a partitioning of the complex is described. An expression for the flagh-polynomial of a simplicial complex in terms of itsh-vector is given, and is used to demonstrate that the flagh-vector is symmetric or non-negative whenever theh-vector is.     

The Number of M-Sequences and f-Vectors

M -sequences (a.k.a. f-vectors for multicomplexes or O-sequences) in terms of the number of variables and a maximum degree. In particular, it is shown that the number of M-sequences for at most 2 variables are powers of two and for at most 3 variables are Bell numbers. We give an asymptotic estimate of the number of M-sequences when the number of variables is fixed. This leads to a new lower bound for the number of polytopes with few vertices. We also prove a similar recursive formula for the number of f-vectors for simplicial complexes. Keeping the maximum degree fixed we get the number of M-sequences and the number of f-vectors for simplicial complexes as polynomials in the number of variables and it is shown that these numbers are asymptotically equal. Received: February 28, 1996/Revised: February 26, 1998     

On the generalized lower bound conjecture for polytopes and spheres

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If P is a simplicial d-polytope then its h-vector (h ₀, h ₁, …, h _d ) satisfies $ {h_0}\leq {h_1}\leq \ldots \leq {h_{{\left\lfloor {{d \left/ {2} \right.}} \right\rfloor }}} $ . Moreover, if h _r?1 = h _r for some $ r\leq \frac{1}{2}d $ then P can be triangulated without introducing simplices of dimension ≤d ? r. The first part of the conjecture was solved by Stanley in 1980 using the hard Lefschetz theorem for projective toric varieties. In this paper, we give a proof of the remaining part of the conjecture. In addition, we generalize this result to a certain class of simplicial spheres, namely those admitting the weak Lefschetz property.     

Gal’s conjecture for nestohedra corresponding to complete bipartite graphs

Convex polytopes have interested mathematicians since very ancient times. At present, they occupy a central place in convex geometry, combinatorics, and toric topology and demonstrate the harmony and beauty of mathematics. This paper considers the problem of describing the f-vectors of simple flag polytopes, that is, simple polytopes in which any set of pairwise intersecting facets has nonempty intersection. We show that for each nestohedron corresponding to a connected building set, the h-polynomial is a descent-generating function for some class of permutations; we also prove Gal’s conjecture on the nonnegativity of γ-vectors of flag polytopes for nestohedra constructed over complete bipartite graphs.