arXiv:1302.4401v1 [math.CO] 18 Feb 2013

f -vectors implying vertex decomposability
Michał Lasoń
Abstract. We prove that if a pure simplicial complex ∆ of dimension d with
n facets has the least possible number of (d − 1)-dimensional faces among all
complexes with n faces of dimension d, then it is vertex decomposable. This
answers a question of J. Herzog and T. Hibi. In fact we prove a generalization
of their theorem using combinatorial methods.

1. Introduction
We call a simplicial complex pure if all its facets are of the same dimension.
Definition 1. A pure simplicial complex ∆ of dimension d and n facets is
called extremal if it has the least possible number of (d − 1)-dimensional faces
among all complexes with n faces of dimension d.
In particular, for d = 0 all zero dimensional complexes are extremal, since all
of them have exactly one (−1)-dimensional face, namely the empty set.
In this paper we generalize and prove by only combinatorial means the following
theorem of Herzog and Hibi form 1999.
Theorem 1. ([8], Theorem 2.3) An extremal simplicial complex is CohenMacaulay over an arbitrary field.
Their proof is algebraic and uses results from [1] and [6]. In fact they asked for
a combinatorial proof. We give it by proving that an extremal simplicial complex
is vertex decomposable. It is well-known that vertex decomposable complexes are
Cohen-Macaulay. Our proof goes along the lines of the proof of Kruskal-Katona
inequality. We start with a presentation of some necessary preliminaries.
1.1. Vertex decomposable and Cohen-Macaulay complexes. For a simplex σ in a simplicial complex ∆, the simplicial complex
{τ ∈ ∆ : τ ∩ σ = ∅ and τ ∪ σ ∈ ∆}
is called a link of σ in ∆, and denoted by lk∆ σ. For a vertex x of ∆ by ∆ \ x we
mean the simplicial complex {τ ∈ ∆ : x ∈
/ τ }.
2010 Mathematics Subject Classification. 05E45, 05E40, 13F55.
Key words and phrases. vertex decomposable simplicial complex, f -vector, Kruskal-Katona
theorem, Cohen-Macaulay module, Stanley-Reisner ring.
This publication is partly supported by the Polish National Science Centre grant no.
2011/03/N/ST1/02918.
1

2

MICHAŁ LASOŃ

Definition 2. A pure simplicial complex ∆ is vertex decomposable if one of
the following holds:
(1) ∆ is empty,
(2) ∆ is a single vertex,
(3) for some vertex x both lk∆ {x} and ∆\x are pure and vertex decomposable.
Definition 3. For a simplicial complex ∆ on the set of vertices {1, . . . , n} and
a given field K, the Stanley-Reisner ring (the face ring) is K[∆] := K[x1 , . . . , xn ]/I,
where I is generated by all square-free monomials xi1 · · · xil for which {i1 , . . . , il }
is not a face in ∆.
When we say that a simplicial complex is Cohen-Macaulay we always mean
that its Stanley-Reisner ring has this property.
The following is a folklore result (we refer the reader to e.g. [2]).
Theorem 2. For a simplicial complex ∆ the following implications hold:
∆ is vertex decomposable ⇒ ∆ is shellable ⇒ ∆ is Cohen-Macaulay over any field.
We recall a combinatorial description of Cohen-Macaulay complexes.
Theorem 3. ([13]) Let R = K[∆] be the face ring of ∆. Then the following
conditions are equivalent:
(1) R is Cohen-Macaulay ring,
(2) H̃i (lk∆ σ; K) = 0 for i < dim(lk∆ σ) for all simplices σ ∈ ∆.
For classical techniques of counting homologies we refer the reader to [7], [14].
For entertaining ones we advise Section 3.2 of [12].
1.2. Kruskal-Katona theorem. One of the most natural questions concerning simplicial complexes is:
What is the minimum number of (k − 1)-element faces in simplicial complex with
n faces of size k?
This question was answered independently by Kruskal [11] and Katona [10] in
1960’s. For a positive integer k, they enlisted all k-element subsets of integers in
the following order, called the squashed order : A < B if max(A \ B) < max(B \ A).
Let Sk (n) be the set of first n sets in this list. For a given set U of k-element
sets, denote by ∆U the set of all (k − 1)-element sets which are contained in some
member of U. The Kruskal-Katona theorem reads as follows.
Theorem 4. For a positive integers n, k and a set U of n sets of size k we have
|∆U| ≥ |∆Sk (n)| .
This result was further generalized by Clements and Lindström in [3]. Daykin
[4, 5] gave two simple proofs, and later Hilton [9] gave another one. For an algebraic
proof we refer the reader to [1]. We will work mainly with Hilton’s idea.
Note that the cardinality of ∆Sk (n) may be easily determined. For a given k,
each positive integer n can be uniquely expressed as

 
  
