ON f - AND h-VECTORS OF RELATIVE SIMPLICIAL COMPLEXES

arXiv:1711.02729v1 [math.CO] 7 Nov 2017

GIULIA CODENOTTI, LUKAS KATTHÄN, AND RAMAN SANYAL

Abstract. A relative simplicial complex is a collection of sets of the form ∆ \ Γ, where Γ ⊂ ∆ are
simplicial complexes. Relative complexes played key roles in recent advances in algebraic, geometric,
and topological combinatorics but, in contrast to simplicial complexes, little is known about their
general combinatorial structure. In this paper, we address a basic question in this direction and give
a characterization of f -vectors of relative (multi)complexes on a ground set of fixed size. On the
algebraic side, this yields a characterization of Hilbert functions of quotients of homogeneous ideals
over polynomial rings with a fixed number of indeterminates.
Moreover, we characterize h-vectors of fully Cohen–Macaulay relative complexes as well as hvectors of Cohen–Macaulay relative complexes with minimal faces of given dimensions. The latter
resolves a question of Björner.

1. Introduction
A simplicial complex ∆ is a collection of subsets of a finite ground set, say [n] := {1, . . . , n}, such
that σ ∈ ∆ and τ ⊆ σ implies τ ∈ ∆. Simplicial complexes are fundamental objects in algebraic,
geometric, and topological combinatorics; see, for example, [Sta96, BS, Bjö95]. A basic combinatorial
statistic of ∆ is the face vector (or f -vector)
f (∆) = (f−1 , f0 , . . . , fd−1 ) ,
where fk = fk (∆) records the number of faces σ ∈ ∆ of dimension k, where dim σ := |σ| − 1
and d − 1 = dim ∆ := max{dim σ : σ ∈ ∆}. Notice that we allow ∆ = ∅, the void complex,
which is the only complex with fk (∆) = 0 for all k ≥ −1. A relative simplicial complex Ψ
on the ground set [n] is the collection of sets ∆ \ Γ = {τ ∈ ∆ : τ 6∈ Γ}, where Γ ⊂ ∆ ⊆ 2[n] are
simplicial complexes. In general, the pair of simplicial complexes (∆, Γ) is not uniquely determined
by Ψ, and we call Ψ = (∆, Γ) a presentation of Ψ. We set dim Ψ := max{dim σ : σ ∈ ∆ \ Γ}.
Relative complexes were introduced by Stanley [Sta87] and made prominent recent appearances in,
for example, [AS16, DGKM16]. The f -vector of a relative complex is given by
f (Ψ) := f (∆) − f (Γ) ,
where we set fk (Γ) := 0 for all k > dim Γ. When Γ = ∅, then Ψ is simply a simplicial complex
and we write ∆ instead of Ψ. We call Ψ a proper relative complex if Γ 6= ∅ or, equivalently, if
f−1 (Ψ) = 0.
In contrast to simplicial complexes, much less is known about the combinatorics of relative simplicial
complexes. The first goal of this paper is to address the following basic question:
Which vectors f = (0, f0 , . . . , fd−1 ) ∈ Zd+1
≥0 are f -vectors of proper relative simplicial complexes?
For simplicial complexes, this question is beautifully answered by the Kruskal–Katona theorem [Kru63,
Kat68]. Björner and Kalai [BK88] characterized the pairs (f (∆), β(∆)) where ∆ is a simplicial complex and β(∆) is the sequence of Betti numbers of ∆ (over a field k). Duval [Duv99] characterized
Date: November 9, 2017.
2010 Mathematics Subject Classification. Primary: 05E45. Secondary: 05E40, 13F55.
Key words and phrases. relative simplicial complex, f -vector, Kruskal–Katona theorem, Hilbert functions, h-vector,
Macaulay theorem.
1

2

GIULIA CODENOTTI, LUKAS KATTHÄN, AND RAMAN SANYAL

