Relationships between shellability, vertex decomposability, and h-vectors of simplicial complexes.

摘要

Simplicial complexes are important from both a combinatorial and topological point of view. Associated to a simplicial complex is a vector called the f-vector, whose entries count the number of faces of each dimension in the complex. Understanding the f-vector, and in particular, which vectors arise as f-vectors is an important problem in geometric combinatorics. In this thesis, we study two structural properties---namely shellability and vertex decomposability---that simplicial complexes may have that give restrictions on possible f-vectors for complexes with these properties. It is well known that vertex decomposable simplicial complexes are shellable and that this inclusion is strict. We give sufficient conditions under which a shelling will give rise to a vertex decomposition. This result is applied to give new proofs of the vertex decomposability of type A and B Coxeter complexes and CL-shellable partially ordered sets. Some of the ideas behind this criterion are used to prove vertex decomposability of CC-shellable partially ordered sets. To each graph, G, is associated a coloring complex DeltaG. There is a vector containing the same data as the f-vector called the h-vector. The h-vector associated to DeltaG encodes the chromatic polynomial of G. It is known that Delta G is Cohen-Macaulay, shellable, and has a convex ear decomposition, which in turn give constraints on possible chromatic polynomials as well as further information about them. We present a Z2 -action on DeltaG, which forces further restrictions upon possible chromatic polynomials. We give asymptotic proofs of some of the known h-vector inequalities, as well as combinatorial explanations of special cases of these known inequalities. In addition, we present a recursive formulation of the h-vector of Delta G. In the case that G is a complete graph, the coloring complex is precisely the codimension one skeleton of the type A Coxeter complex. We prove the k-skeleton of a vertex decomposable simplicial complex is itself vertex decomposable, thus proving vertex decomposability of coloring complexes associated to complete graphs.