at
ak−1
ak
,
+ ··· +
+
n=
t
k−1
k
with 1 ≤ t ≤ at and at < · · · < ak . We have



 

at
ak−1
ak
.
+ ···+
+
δk−1 (n) := |∆Sk (n)| =
t−1
k−2
k−1

f -VECTORS IMPLYING VERTEX DECOMPOSABILITY

3

As a consequence of Kruskal-Katona theorem we get:
Corollary 1. A pure simplicial complex ∆ of dimension d > 0 with f -vector
(f0 , . . . , fd ) is extremal if and only if fd−1 = δd (fd ).
2. The main result
For a better understanding of the assumption that ∆ is extremal we will use
Hilton’s idea from his proof [9] of the Kruskal-Katona theorem. First we define sets
similar to Sk (n). Let Ski (n) denote the first n sets of k-element subsets of integers
in the squashed order (A < B if max(A \ B) < max(B \ A)) which do not contain
i. We also denote by {i}(∪)U the set {{i} ∪ A : A ∈ U}. S
Let U be a n-element set of k-element sets, let V = A∈U A be an underlying
set, and let v be its cardinality. For i ∈ V , let Bi = {A ∈ U : i ∈
/ A}, Ci = {A \ {i} :
i ∈ A ∈ U}, and let bi , ci be the respective cardinalities. Note that ci 6= 0. We want
to find an index i such that |∆Bi | > |Ci |.
Lemma 1. Either there exists an i such that |∆Bi | > |Ci |, or U consists of all
possible k-element subsets of V .
Proof. We are going to count the sum of cardinalities of both sets when i
runs over all elements of V . Then
X
X
|∆Bi | ≥ kn(v − k)/(v − k) = kn =
|Ci | ,
i∈V

i∈V

since at left hand side each A ∈ U gives k distinct sets in its boundary, and it is
counted once for every i ∈
/ A. Some sets in boundaries of sets from Bi can be the
same, but their number is at most (v − 1) − (k − 1) = v − k. On the other hand
each A ∈ U is counted k times at the right side. Hence we can find a desired i, or
the above bounds are tight. In the latter case, when A ∈ ∆Bi , all v − k possibilities
of completing it to a k-element set has to be in U. This means that U consists of
all possible k-element subsets of V because from any set in U we can delete any
element and insert any other.

Lemma 2. If ∆ is an extremal simplicial complex of positive dimension, then
there exists a vertex x such that both lk∆ {x} and ∆ \ x are extremal.
Proof. Let ∆ be of dimension d − 1 > 0 and let U be the set of all d-element
sets in ∆. If U consists of all possible d-element subsets of a given v-element set,
then the assertion of the lemma is clearly true (we can take any vertex). Otherwise,
due to Lemma 1, there exists an i ∈ V such that |∆Bi | > |Ci |. We have that
∆U = ∆Bi ∪ Ci ∪ ({i}(∪)∆Ci ).
Since ∆Bi and {i}(∪)∆Ci are disjoint, it follows that
|∆U| ≥ |∆Bi | + |{i}(∪)∆Ci | > |Ci | + |{i}(∪)∆Ci | .
So, by Theorem 4,
(2.1)

i
|∆U| ≥ ∆Sdi (bi ) + {i}(∪)∆Sd−1
(ci ) ,

and
(2.2)

i
i
|∆U| > Sd−1
(ci ) + {i}(∪)∆Sd−1
(ci ) .

i
Since ∆Sdi (bi ) = Sd−1
(e) for some e, there are now two possibilities:

4

MICHAŁ LASOŃ

i
(1) ∆Sdi (bi ) ⊂ Sd−1
(ci ), then by (2.2) we get
i
i
i
|∆U| > Sd−1 (ci ) + {i}(∪)∆Sd−1
(ci ) = ∆(Sdi (bi ) ∪ ({i}(∪)Sd−1
(ci ))) ,
which contradicts the assumption that ∆ is extremal, since a complex
i
generated by sets Sdi (bi ) ∪ ({i}(∪)Sd−1
(ci )) has bi + ci = |U| maximal
faces.
i
(2) ∆Sdi (bi ) ⊃ Sd−1
(ci ), then by (2.1) we obtain
i
i
i
|∆U| ≥ ∆Sd (bi ) + {i}(∪)∆Sd−1
(ci ) = ∆(Sdi (bi ) ∪ ({i}(∪)Sd−1
(ci ))) ,
i
and equality holds if and only if Ci ⊂ ∆Bi , |∆Bi | = ∆Sd (bi ) , and
i
i
|∆Ci | = {i}(∪)∆Sd−1
(ci ) = ∆Sd−1
(ci ) .
The complex ∆ is extremal, so equality holds, and we get that Ci ⊂ ∆Bi and
[Bi ], [Ci ] are extremal, where [A] means the simplicial complex generated by the
set of faces A. Observe that lk∆ {i} = [Ci ] and ∆ \ i = [Bi ]. The first equality
is obvious, while the second is not as clear. If σ = {v1 , . . . , vk } is a face in ∆ \ i
then it is a subface of some facet F = {v1 , . . . , vd }. If i does not belong to F then
F ∈ [Bi ] and so σ does. Otherwise, F \ {i} ∈ Ci ⊂ ∆Bi , so F \ {i} ∪ {j} ∈ Bi for
some j. Hence σ ∈ [Bi ]. Now i = x gives the assertion.