the pairs (f (∆), f (Γ)) where ∆ ⊆ Γ but, as stated before, the presentation Ψ = ∆ \ Γ is generally
not unique. Moreover, the following example shows that a characterization of f -vectors of relative
complexes is trivial without further qualifications.
Example 1. If ∆ = 2[k+1] is a k-dimensional simplex and ∂∆ := ∆ \ {[k + 1]} denotes its boundary
complex, then fi (∆, ∂∆) = 1 if i = k and = 0 otherwise. Hence, by observing that relative simplicial
complexes are closed under disjoint unions, any vector f = (0, f0 , . . . , fd−1 ) ∈ Zd+1
≥0 can occur as the
f -vector of a proper relative simplicial complex.
The main difference between f -vectors of complexes and relative complexes is that f0 (Ψ) does not
reveal the size of the ground set and the construction outlined in Example 1 produces relative
complexes with given f -vectors on large ground sets. Restricting the size of the ground set is the key
to a meaningful treatment of f -vectors of relative complexes. To state our characterization, we need
to recall the binomial representation of a natural number: For any r, k ∈ Z≥0 with k > 0, there are
unique integers rk > rk−1 > · · · > r1 ≥ 0 such that
  

 
rk
rk−1
r1
(1)
r =
.
+
+ ··· +
1
k
k−1
We refer the reader to Greene–Kleitman’s excellent article [GK78, Sect. 8] for details and combinatorial motivations for this and the following definition. For the representation given in (1) we
define

 

 
rk
rk−1
r1
∂k (r) :=
+
+ ··· +
.
k−1
k−2
0
We prove the following characterization of f -vectors of proper relative complexes in Section 2.
Theorem 1. Let f = (0, f0 , . . . , fd−1 ) ∈ Zd+1
≥0 and n > 0 and define two sequences (a0 , . . . , ad−1 )
and (b0 , . . . , bd−1 ) by ad−1 := fd−1 and bd−1 := 0 and continue recursively
ak−1 := max(∂k+1 (ak ), fk−1 + ∂k+1 (bk ))
bk−1 := max(∂k+1 (bk ), ∂k+1 (ak ) − fk−1 )
for k ≥ 0. Then there is a proper relative simplicial complex Ψ on the ground set [n] with f = f (Ψ)
if and only if a0 ≤ n.
(Relative) simplicial complexes can be generalized to (relative) multicomplexes by replacing sets with
multisubsets. The notion of an f -vector of a multicomplex is immediate (by taking into account multiplicities) and the question above carries over to relative multicomplexes on a ground set of fixed
size. Multicomplexes are more natural from an algebraic perspective: If S := k[x1 , . . . , xn ] is the
polynomial ring over a field k with n indeterminates and I ⊆ S is a monomial ideal, then the monomials outside I form a (possibly infinite) multicomplex on ground set [n] and every multicomplex
over [n] arises this way. In particular, the f -vector of a multicomplex is the Hilbert function of S/I.
By appealing to initial ideals it is easy to see that f -vectors of (infinite) multicomplexes are exactly
the Hilbert functions of standard graded algebras, which were characterized by Macaulay [Mac27].
In Section 3 we give precise definitions and Theorem 5 is the corresponding analogue of Theorem 1
for proper, possibly infinite, relative multicomplexes. The corresponding algebraic statement characterizes Hilbert functions of I/J where J ⊂ I ⊆ S are pairs of homogeneous ideals; see Corollary 7.
The h-vector h(Ψ) = (h0 , . . . , hd ) of a (d − 1)-dimensional relative complex Ψ is defined through
(2)

d
X
k=0

fk−1 (Ψ)td−k =

d
X

hi (Ψ)(t + 1)d−i .

i=0

The h-vector clearly carries the same information as the f -vector but it has been amply demonstrated
that h-vectors often times reveal more structure; see [Sta96] for example. In particular, if ∆ is a

ON f - AND h-VECTORS OF RELATIVE SIMPLICIAL COMPLEXES

3

Cohen–Macaulay simplicial complex (or CM complex, for short) over some field k, then hi (∆) ≥ 0
for all i ≥ 0. Stanley [Sta77] showed that Macaulay’s theorem characterizing Hilbert functions of
standard graded algebras yields a characterization of h-vectors of CM complexes akin to the Kruskal–
Katona theorem. Stronger even, Björner, Frankl, and Stanley [BFS87] showed that all admissible
h-vectors can be realized by shellable simplicial complexes, a proper subset of CM complexes.
In Section 4, we give a characterization of h-vectors of fully CM relative complexes. We call a relative
complex Ψ fully Cohen–Macaulay over a ground set [n] if it has a presentation Ψ = (∆, Γ) with
Γ ⊂ ∆ ⊆ 2[n] , dim Γ = dim Ψ, and Ψ as well as ∆ and Γ are Cohen–Macaulay.
For r, k ∈ Z≥0 with k > 0, let rk > · · · > r1 ≥ 0 as defined by (1). We define

 



rk − 1
rk−1 − 1
r1 − 1
e
∂k (r) :=
+
+ ··· +
.
k−1
k−2
0
Note that Ψ is proper if and only if h0 (Ψ) = 0. Our characterization of h-vectors of fully CM complexes parallels that of CM complexes in that it suffices to consider fully shellable relative complexes;
see Section 4 for a definition.
Theorem 2. Let h = (0, h1 , . . . , hd ) ∈ Zd+1
≥0 and n > 0. Then the following are equivalent:
(a) There is a fully CM relative complex Ψ on ground set [n] with h = h(Ψ);
(b) There is a fully shellable relative complex Ψ on ground set [n] with h = h(Ψ);
(c) Let (a0 , . . . , ad−1 ) and (b0 , . . . , bd−1 ) be the sequences defined through ad−1 := hd and bd−1 := 0
and recursively continued
ai−1 := max(∂ei+1 (ai ), hi + ∂ei+1 (bi ))
bi−1 := max(∂ei+1 (bi ), ∂ei+1 (ai ) − hi )
for i ≥ 1. Then a0 ≤ n − d.
In Section 5, we discuss the difference between CM and fully CM relative complexes. In particular,
we show in Theorem 9 that every (d − 1)-dimensional CM relative complex has a presentation as a
fully CM relative complex if we allow the ground set to grow by at most d elements. From this, we
derive the following necessary condition on h-vectors of proper CM relative complexes.
Corollary 3. Let h = (0, h1 , . . . , hd ) ∈ Zd+1
≥0 and n > 0. Further, let (a0 , . . . , ad−1 ) and (b0 , . . . , bd−1 )
be the sequences defined in Theorem 2(c). If there exists a CM relative complex Ψ on ground set [n]
with h = h(Ψ), then a0 ≤ n.
We conjecture that it actually suffices to extend the ground set by a single new vertex. This would
strengthen the bound of Corollary 3 to n − d + 1.
Finally, Theorem 10 gives characterization of h-vectors of relative multicomplexes if the dimensions
of the minimal faces of Ψ = ∆ \ Γ are given. This resolves a question of A. Björner stated in [Sta87].

Acknowledgments. Research that led to this paper was supported by the National Science Foundation under Grant No. DMS-1440140 while the authors were in residence at the Mathematical
Sciences Research Institute in Berkeley, California, during the Fall 2017 semester on Geometric and
Topological Combinatorics. G.C. was also supported by the Center for International Cooperation at
Freie Universität Berlin and the Einstein Foundation Berlin. L.K. was also supported by the DFG,
grant KA 4128/2-1. R.S. was also supported by the DFG Collaborative Research Center SFB/TR
109 “Discretization in Geometry and Dynamics”.

4

GIULIA CODENOTTI, LUKAS KATTHÄN, AND RAMAN SANYAL

2. f -vectors of relative simplicial complexes
The proof of Theorem 1 follows the same ideas as that of the classical Kruskal–Katona theorem given
in [GK78, Sect. 8]. A simplicial complex ∆ ⊂ 2[n] is called compressed if its set of k-faces forms an
initial segment with respect to the reverse lexicographic order on the (k + 1)-subsets of [n], for each
k. Note that if ∆ and Γ are both compressed simplicial complexes and fk (Γ) ≤ fk (∆) for all k, then
Γ ⊆ ∆. The Kruskal–Katona theorem now states that f is the f -vector of a simplicial complex if
and only if it is the f -vector of a compressed simplicial complex, which can be checked by numerical
conditions.
Theorem 4 (Kruskal [Kru63], Katona [Kat68]). For a vector f = (1, f0 , . . . , fd−1 ) ∈ Zd+1
≥0 , the
following conditions are equivalent:
(a) f is f -vector of a simplicial complex;
(b) f is f -vector of a compressed simplicial complex;
(c) ∂k+1 (fk ) ≤ fk−1 for all k ≥ 1.
The shadow of a family of k-sets consists of all (k − 1)-subsets of the k-sets of the family. The
Kruskal-Katona theorem tells us that ∂k+1 (r) is the minimum size of the shadow of a family k-sets of
size r. Actually, this minimum is always achieved if the family is compressed. Note that this implies
in particular that the function ∂k are monotone.
With these preparations, we can now give the proof of our Theorem 1.
Proof of Theorem 1. Let us recall the definition of the sequences (a0 , . . . , ad−1 ) and (b0 , . . . , bd−1 ).
We have that ad−1 = fd−1 , bd−1 = 0 and
ak−1 = max(∂k+1 (ak ), fk−1 + ∂k+1 (bk ))

= ∂k+1 (ak ) + max(0, fk−1 − (∂k+1 (ak ) − ∂k+1 (bk )));

bk−1 = max(∂k+1 (bk ), ∂k+1 (ak ) − fk−1 )

= ∂k+1 (bk ) + max(0, (∂k+1 (ak ) − ∂k+1 (bk )) − fk−1 ).

for 1 ≤ k ≤ d − 1. From the second expression for ak−1 and bk−1 it is easy to see that ak−1 − bk−1 =
fk−1 . In particular, we have that ak ≥ bk for k ≥ 0.
We now show the sufficiency of the condition, so assume that a0 ≤ n. As both sequences (a0 , . . . , ad−1 )
and (b0 , . . . , bd−1 ) satisfy the condition of the Kruskal-Katona theorem (Theorem 4), there exist
compressed simplicial complexes Γ, ∆ ⊂ 2[n] whose respective f -vectors equal the two sequences. In
particular, since both complexes are compressed and fk (Γ) = bk ≤ ak = fk (∆), it holds that Γ ⊂ ∆,
and the relative complex Ψ := (∆, Γ) has f -vector f .
Now we turn to the necessity of our condition. Assume that we are given a relative complex Ψ =
(∆, Γ) on the ground set [n] with f (Ψ) = f . We show by induction on k that ak ≤ fk (∆) and
bk ≤ fk (Γ) for k ≥ 0.
The base case k = d − 1 is obvious. For the inductive step, it follows from Theorem 4 that fk−1 (∆) ≥
∂k+1 (fk (∆)), and further fk (∆) ≥ ak implies that ∂k+1 (fk (∆)) ≥ ∂k+1 (ak ). Similarly, it holds that
fk−1 (∆) = fk−1 + fk−1 (Γ) ≥ fk−1 + ∂k+1 (fk (Γ)) ≥ fk−1 + ∂k+1 (bk ). Together, this implies that
fk−1 (∆) ≥ max(∂k+1 (ak ), fk−1 + ∂k+1 (bk )) = ak−1 .
Moreover, the last inequality together with the fact that fk−1 (∆) − fk−1 (Γ) = ak−1 − bk−1 implies
that fk−1 (Γ) ≥ bk−1 . In particular, a0 ≤ f0 (∆) ≤ n.