Finally, we are ready to prove the generalization of Theorem 1.
Theorem 5. An extremal simplicial complex is vertex decomposable.
Proof. The proof goes by an induction on d the dimension of ∆ and secondly
on the number of facets. If d = 0 then ∆ consists of points and by the definition
it is vertex decomposable. When d > 0, then by Lemma 2 there exists a vertex
x, such that both complexes lk∆ {x} and ∆ \ x are extremal. The first is of lower
dimension; and the second either has the same dimension as ∆ but fewer facets, or
it has smaller dimension. By the inductive hypothesis, both lk∆ {x} and ∆ \ x are
vertex decomposable, and as a consequence ∆ also is.

The above result is best possible in the following sense. Let ∆ be a pure
simplicial complex of dimension d > 0 with f -vector (f0 , . . . , fd ), and with fd−1 =
δd (fd )+c, c ∈ N. Due to Corollary 1 the meaning of Theorem 5 is that if c = 0, then
∆ is vertex decomposable. But even for c = 1 complex ∆ does not have to be CohenMacaulay, which by Theorem 2 is a weaker property then vertex decomposability.
We show the following.
Example 1. We have that δd (2) = 2d+1. Let ∆ be a pure simplicial complex of
dimension d with the set of facets U consisting of two disjoint ones. Then |∆U| =
2d + 2, and H̃0 (lk∆ ∅; K) = 1, so due to Theorem 3 complex ∆ is not CohenMacaulay over any field K, and as a consequence it is also not vertex decomposable.
Acknowledgements
I would like to thank Ralf Fröberg and Jürgen Herzog for many inspiring conversations and introduction to this subject. I would also like to thank Jarek Grytczuk
and Piotr Micek for help in preparation of this manuscript.
References
[1] A. Aramova, J. Herzog, T. Hibi, Gotzmann theorems for exterior algebras and combinatorics,
J. Algebra 191 (1997), 174-211.
[2] A. Björner, Topological methods, in Handbook of Combinatorics, R. Graham, M. Grötschel,
L. Lovász, Elsevier, Amsterdam (1995), 1819-1872.

f -VECTORS IMPLYING VERTEX DECOMPOSABILITY

5

[3] G. Clements, B. Lindstöm, A generalization of a combinatorial theorem of Macaulay, J.
Combin. Theory 7 (1969), 230-238.
[4] D. Daykin, A simple proof of the Kruskal-Katona theorem, J. Combin. Theory A 17 (1974),
252-253.
[5] D. Daykin, An algorithm for cascades giving Katona-type inequalities, Nanta Math. 8 (1975),
78-83.
[6] J. Eagon, V. Reiner, Resolutions of Stanley-Reisner rings and Alexander duality, J. Pure
Appl. Algebra 130 (1989), 265-275.
[7] A. Hatcher, Algebraic Topology, Cambridge University Press 2002.
[8] J. Herzog, T. Hibi, Componentwise linear ideals, Nagoya Math. J. 153 (1999), 141-153.
[9] A. Hilton, A simple proof of the Kruskal-Katona theorem and of some associated binomial
inequalities, Period. Math. Hungar. 10 (1979), no. 1, 25-30.
[10] G. Katona, A theorem of ﬁnite sets, Theory of Graphs (Proc. Colloq. Tihany, 1966), 187-207.
Academic Press, New York, 1968.
[11] J. Kruskal, The number of simplices in a complex, Mathematical Optimalization Techniques,
University of California Press, Berkeley, 1963, 251-278.
[12] M. Lasoń, M. Michałek, On the full, strongly exceptional collections on toric varieties with
Picard number three, Coll. Math. 62 (2011), no. 3, 275-296.
[13] G. Reisner, Cohen-Macaulay quotients of polynomial rings, Advances in Math. 21 (1976), no.
1, 30-49.
[14] R. Stanley, Combinatorics and Commutative Algebra, Birkhäuser.
Theoretical Computer Science Department, Faculty of Mathematics and Computer
Science, Jagiellonian University, S.Łojasiewicza 6, 30-348 Kraków, Poland
Institute of Mathematics of the Polish Academy of Sciences, Śniadeckich 8, 00-956
Warszawa, Poland
E-mail address: michalason@gmail.com