3. f -vectors of relative multicomplexes
A k-multiset of [n] is a subset with repetitions allowed. We denote a k-multisubset of [n] by
e is a collection of
F = {s1 , s2 , . . . , sk }≤ where 1 ≤ s1 ≤ s2 ≤ · · · ≤ sk ≤ n. A multicomplex ∆
multisets closed under taking (multi-)subsets. The dimension of F is k − 1 and in the same way as

ON f - AND h-VECTORS OF RELATIVE SIMPLICIAL COMPLEXES

5

for simplicial complexes, one defines f -vectors of multicomplexes. Note that multicomplexes can be
infinite, even if the ground set is finite.
The sequences which arise as f -vectors of multicomplexes are called M -sequences and they have
a well-known classification due to Macaulay. Namely, a sequence (1, f0 , f1 , . . . ) is an M -sequence if
and only if fk−1 ≥ ∂ek+1 (fk ). Moreover, as in the simplicial case, for each M -sequence f there exists
e with f = f (∆).
e Here, being compressed is defined as in the
a unique compressed multicomplex ∆
simplicial case.
We refer the reader to [GK78, Sect. 8] of [Sta96, Sect. II.2] for details. Using these facts, the same
proof as for Theorem 1 also yields the following characterization for f -vectors of finite proper relative
e = (∆,
e Γ).
e
multicomplexes Ψ
Theorem 5. Let f = (0, f0 , . . . , fd−1 ) ∈ Zd+1
≥0 and n > 0 and define two sequences (a0 , . . . , ad−1 )
and (b0 , . . . , bd−1 ) by ad−1 := fd−1 and bd−1 := 0 and continue recursively
ak−1 := max(∂ek+1 (ak ), fk−1 + ∂ek+1 (bk ))
bk−1 := max(∂ek+1 (bk ), ∂ek+1 (ak ) − fk−1 )
e on the ground set [n] with f = f (Ψ)
e
for k ≥ 0. Then there is a proper (finite) relative multicomplex Ψ
if and only if a0 ≤ n.
Now we turn to the classification of f -vectors of not necessarily finite multicomplexes. In the proof
of Theorem 1, it was crucial that relative simplicial complexes have bounded dimension, so that we
could proceed by induction from the top dimension downwards. For general relative multicomplexes,
we will instead proceed from dimension 0 upwards. This requires some new notation. For r, k ∈ Z≥0
with k > 0, let rk > · · · > r1 ≥ 0 as defined by (1). We define

 



rk + 1
rk−1 + 1
r1 + 1
k
˜
∂ (r) :=
+
+ ··· +
.
k+1
k+2
2
It is not difficult to see that ∂ek+1 (∂˜k (r)) = r and ∂˜k−1 (∂ek (r)) ≥ r. Therefore, M -sequences can be
equivalently characterized as those sequences (f−1 , f0 , . . . ) which satisfy fk+1 ≥ ∂˜k+1 (fk ) for all k.
Theorem 6. Let f = (0, f0 , f1 , . . . ) be a sequence of non-negative integers and n > 0 and define two
sequences (a0 , a1 , . . . ) and (b0 , b1 , . . . ) by a0 := n, b0 := n − f0 and continue recursively
ak+1 := min(∂˜k+1 (ak ), fk+1 + ∂˜k+1 (bk ))
bk+1 := min(∂˜k+1 (bk ), ∂˜k+1 (ak ) − fk+1 )
e on the ground set [n] with f = f (Ψ)
e if
for k ≥ 0. Then, there is a proper relative multicomplex Ψ
and only if bk ≥ 0 for all k ≥ 0.
The proof is almost the same as the proof of Theorem 1, using the characterization of M -sequences in
terms of ∂˜k . The only difference is that in the proof of the necessity, one needs to start the induction
at k = 0 to the proceed in increasing order.
The classical theorem by Macaulay characterizes Hilbert functions of standard graded algebras, and
Theorem 6 has a similar interpretation:
Corollary 7 (Macaulay for quotients of ideals). Let H : Z≥0 → Z≥0 with H(0) = 0 and n ≥
H(1). Further, let (a0 , a1 , . . . ) and (b0 , b1 , . . . ) be the two sequences of Theorem 6, where we set
fk = H(k + 1). Then, there exist two proper homogeneous ideals J ⊂ I ( S := k[x1 , . . . , xn ] with
H(k) = H(I/J, k) for all k, if and only if bk ≥ 0 for all k ≥ 0.
Proof. Consider an ideal I ⊆ k[x1 , . . . , xn ]. For any fixed term order , the corresponding collection
e Since the standard monomials
of standard monomials is naturally identified with a multicomplex ∆.

6

GIULIA CODENOTTI, LUKAS KATTHÄN, AND RAMAN SANYAL

e coincides with the Hilbert series of
form a vector space basis of k[x1 , . . . , xn ]/I, the f -vector of ∆
k[x1 , . . . , xn ]/I. Therefore, any Hilbert series of a quotient of ideals also arises as f -vector of a
relative multicomplex.
e the monomial ideal corresponding to all mulFor the converse we associate to any multicomplex ∆
e
tisets not in ∆.

4. h-vectors of relative Cohen-Macaulay complexes
Let Ψ = (∆, Γ) be a (d − 1)-dimensional relative simplicial complex and let σ1 , . . . , σm be some
ordering of the inclusion-maximal faces (i.e., the facets) of Ψ. Define
Ψj := (2σ1 ∪ 2σ2 ∪ · · · ∪ 2σj ) ∩ (∆ \ Γ)
for j ≥ 1 and set Ψ0 := ∅. We call the ordering of the facets a shelling order if Ψj \ Ψj−1 has
a unique inclusion-minimal element R(σj ) for all j = 1, . . . , m. Consequently, Ψ is shellable if it
has a shelling order. If Γ = ∅ and hence Ψ is a simplicial complex, this recovers the usual notion of
shellability. The h-vector h(Ψ) of a shellable relative complex has a particularly nice interpretation:
hi (Ψ) = |{j : |R(σj )| = i}| ,
for 0 ≤ i ≤ d. It is shown in [Sta96, Sect. III.7] that a shellable relative complex is Cohen–Macaulay
but the converse does not need to hold.
We will call a relative complex Ψ fully shellable if it has a presentation Ψ = (∆, Γ) such that
dim Ψ = dim Γ and Ψ as well as ∆ and Γ are shellable. By the above remarks, it is clear that fully
shellable relative complexes are fully Cohen–Macaulay and, again, the converse does not necessarily
hold.
In light of Theorem 5, condition (c) of Theorem 2 states that h is the f -vector of a proper relative
multicomplex. In order to prove the implication (c) =⇒ (b), we will show that to every relative
multicomplex on ground set [n − d] with given f -vector h = (0, h1 , . . . , hd ), there is a fully shellable
relative complex Ψ with h(Ψ) = h. Since fully shellable implies fully Cohen–Macaulay, this also
proves (b) =⇒ (a).
e = (∆,
e Γ)
e be a proper relative (d − 1)-dimensional multicomplex on ground set [n − d] and
Let Ψ
e and Γ
e are compressed. To turn Ψ
e into a relative complex, we follow the construction
assume that ∆
in [BFS87]. Order the collection of multisets of size ≤ d on the ground set [n − d] by graded reverse
lexicographic order, and the collection of d-sets on [n] by reverse lexicographic order. There is a
unique bijection Φd between these two collections which preserves the given orders. Explicitly, the
map is
F = {b1 , b2 , . . . , bk }≤ 7→ Φd (F ) := {1, 2, . . . , d − k, b1 + d − k + 1, b2 + d − k + 2, . . . , bk + d} .
e and Γ likewise. Since Γ
e
We denote by ∆ the simplicial complex with facets {Φd (F ) : F ∈ ∆}
e
is a submulticomplex of ∆, it follows that Γ ⊂ ∆ and Ψ = (∆, Γ) is a relative complex with
dim Ψ = dim ∆ = dim Γ = d − 1.
e = (∆,
e Γ)
e be a (d − 1)-dimensional relative multicomplex and let Ψ be the
Proposition 8. Let Ψ
e
corresponding relative simplicial complex constructed above. Then any ordering of the faces of ∆
e Φd (F ) comes before Φd (F 0 ) whenever |F | < |F 0 |, yields a shelling
such that for every F, F 0 ∈ ∆,
order for ∆, Γ and Ψ.
Proof. It was shown in [BFS87] that any such order yields a shelling order for ∆ with restriction sets
R(σ) = σ \ {1, 2, . . . , d − k} = {s1 + d − k + 1, . . . , sk + d}

ON f - AND h-VECTORS OF RELATIVE SIMPLICIAL COMPLEXES

7

if σ = Φd ({s1 , . . . , sk }≤ ). We are left to prove that restricting this order to the facets of ∆ \ Γ yields
a shelling order for Ψ. It suffices to show that if σ is a facet of Ψ, i.e., a facet of ∆ not contained in
Γ, then R(σ) 6∈ Γ.
e such that σ = Φd (F ). We will show that any facet σ 0 of ∆
Let F = {s1 , . . . , sk }≤ be the face of ∆
which contains R := R(σ) does not belong to Γ, and since by construction facets of Γ are a subset
of the facets of ∆, neither does R.
e with σ 0 = Φd (F 0 ).
Let σ 0 be a facet of ∆ which contains R and let F 0 be the corresponding element of ∆
Observe that either σ 0 = σ or t = |F 0 | > |F | = k. Indeed, since {1, 2, . . . , d − k + 1} ⊆ σ 0 and
R ∩ {1, 2, . . . , d − k + 1} = ∅, R cannot be a subset of σ 0 if t < k. If t = k, then σ 0 ⊇ R implies
σ 0 = σ.
So, let us assume that t > k. Let G = {r1 , . . . , rt }≤ be the smallest t-multiset in M in reverse
lexicographic order such that τ = Φd (G) ⊇ R. Now τ = {1, . . . , d − t} ∪ S, with S = {d − t +
1 + r1 , . . . , d + rt }. As before, observe that R ∩ {1, . . . , d − t} = ∅. Since Φd preserves the reverse
lexicographic order on t-multisets, S is also minimal with respect to reverse lexicographic order.
Therefore the elements of R are the largest elements in S and
G = {1, . . . , 1, s1 , . . . , sk }≤ .
| {z }
t−k

e and Γ
e is a multicomplex, it follows that G ∈
e Since
Then F = {s1 , . . . , sk }≤ ⊆ G, and since F ∈
/Γ
/ Γ.
e is compressed and G is smaller than F 0 , F 0 also does not belong to Γ.
e This implies σ 6∈ Γ.
Γ

Proof of Theorem 2: (c) =⇒ (b) =⇒ (a). By Theorem 5, condition (c) guarantees the existence of
e with f -vector h. By Proposition 8, the construction above yields
a proper relative multicomplex Ψ
a fully shellable relative simplicial complex Ψ with h = h(Ψ). This proves (c) =⇒ (b). Theorem 2.5
for relative complexes in [Sta96] asserts that Ψ is fully Cohen–Macaulay and hence proves (b) =⇒
(a).

In order to prove the implication (a) =⇒ (c), we make use of the powerful machinery of Stanley–
Reisner modules. Let k be an infinite field. For a fixed n > 0, let S := k[x1 , . . . , xn ] be the polynomial
ring. For a simplicial complex ∆ ⊆ 2[n] , its Stanley–Reisner ideal is I∆ := hxτ : τ 6∈ ∆i and we
write k[∆] := S/I∆ for its Stanley–Reisner ring. If Γ ⊂ ∆ is a pair of simplicial complexes, then
k[∆]  k[Γ] and the Stanley–Reisner module of Ψ = (∆, Γ) is
M[Ψ] := ker(k[∆]  k[Γ]) = IΓ /I∆ .
This is a graded S-module of dimension d and Ψ is Cohen–Macaulay by definition when M[Ψ] is a
Cohen–Macaulay module over S. In particular, any choice of generic linear forms θ1 , . . . , θd ∈ S is a
regular sequence for M[Ψ] and
dimk (M[Ψ]/hθ1 , . . . , θd iM[Ψ])i = hi (Ψ) ,
for all i ≥ 0.
Proof of Theorem 2: (a) =⇒ (c). Let (∆, Γ) be a presentation of Ψ such that dim Γ = dim Ψ and ∆
and Γ are CM. Consider the short exact sequence
(3)

0 → M[Ψ] → k[∆] → k[Γ] → 0

of S-modules. Let θ ∈ S be a generic linear form. Tensoring (3) with S/θ yields
(4)

TorS1 (k[Γ], S/θ) → M[Ψ]/θM[Ψ] → k[∆]/θk[∆] → k[Γ]/θk[Γ] → 0

By resolving S/θ, it is easy to see that TorS1 (k[Γ], S/θ) = (0 :k[Γ] θ) = 0, so (4) is a short exact
sequence as well.

8

GIULIA CODENOTTI, LUKAS KATTHÄN, AND RAMAN SANYAL

1

2

1

2

1

2

5
4

3

4

3

4

3

Figure 1. The relative complexes of Example 2, Example 3, and Example 4. In each
case, Γ is drawn in bold.
By our choice of presentation, k[Γ] is Cohen–Macaulay and we may repeat the process for a full
regular sequence Θ = (θ1 , . . . , θd ) to arrive at
(5)

0 → M[Ψ]/ΘM[Ψ] → k[∆]/Θk[∆] → k[Γ]/Θk[Γ] → 0 .

Since Ψ is Cohen–Macaulay, the Hilbert series of M[Ψ]/ΘM[Ψ] is exactly the h-vector of Ψ and,
moreover, we can identify M[Ψ]/ΘM[Ψ] with a graded ideal in k[∆]/Θk[∆]. By a linear change
coordinates, this yields a pair of homogeneous ideals J∆ ⊂ JΓ ⊂ R := k[y1 , . . . , yn−d ] with difference
of Hilbert functions exactly h(Ψ). For any fixed term order , we denote by in (J∆ ), in (JΓ )
the corresponding initial ideals. The passage to initial ideals leave the Hilbert series invariant and
in (J∆ ) ⊆ in (JΓ ); c.f. [CLO15, Prop. 9.3.4]. The corresponding collections of standard monomials
e⊂∆
e with f -vector h and this completes the
are naturally identified with a pair of multicomplexes Γ
proof.

5. Cohen–Macaulay versus fully Cohen–Macaulay
Theorem 2 only addresses the characterization of h-vectors of fully CM relative complexes. By
definition, a relative simplicial complex Ψ is the set difference of a pair Γ ⊂ ∆ ⊆ 2[n] of simplicial
complexes. This presentation is by no means unique and it is natural to ask if in the case that Ψ
is Cohen–Macaulay, there are always CM complexes Γ0 ⊆ ∆0 ⊆ 2[n] of dimension dim Ψ such that
Ψ = ∆0 \ Γ0 . The following example shows that this is not the case.
Example 2. Let ∆ ⊂ 2[4] be the complete graph on 4 vertices, that is, the complex consisting of all
subsets of [4] of size at most 2. Let Γ ⊂ ∆ be a perfect matching, see Figure 1. Then ∆ \ Γ is the
relative complex consisting of 4 open edges. This is a shellable relative complex. It is easy to check
that on the fixed ground set [4], this is the only presentation with dim ∆ = dim Γ = 1 and hence Ψ
is not fully Cohen–Macaulay.
There are several possibilities to weaken the requirements on fully Cohen–Macaulay, for example,
the requirement that dim Γ = dim Ψ. The next example, however, shows that the characterization
of Theorem 2 then ceases to hold.
Example 3. Let ∆ ⊆ 2[4] be the 1-dimensional complex with facets {1, 2}, {2, 3}, {3, 4}, {1, 4} and
let Γ be the complex composed of the vertices of ∆. Then Ψ = (∆, Γ) is a relative complex isomorphic
to the relative complex of Example 2. Both ∆ and Γ are Cohen–Macaulay but dim Γ < dim Ψ. In
particular, Ψ is shellable with h-vector h := h(Ψ) = (0, 0, 4). However, h is not the f -vector of a
relative multicomplex on ground set [4 − 2], as any such (relative) multicomplex can have at most 3
faces of dimension 1.
Nevertheless, it is possible to remedy the problem exemplified in Example 2 by allowing more vertices.
Example 4. Let Ψ = (∆, Γ) be the relative complex of Example 2. Let ∆0 := ∆ ∪ {{i, 5} : i ∈ [4]}
be the graph-theoretic cone over ∆ and define Γ0 accordingly. Then ∆ \ Γ = ∆0 \ Γ0 and, since ∆0 and
Γ0 are connected graphs and hence shellable, this shows that Ψ is a fully Cohen–Macaulay relative
complex over the ground set [5].

ON f - AND h-VECTORS OF RELATIVE SIMPLICIAL COMPLEXES

9

The following result now shows that every Cohen–Macaulay relative complex is fully Cohen–Macaulay
if the ground set is sufficiently enlarged.
Theorem 9. Let Γ ⊂ ∆ ⊆ 2[n] be simplicial complexes, such that Ψ = (∆, Γ) is Cohen-Macaulay
of dimension d − 1. Let e be the depth of k[Γ]. Then there exist Γ0 ⊆ ∆0 ⊆ 2[n+d−e] , such that
∆0 \ Γ0 = ∆ \ Γ, and both ∆ and Γ are Cohen-Macaulay of dimension d − 1.
Proof. Let Γ1 be the (d − e)-fold cone over Γ and set ∆1 := ∆ ∪ Γ1 . Then ∆1 \ Γ1 = ∆ \ Γ1 . Further
note that k[Γ1 ] = k[Γ][y1 , . . . , yd−e ], where the yi are new variables. Thus, the depth of k[Γ1 ] is
d. Finally, we define ∆0 and Γ0 to be the (d − 1)-dimensional skeleta of ∆1 and Γ1 , respectively.
Again, ∆0 \ Γ0 = ∆ \ Γ and thus Ψ ∼
= (∆0 , Γ0 ). By [Hib91, Corollary 2.6], Γ0 is Cohen-Macaulay.
0
0
By assumption, Ψ = ∆ \ Γ is Cohen-Macaulay, and since dim Ψ = dim ∆0 = dim Γ0 , it follows
from [BH93, Prop 1.2.9] that ∆0 is also Cohen–Macaulay.

In the construction given in the course of the proof, the complexes ∆ and Γ occur as induced
subcomplexes. If we are to abandon this requirement, then our computations suggest that it suffices
to add a single new vertex. Based on this evidence, we offer the following conjecture.
Conjecture 1. Every Cohen–Macaulay relative complex Ψ on ground set [n] is a fully Cohen–
Macaulay relative complex on ground set [n + 1]. That is, for every (d − 1)-dimensional Cohen–
Macaulay relative complex Ψ = (∆, Γ) on ground set [n], there are Cohen–Macaulay simplicial complexes Γ0 ⊆ ∆0 ⊆ 2[n+1] of dimension d − 1, such that ∆ \ Γ = ∆0 \ Γ0 .
We also offer a more precise conjecture on how the complexes Γ0 ⊂ ∆0 can be obtained.
Conjecture 2. Let ∅ 6= Γ ( ∆ ⊂ 2[n] be two simplicial complexes, such that the relative complex
(∆, Γ) is Cohen–Macaulay of dimension d−1 over some field k. If ∆ and Γ have no common minimal
non-faces, then the depth of k[Γ] is at least d − 1.
To see that Conjecture 2 implies Conjecture 1, let Ψ = (∆, Γ) be a given presentation. We can
assume that ∆ and Γ have no minimal non-faces in common. Conjecture 2 then assures us that k[Γ]
has depth d − 1 and Theorem 9 yields Conjecture 1.
Instead of fixing the ground set, we may instead consider the dimensions of the minimal faces in
Ψ = (∆, Γ). For a sequence α = (α1 , α2 , α3 , . . . ) of numbers and i ≥ 0 we set
E i α := (0, . . . , 0, α1 , α2 , α3 , . . . ) .
| {z }
i

Theorem 10. For a vector h = (h0 , . . . , hd ) ∈ Zd+1
≥0 and numbers a1 , . . . , ar ∈ Z≥0 , the following are
equivalent:
(i) h = h(∆, Γ) for a shellable relative complex (∆, Γ), whose minimal faces have cardinalities
a1 , . . . , ar ;
(ii) h = h(∆, Γ) for a Cohen-Macaulay relative complex (∆, Γ), whose minimal faces have cardinalities a1 , . . . , ar ;
(iii) h is the h-vector of a graded Cohen-Macaulay module (over some polynomial ring), whose
generators have the degrees a1 , . . . , ar .
(iv) There exist M-sequences ν1 , . . . , νr such that
h = E a1 ν1 + E a2 ν2 + · · · + E ar νr .
The implications (i) ⇒ (ii) ⇒ (iii) are clear, and (iii) ⇒ (iv) is Proposition 5.2 of [Sta87]. In loc. cit.
Anders Björner asked if the implication (iv) ⇒ (iii) also holds.
Proof. We only need to show (iv) ⇒ (i). For each i, we can find a shellable simplicial complex ∆i
whose h-vector is νi . Further, let vi1 , . . . , viai be new vertices and let Ψi be the relative complex with

10

GIULIA CODENOTTI, LUKAS KATTHÄN, AND RAMAN SANYAL

faces {F ∪ {vi1 , . . . , viai } : f ∈ ∆i }. It is clear that any shelling order on ∆i yields a shelling on Ψi ,
and that h(Ψi ) = E ai νi . Finally, by taking cones if necessary, we may assume that all the Φi have
the same dimension. Then the disjoint union of the Ψi is the desired shellable relative complex. 
References
[AS16]

K. A. Adiprasito and R. Sanyal, Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski
sums, Publ. Math. Inst. Hautes Études Sci. 124 (2016), 99–163.
[BFS87]
A. Björner, P. Frankl, and R. Stanley, The number of faces of balanced Cohen-Macaulay complexes and a
generalized Macaulay theorem, Combinatorica 7 (1987), no. 1, 23–34.
[BH93]
W. Bruns and J. Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics, vol. 39,
Cambridge University Press, Cambridge, 1993.
[Bjö95]
A. Björner, Topological methods, Handbook of combinatorics, Vol. 1, 2, Elsevier, Amsterdam, 1995,
pp. 1819–1872.
[BK88]
A. Björner and G. Kalai, An extended Euler-Poincaré theorem, Acta Math. 161 (1988), no. 3-4, 279–303.
[BS]
M. Beck and R. Sanyal, Combinatorial reciprocity theorems, Book in preparation. Preliminary version
available at http://math.sfsu.edu/beck/crt.html.
[CLO15]
D. A. Cox, J. Little, and D. O’Shea, Ideals, varieties, and algorithms, fourth ed., Undergraduate Texts in
Mathematics, Springer, 2015.
[DGKM16] A. M. Duval, B. Goeckner, C. J. Klivans, and J. L. Martin, A non-partitionable Cohen-Macaulay simplicial
complex, Adv. Math. 299 (2016), 381–395.
[Duv99]
A. M. Duval, On f -vectors and relative homology, J. Algebraic Combin. 9 (1999), no. 3, 215–232.
[GK78]
C. Greene and D. J. Kleitman, Proof techniques in the theory of finite sets, Studies in combinatorics, MAA
Stud. Math., vol. 17, Math. Assoc. America, Washington, D.C., 1978, pp. 22–79.
[Hib91]
T. Hibi, Quotient algebras of Stanley-Reisner rings and local cohomology, Journal of Algebra 140 (1991),
no. 2, 336 – 343.
[Kat68]
G. Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq., Tihany, 1966), Academic Press, New
York, 1968, pp. 187–207.
[Kru63]
J. B. Kruskal, The number of simplices in a complex, Mathematical optimization techniques, Univ. of
California Press, Berkeley, Calif., 1963, pp. 251–278.
[Mac27]
F. S. Macaulay, Some Properties of Enumeration in the Theory of Modular Systems, Proc. London Math.
Soc. (2) 26 (1927), 531–555.
[Sta77]
R. P. Stanley, Cohen-Macaulay complexes, Higher combinatorics (Proc. NATO Advanced Study Inst.,
Berlin, 1976), Reidel, Dordrecht, 1977, pp. 51–62.
[Sta87]
, Generalized H-vectors, intersection cohomology of toric varieties, and related results, Commutative
algebra and combinatorics (Kyoto, 1985), Adv. Stud. Pure Math., vol. 11, North-Holland, Amsterdam,
1987, pp. 187–213.
, Combinatorics and commutative algebra, second ed., Progress in Mathematics, vol. 41, Birkhäuser
[Sta96]
Boston Inc., Boston, MA, 1996.
Fachbereich Mathematik und Informatik, Freie Universität Berlin, Berlin, Germany
E-mail address: codenotti@math.fu-berlin.de
School of Mathematics, University of Minnesota, Minneapolis, MN 55455, USA
E-mail address: katth001@umn.edu
Institut für Mathematik, Goethe-Universität Frankfurt, Germany
E-mail address: sanyal@math.uni-frankfurt.de

