h-VECTORS OF MATROID COMPLEXES

arXiv:1212.3226v2 [math.AC] 14 Dec 2012

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

Abstract. In this paper we partition in classes the set of matroids of fixed dimension on a
fixed vertex set. In each class we identify two special matroids, respectively with minimal and
maximal h-vector in that class. Such extremal matroids also satisfy a long-standing conjecture
of Stanley. As a byproduct of this theory we establish Stanley’s conjecture in various cases, for
example the case of Cohen-Macaulay type less than or equal to 3.

Introduction
In 1977 Stanley conjectured that the h-vectors of matroids are pure O-sequences [19, p.59],
that is they are h-vectors of Artinian monomial level algebras or, equivalently, f -vectors of pure
order ideals. Ever since, the h-vectors of matroids have been in the focus of many researchers
(see [7, 8, 3, 10, 23, 18]). Pure O-sequences themselves have attracted a lot of attention as well,
quite a few conjectures being made regarding their shape ([1] gives an overview of the topic).
Although several researchers have approached Stanley’s conjecture, to our knowledge only very
specific cases have been proven. The case of cographic matroids was proven in [3, 11], that of
lattice path matroids in [17] and more generally the one of cotransversal matroids in [14]. Low
rank and degree situations were recently investigated in [21, 22, 5].
In the present paper we prove Stanley’s conjecture in several cases, which appear in every
rank and codimension. As a particular case, we obtain the conjecture for all matroid complexes
of Cohen-Macaulay type less than or equal to 3. For any positive integers n and d, we divide
the (d − 1)-dimensional matroids on n vertices in different classes, which are indexed by the
partitions of n with length at least d. For each class we build the set of all possible h-vectors of
the duals of the matroids in the respective class. We then identify two special matroids whose
duals have minimal, respectively maximal h-vectors in that set. For all these extremal matroids
we prove in a constructive way that Stanley’s conjecture holds.
Our approach passes via an equivalent phrasing of Stanley’s conjecture. The h-vector of a
matroid ∆ is defined as the h-vector of the corresponding Stanley-Reisner ring and we will
denote it by h∆ . To a simplicial complex in general, apart from the Stanley-Reisner ideal I∆ ,
one can associate its vertex cover ideal J(∆). We will denote the h-vector of the quotient ring
of J(∆) by h∆ . If we denote by ∆c the dual of ∆ (that is the simplicial complex generated by
the complements of the facets in the vertex set), we have that
J(∆c ) = I∆

and

c

h∆ = h∆ .

A classical theorem of matroid theory says that ∆ is a matroid if and only if ∆c is a matroid.
This implies the following equivalent formulation of Stanley’s conjecture:
Conjecture (Stanley). For any matroid ∆, the vector h∆ is a pure O-sequence.
Let us summarize the contents of the paper. Section 1 is mainly devoted to preliminary results
and establishing the notation. Nevertheless, we show in Corollary 1.4 an equality involving the
cover ideals of certain matroid complexes. This equality supplies the exact sequence (1), which
will be a crucial tool throughout the paper. The existence of this exact sequence depends heavily
Date: February 2, 2018.
2010 Mathematics Subject Classification. Primary: 52B05, 05E40; Secondary: 13D40, 13E10, 13F55.
Key words and phrases. Stanley’s Conjecture and Matroid complex and h-vector and pure O-sequence.
1

2

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

on the properties of matroids. In Remark 1.10 we also present a counterexample to the Interval
Conjecture for Pure O-sequences formulated by Boij et al. in [1].
In Section 2, we first provide some structural results for matroid complexes. We show that
the 1-skeleton of a matroid is a complete p-partite graph. The division of the matroids into
classes will be done in correspondence with these partitions of the vertex set. In each class we
then define d − 1 matroids: ∆t (d, p, a), for t = 0, . . . , d − 2, where a is the partition of n. All
these matroids are representable over fields with “enough” elements, and in most cases they are
neither graphic nor transversal. We will call ∆0 (d, p, a) complete p-partite matroids. These are
a simultaneous generalization of both uniform and partition matroids.
Later on in this section, we attach to each matroid ∆ another matroid si∆, named simplified
matroid, of the same dimension but on less vertices. The simplified matroid reflects many
properties of the original matroid. For example, the total Betti numbers of J(∆) and J(si∆) are
the same (Proposition 2.8). In Proposition 2.10 we provide a formula which computes h∆ for
1-dimensional matroids. It turns out that the set of h-vectors of matroid complexes of the type
(1, 2, h2 , . . . , hs ) coincides with the set of pure O-sequences of the form (1, 2, h2 , . . . , hs ).
In Section 3 we prove the conjecture of Stanley in various instances. In Theorem 3.5 we show
that h∆ is a pure O-sequence whenever ∆ is a (d − 1)-dimensional complete p-partite matroid
for some p ≥ d. Using Theorem 3.5, we prove the more general statement that h∆t (d,p,a) is a
pure O-sequence for all t = 0, . . . , d − 2 (Theorem 3.7).
In Section 4, for any partition a of n with p ≥ d parts, we denote by M(d, p, a) the set of
(d − 1)-matroids on n vertices, whose 1-skeleton is p-partite and the cardinalities of the partition
sets correspond to a. By the results of Section 2, every matroid belongs to exactly one of these
sets. In Theorems 4.3 and 4.6, we show that
h∆d−2 (d,p,a) ≤ h∆ ≤ h∆0 (d,p,a), ∀ ∆ ∈ M(d, p, a).
A priori the existence of a matroid in M(d, p, a) with minimal h-vector is not clear at all. Indeed,
a striking consequence is the validity of Stanley’s conjecture whenever the Cohen-Macaulay type
of S/I∆ is less than or equal to three. In other words, we establish Stanley conjecture for all
the h-vectors of type (h0 , h1 , . . . , hs ) with hs ≤ 3.
Acknowledgement. We would like to thank Thomas Kahle for helpful discussions that led to
improvements of the paper.
1. Preliminaries
In this section we will recall most of the algebraic and combinatorial notions that we will use
throughout the paper. For general aspects on the topics presented below we refer the reader to
the books of Stanley [20], of Bruns and Herzog [2] and of Oxley [15].
For a positive integer n denote by [n] the set {1, . . . , n}. A simplicial complex ∆ on [n] is a
collection of subsets
of [n] such that F ∈ ∆ and F ′ ⊂ F imply F ′ ∈ ∆. Notice that we are not
S
requiring
that F ∈∆ F = [n], therefore ∆ can be viewed as a simplicial complex on any overset
S
of F ∈∆ F . Each element F ∈ ∆ is called a face of ∆. The dimension of a face F is |F | − 1 and
the dimension of ∆ is max{dim F : F ∈ ∆}. A maximal face of ∆ with respect to inclusion is
called a facet and we will denote by F(∆) the set of facets of ∆. A simplicial complex is called
pure if all facets have the same cardinality. We call a vertex v a cone point of ∆ if v ∈ F for
any F ∈ F(∆). If F1 , . . . , Fm are subsets of [n], then we denote by hF1 , . . . , Fm i the smallest
simplicial complex on [n] containing them. Explicitly:
hF1 , . . . , Fm i = {F ⊂ [n] : ∃ i ∈ {1, . . . , m} : F ⊂ Fi }.
We say that F1 , . . . , Fm generate the simplicial complex hF1 , . . . , Fm i. Clearly every simplicial
complex is generated by its set of facets. For any face F the link of F in ∆ is the following
simplicial complex:
link∆ F = {F ′ ∈ ∆ : F ′ ∪ F ∈ ∆ and F ′ ∩ F = ∅}.

h-VECTORS OF MATROID COMPLEXES

3

For a set of vertices W ⊂ [n], the restriction of ∆ to W is the following subcomplex of ∆:
∆|W = {F ∈ ∆ : F ⊂ W }.
The subcomplex ∆|W is also called the subcomplex of ∆ induced by the vertex set W . If F is
a face of ∆, then the face deletion of F in ∆ is ∆ \ F = {F ′ ∈ ∆ : F * F ′ }. Whenever F is
a 0-dimensional face {v} we will just write ∆ \ v for the face deletion of {v} and link∆ v for the
link of {v}. Notice that ∆ \ v = ∆|[n]\{v} for all v ∈ [n]. The dual complex of ∆ is the simplicial
complex ∆c on [n] with facets
F(∆c ) = {[n] \ F : F ∈ F(∆)}.
For any integer 0 ≤ k ≤ dim ∆, the k-skeleton of ∆ is defined as the simplicial complex with
facet set {F ∈ ∆ : dim F = k}.
We will now associate to a simplicial complex two square-free monomial ideals. We will
then see how these ideals are related via the dual complex. Denote by S = k[x1 , . . . , xn ] the
polynomial ring in n variables over a field k. For each subset F ⊂ [n] define the monomial xF
and the prime ideal PF as follows:
Y
xF =
xi ,
i∈F

PF

= (xi : i ∈ F ).

The Stanley-Reisner ideal of ∆ is the ideal I∆ of S generated by the square-free monomials xF ,
with F ∈
/ ∆. In particular we have
I∆ = (xF : F is a minimal nonface of ∆).
The second square-free monomial ideal we can associate to ∆ is the cover ideal of ∆, namely
\
J(∆) =
PF .
F ∈F (∆)

The name “cover ideal” comes from the following fact. A collection of vertices A ⊂ [n] is called
a vertex cover of ∆ if A ∩ F 6= ∅ for any F ∈ F(∆). A vertex cover A is called basic if no proper
subset of A is again a vertex cover. It is easy to check that we have
J(∆) = (xA : A is a basic vertex cover of ∆).
It is a well known fact that the prime decomposition of the Stanley-Reisner ideal is
\
I∆ =
P[n]\F .
F ∈F (∆)

The following equality, which follows directly from the definition, will be very important for the
approach of this paper:
J(∆) = I∆c .
We denote by k[∆] = S/I∆ the Stanley-Reisner ring of ∆. Let hk[∆] = (h0 , h1 , . . . , hs ) be its
h-vector. If HSk[∆] (t) is the Hilbert series of k[∆], then we have
HSk[∆] (t) =

h0 + h1 t + . . . + hs ts
,
(1 − t)d

where hs 6= 0 and d = dim k[∆] = dim ∆ + 1.
In the classical terminology, the h-vector of a simplicial complex is the h-vector of its StanleyReisner ring. As we will mainly deal with cover ideals, in order to avoid the over-use of the word
dual, we will fix the following notation and terminology.
Notation 1.1. Let ∆ be any simplicial complex.
1. We denote the h-vector of k[∆] by h∆ .
2. We denote the h-vector of S/J(∆) by h∆ .
3. We will refer throughout this paper to h∆ as the h-vector of ∆.

4

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

Notice that we have the correspondence h∆ = h∆c .
For a (d − 1)-dimensional simplicial complex ∆ on [n] such that S/J(∆) is Cohen-Macaulay,
we denote by type(∆) the last total Betti number in the minimal free resolution of S/J(∆),
namely
type(∆) = βd (S/J(∆)) = dimk TorSd (S/J(∆), k).
Matroid theory was born out of the need to study the concept of dependence in an abstract
way. In this paper we will view matroids as simplicial complexes whose faces correspond to the
independent sets. A characteristic of matroids is that they admit many different but equivalent
definitions (see [15] and [20, Chapter III.3]). We present here three of them.
Definition 1.2. A simplicial complex ∆ is called a matroid complex (or just matroid) if one of
the following equivalent properties hold:
1. The augmentation axiom: For any two faces F, G ∈ ∆ with |F | < |G| there exists i ∈ G
such that F ∪ {i} ∈ ∆.
2. The exchange property: For any two facets F, G ∈ F(∆) and for any i ∈ F there exists
a j ∈ G such that (F \ {i}) ∪ {j} ∈ ∆.
3. For any subset W ⊂ [n] the restriction ∆|W is pure.
A basic result in matroid theory that we will exploit a lot is the following:
Theorem 1.3 ([15]Theorem 2.1.1). A simplicial complex ∆ on [n] is a matroid if and only if
∆c is a matroid.
An algebraic characterization of matroid complexes has been given in [13] and [24], namely a
simplicial complex ∆ is a matroid iff all the symbolic powers of I∆ are Cohen-Macaulay. Another
algebraic property that will be important for us (even if it does not characterize matroids) is
the following: the Stanley-Reisner ring of a matroid is level ([20, Chapter III, Theorem 3.4]).
This means that k[∆] is Cohen-Macaulay and the socle of its Artinian reduction lies in exactly
one degree. A prototype of level algebras are the Gorenstein algebras, which correspond to socle
dimension 1. An important consequence of S/J(∆) being level is that the type can be expressed
only in terms of the last entry of the h-vector, namely
type(∆) = h∆ (s)

where s = max{i : h∆ (i) 6= 0}.

The following lemma is important because it provides a recursive formula for the h-vectors.
This formula will be a main ingredient in many of our proofs. The lemma itself can also be
interpreted from a liaison-theoretical point of view, namely it is easy to check that the ideal
relation provides a basic double link.
Lemma 1.4. If ∆ is a matroid on [n] and v ∈ ∆ is a vertex that is not a cone point, then
J(∆) = xv J(∆ \ v) + J(link∆ v).
Proof. We will first make a general observation. Let Γ be a simplicial complex on [n] and
consider Γ \ n and linkΓ n as simplicial complexes on [n − 1]. It is straightforward to show that,
if Γ \ n is pure and of the same dimension as Γ, then (Γ \ n)c = linkΓc n.
We may obviously assume that v = n. Since ∆ is a matroid, ∆ \ n is pure. Since n is not a
cone point, it has the same dimension as ∆. Therefore, by the above observation we have
(∆ \ n)c = link∆c n.
As we assumed that n ∈ ∆, we have that n is not a cone point of ∆c . By Theorem 1.3 and the
general observation we obtain also that
∆c \ n = ((∆c \ n)c )c = (link(∆c )c n)c = (link∆ n)c .
For all simplicial complexes Γ on [n] we have the following equality for Stanley-Reisner ideals:
IΓ = xn IlinkΓ n + IΓ\n .
Exploiting it for Γ = ∆c , together with I∆c = J(∆) and all the above observations, we conclude.


h-VECTORS OF MATROID COMPLEXES

5

Remark 1.5. Whereas the equality I∆ = xn Ilink∆ n +I∆\n holds true for any simplicial complex,
the equality J(∆) = xv J(∆ \ v) + J(link∆ v) depends strongly on the fact that ∆ is a matroid.
For instance, Lemma 1.4 already fails for any vertex of a path of length three.
Remark 1.6. From the point of view of Gorenstein liaison, Lemma 1.4 implies that the ideals
J(∆) can be linked to a complete intersection. A more general statement in this direction has
been proven by Nagel and Römer in [16].
Remark 1.7. Lemma 1.4 gives rise to the exact sequence
0 −→ J(link∆ v)(−1) −→ J(∆ \ v)(−1) ⊕ J(link∆ v) −→ J(∆) −→ 0.
The above exact sequence yields the following relation for the Hilbert functions:
HFJ(∆) (k) = HFJ(∆\v) (k − 1) + HFJ(link∆ v) (k) − HFJ(link∆ v) (k − 1)

∀ k ∈ Z,

which in turn yields
HFS/J(∆) (k) = HFS/J(∆\v) (k − 1) + HFS/J(link∆ v) (k) − HFS/J(link∆ v) (k − 1)

∀ k ∈ Z.

Eventually, taking differences, for every matroid ∆ and every v ∈ ∆ that is not a cone point we
obtain
h∆ (k) = h∆\v (k − 1) + hlink∆ v (k)

(1)

∀ k ∈ Z.

Formula (1) will be crucial throughout the paper.
An order ideal is a finite collection Γ of monomials of some standard graded polynomial ring,
such that M ∈ Γ and N divides M imply N ∈ Γ. The partial order given by the divisibility
of monomials gives Γ a poset structure. An order ideal is called pure if all maximal monomials
have the same degree. To every order ideal Γ we associate its f -vector f (Γ) = (f0 (Γ), . . . , fs (Γ)),
where for every i = 0, . . . , d we have
fi (Γ) = |{M ∈ Γ : deg(M ) = i}|.
A pure O-sequence is a vector h = (h0 , . . . , hs ) that can be obtained as the f -vector of some
pure order ideal.
Remark 1.8. Pure O-sequences can also be presented as the h-vectors of Artinian monomial
level algebras, i.e. Artinian level algebras A which are isomorphic to R/I for some polynomial
ring R and some monomial ideal I ⊂ R. It is very easy to see that, in this situation, if
A is Gorenstein then I is forced to be a complete intersection. So the pure O-sequences of
type (h0 , h1 , . . . , hs−1 , 1) are well understood: they are h-vectors of complete intersections. In
particular, it emerges that pure O-sequences are much more special than h-vectors of level
algebras in general.
However, already a characterization of pure O-sequences of the type (h0 , h1 , . . . , hs−1 , 2), i.e.
when the Artinian monomial level algebra A has Cohen-Macaulay type 2, is not known (see [1]).
In [19] Stanley phrased his conjecture in terms of the h-vector of the Stanley-Reisner ring.
By Theorem 1.3 an equivalent statement is the following:
Conjecture 1.9 (Stanley). If ∆ is a matroid, then the h-vector of S/J(∆) is a pure O-sequence.
Conjecture 1.9 is known for some families; we list here the most general of them.
1.
2.
3.
4.
5.

When S/J(∆) is Gorenstein, see [21, Theorem 4.4.10].
When h∆ = (1, h1 , h2 , h3 ), see [21] and [5].
When ∆ is a graphic matroid, see [11].
When ∆ is a transversal matroid, see [14].
Whenthe dual 
of ∆ is a paving matroid, see [12]. This corresponds to the case in which
v+i−1
hi =
for all i < s, where v is the number of 0-dimensional faces of ∆c .
i

6

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

6. When h∆ = (1, 2, h2 , . . . , hs ). Indeed, one can see by the Hilbert-Burch theorem that,
in the height 2 case, pure O-sequences coincide with h-vectors of level algebras (see [1,
Proposition 4.5] for the precise proof), so one can deduce the validity of the conjecture
in this case by [20, Chapter III, Theorem 3.4].
Computational experiments using the computer algebra system CoCoa [4] were an important
part in the preparation of this work. In our investigation, we found a counterexample to the
Interval Conjecture for Pure O-sequences (see [1]):
Remark 1.10. One can check that the vectors (1, 4, 10, 13, 12, 9, 3) and (1, 4, 10, 13, 14, 9, 3) are
pure O-sequences. Indeed, the order ideals are generated by {x3 y 2 z, x3 yts 2, x3 z 2 t}, respectively
by {x4 y 2 , x3 yzt, x2 z 2 t2 }. Looking at all possible choices of three monomials of degree 6 in 4
variables, it is possible to compute all the pure O-sequences of the form (1, 4, h2 , . . . , h5 , 3).
Checking the obtained list, one can realize that (1, 4, 10, 13, 13, 9, 3) does not appear among the
pure O-sequences, a contradiction to the above-mentioned conjecture.
2. The structure of matroids
In this paper we will stratify the set of matroids of fixed dimension and on a fixed vertex set
in terms of partitions of the vertex set. To this aim, in this section we will prove some technical
facts. Most of these are well known facts for matroid theory specialists, however we consider it
convenient to provide proofs as well. We will then present the simplified matroid associated to
any given matroid. This matroid has only trivial parallel classes, but important information,
such as the total Betti numbers βi (S/J(∆)), is preserved. We conclude the section presenting a
formula that computes the h-vector of a codimension two Stanley-Reisner ring of a matroid.
From now on, unless otherwise stated, we will consider simplicial complexes ∆ on [n] with
the property that v ∈ ∆ for all v ∈ [n]. Notice that the number of vertices not belonging to ∆
does not influence h∆ , so
S this is no restriction in terms of our goals. This assumption can be
also expressed as [n] = F ∈∆ F and if ∆ is a (d − 1)-dimensional matroid on [n], a remark in
[20, p. 94] implies that
n − d = max{i : h∆ (i) 6= 0}.
The following easy remark is the starting point for many of the following technical results.
Remark 2.1. If ∆ is a 1-dimensional simplicial complex on [n], then ∆ is a matroid if and only
if for any v, w ∈ [n] with {v, w} ∈
/ ∆ we have that link∆ (v) = link∆ (w).
One-dimensional simplicial complexes can be viewed as graphs on the same vertex set; the
edges are the faces of dimension one. For this reason we will switch between graph and simplicial
complex whenever we find ourselves in this case. Let us recall that a graph is called a complete
p-partite graph if and only if its vertex set can be partitioned into p disjoint nonempty sets
A1 , . . . , Ap such that {v, w} is an edge if and only if v and w lie in different sets of the partition.
The following proposition shows that one-dimensional matroids and complete p-partite graphs
are actually the same thing.
Proposition 2.2. If ∆ is a 1-dimensional matroid, then ∆ is a complete p-partite graph, for
some integer p ≥ 2.
Proof. We will proceed by induction on n, the number of vertices. Assume that n ≥ 2, choose v
a vertex of ∆ and consider the set Av = {w ∈ ∆ : {v, w} ∈
/ ∆}. As ∆ is a matroid, we have by
Remark 2.1 that link∆ v = link∆ w for any w ∈ Av . This implies that Av is an independent set
of vertices. Clearly link∆ v is a 0-dimensional simplicial complex whose faces correspond to the
elements in [n] \ Av . Moreover, as one can check by definition, the restriction ∆|[n]\Av is also a
matroid.
If dim ∆|[n]\Av = 1, we have by induction that ∆|[n]\Av is a complete p-partite graph, with ppartition of the vertex set A1 ∪. . .∪Ap . In this case it follows that ∆ is a complete (p+1)-partite
graph with partition [n] = Av ∪ A1 ∪ . . . ∪ Ap .

h-VECTORS OF MATROID COMPLEXES

7

If dim ∆|[n]\Av = 0 then [n] \ Av is an independent set of vertices, so ∆ is a complete bipartite
graph with bipartition [n] = Av ∪ ([n] \ Av ).

The next corollary gives a stratification of the set of all (d − 1)-dimensional matroids on [n]
that will be crucial throughout this work. Clearly, the k-skeleton of a matroid is again a matroid,
so we have the following.
Corollary 2.3. Let ∆ be a simplicial complex. If ∆ is a matroid, then there exists a positive
integer p ≥ 2 such that the 1-skeleton of ∆ is a complete p-partite graph.
Before showing the next technical lemmas let us fix more notation. From now on, exploiting
Corollary 2.3, ∆ will be a (d − 1)-dimensional matroid on [n], with p-partition of its 1-skeleton
A1 , . . . , Ap . We will call the sets of independent vertices given by the p-partition parallel classes.
Whenever necessary we will denote the vertices of a given parallel class as follows
Ai = {vi,1 , vi,2 , . . . , vi,ai }.
For any integer r ∈ {1, . . . , p} and any indices 1 ≤ i1 < . . . < ir ≤ p we denote by ∆i1 ,...,ir the
restriction of ∆ to the vertex set Ai1 ∪ . . . ∪ Air . We call ∆i1 ,...,ir the restriction of ∆ to the
parallel classes Ai1 , . . . , Air .
Lemma 2.4. If for r ≤ d parallel classes Ai1 , . . . , Air , with 1 ≤ i1 < . . . < ir ≤ p, there exist
r vertices vij ∈ Aij such that {vi1 , . . . , vir } ∈ ∆, then for any r vertices uij ∈ Aij we have that
{ui1 , . . . , uir } ∈ ∆.
Proof. We may assume without loss of generality that ij = j, for j = 1, . . . , r. Choose now
r vertices uj ∈ Aj and assume that {u1 , . . . , ur } ∈
/ ∆. Let s < r be the maximum size of a
subset of {u1 , . . . , ur } that belongs to ∆. Again we may assume that actually {u1 , . . . , us } ∈ ∆.
The simplicial complex ∆1,...,r is a matroid. Since {v1 , . . . , vr } ∈ ∆1,...,r and the 1-skeleton of
∆1,...,r is complete r-partite, we have dim ∆1,...,r = r − 1. As a matroid is pure, we have that
us+1 belongs to some (r − 1)-dimensional facet F of ∆1,...,r . Notice that, by the r-partition of
∆1,...,r ’s 1-skeleton, the facet F has to contain exactly one vertex from each parallel class. By
the augmentation axiom, we know that there exist r − s vertices w1 , . . . , wr−s ∈ F such that
{u1 , . . . , us , w1 , . . . , wr−s } ∈ ∆1,...,r . As a face cannot contain two vertices from the same parallel
class, we obtain that wi = us+1 for some 1 ≤ i ≤ r − s. In particular {u1 , . . . , us , us+1 } ∈ ∆, a
contradiction to the maximality of s.

Lemma 2.5. Let Ai be one of the parallel classes of ∆ and let v, w ∈ Ai . Then
link∆ v = link∆ w.
Proof. Choose {a1 , . . . , ad−1 } ∈ link∆ v. The restriction ∆|{v,w,a1 ,...,ad−1 } is a (d − 1)-dimensional
pure complex. As {v, w} ∈
/ ∆ we obtain that {a1 , . . . , ad−1 , w} ∈ ∆|{v,w,a1 ,...,ad−1 } and thus
{a1 , . . . , ad−1 } ∈ link∆ w.

Exploiting the results of Lemma 2.4 and Lemma 2.5 we will simplify notation in the following
way. We will write Ai1 . . . Air ∈ ∆ if there exist vertices vij ∈ Aij for all j = 1, . . . , r such that
{vi1 , . . . , vir } ∈ ∆. By Lemma 2.4 this holds for any choice of r vertices, one in each parallel
class. As by Lemma 2.5 the link of all the vertices in one parallel class is the same, we will
denote by link∆ Ai the link of some vertex v ∈ Ai . These two lemmas lead us to the following
definition (see [15, p. 49] for the classical matroid-theoretical definition).
Definition 2.6. Let ∆ be a simplicial complex with complete p-partite 1-skeleton, satisfying
Lemma 2.4. Let A1 ∪ . . . ∪ Ap be the p-partition and choose for each i = 1, . . . , p a vertex
vi,1 ∈ Ai . We define the associated simplified complex as
si

∆ = ∆|{v1,1 ,...,vp,1 } .

We will call a parallel class of ∆ a cone class if the corresponding vertex in si∆ is a cone point
of si∆. This is clearly equivalent to every facet of ∆ containing a vertex of that parallel class.

8

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

Remark 2.7. Let ∆ be a simplicial complex with complete p-partite 1-skeleton. Then, using
Lemma 2.4, we have
∆ is a matroid ⇐⇒ si∆ is a matroid.
The next proposition shows the close relation between a matroid ∆ and si∆.
Proposition 2.8. Given a matroid ∆ on [n], we have βi (S/J(∆)) = βi (S/J(si∆)) for all i. In
particular, type(∆) = type(si∆).
Proof. Set R = k[y1 , . . . , yp ], and consider the k-algebra homomorphism
φ : R −→ S
Q
yi 7→
j∈Ai xj = mi

One can check that φ(J(si∆))S = J(∆). Moreover it is obvious that m1 , . . . , mp form a regular
sequence of S, so by a theorem of Hartshorne ([6, Proposition 1]) S is a flat R-module via φ. So,
if F• is a minimal free resolution of R/J(si∆) over R, then it follows that F• ⊗R S is a minimal
free resolution of S/J(∆) over S. Therefore we may conclude.

Remark 2.9. With the notation of Proposition 2.8, notice that φ allows also to recover the
graded Betti numbers of J(∆) from those of J(si∆). Provided that the partition of the 1-skeleton
of ∆ is known, it is enough to consider the natural Zp -grading both on R and on S. The Zp grading on S is given by the p-partition.
We will conclude this section with a first application of Equation (1). We will find a formula
the h-vectors h∆ where ∆ is a 1-dimensional matroid. By Theorem 1.3, this is equivalent to
describing the h-vectors of k[∆], where ∆ is a matroid such that its Stanley-Reisner ideal has
height 2.
By Proposition 2.2, a 1-dimensional matroid ∆ is actually a complete p-partite graph on n
vertices. For all k = 1, . . . , n − 1, let us set
ck (∆) = |{i ∈ {1, . . . , p} : |Ai | ≥ k}| − 1.
Proposition 2.10. Let ∆ be a 1-dimensional matroid on [n]. For all k = 0, . . . , n − 2, we have
∆

h (k) =

n−k−1
X

ci (∆).

i=1

Proof. Let us choose a vertex v ∈ Ap . Clearly, the cover ideal of the link of v is the principal
ideal

 Y
xi .
J(link∆ v) =
i∈[n]\Ap

In particular, we have
h

link∆ v

(i) =



1 if 0 ≤ i < n − |Ap |,
0 otherwise.

The partition sets of the matroid ∆ \ v are A1 , A2 , . . . , Ap−1 , Ap \ {v}, so we have

ck (∆)
if k 6= |Ap |,
ck (∆ \ v) =
ck (∆) − 1 if k = |Ap |.
By induction we have
h∆\v (k) =

n−k−2
X

ci (∆ \ v),

i=1

for all k = 0, . . . , n − 3. On the other side, by (1) we have
h∆ (k) = h∆\v (k − 1) + hlink∆ v (k),

∀ k = 0, . . . , n − 1.

h-VECTORS OF MATROID COMPLEXES

9

Therefore,

h∆ (k) =

 Pn−k−1
Pn−k−1

ci (∆) − 1 + hlink∆ v (k) =
ci (∆) if k ≤ n − |Ap | − 1,

i=1
i=1

 Pn−k−1
i=1

ci (∆) + hlink∆ v (k)

=

Pn−k−1
i=1

ci (∆) otherwise.



Corollary 2.11. For a sequence h = (1, 2, h3 , . . . , hs ), the following are equivalent:
(i)
(ii)
(iii)
(iv)
(v)

There is a matroid ∆ such that h is the h-vector of k[∆].
There is a matroid ∆ such that h is the h-vector of S/J(∆).
h is a pure O-sequence.
h is the h-vector of a level algebra.
hi+1 ≤ 2hi + hi−1 for all i = 1, . . . , s.

Proof. The equivalence between (i) and (ii) follows by Theorem 1.3, whereas (iii) is equivalent
to (iv) by the Hilbert-Burch theorem. The equivalence between (iv) and (v) was shown by
Iarrobino in [9]. As S/J(∆) is level, and thus (ii) implies (iv), we just need to prove that (v)
implies (ii) and this follows easily from Proposition 2.10.

Corollary 2.12. If ∆ is a 1-dimensional matroid, then type(∆) = p − 1, where ∆ is p-partite.

3. Stanley’s Conjecture
The main result of this section is Theorem 3.7, in which we prove that Stanley’s conjecture
holds for certain matroids which we identify in a natural way. The first discussion of this section
and Theorem 3.5 are particular cases of the main result. They are the starting point of the
inductive procedure in the proof of Theorem 3.7. For a better understanding of the construction
which we present here, we will start with a closer look at an already known case of Stanley’s
Conjecture 1.9, namely the codimension two case. In this first part we will concentrate on examples which hopefully provide the necessary intuition for the more technical proofs.
Consider a 1-dimensional matroid ∆ on [n], thus by Proposition 2.2 it is a complete p-partite
graph. Recall that we denote the partition sets of the graph by Ai and for i = 1, . . . , p we have
ai = |Ai |. For simplicity, we assume for the moment that a1 ≤ . . . ≤ ap . We will now present
an inductive method to compute the h-vector of ∆.
When we restrict to the first layer A1 , we obtain a 0-dimensional matroid on a1 vertices. It
is clear that in this case J(∆1 ) = (x1 · · · xa1 ) so the h-vector of ∆1 is the vector of length a1 :
(1, 1, . . . , 1). Let v2,1 be the first vertex of the parallel class A2 . This vertex will be a cone-point
of the 1-dimensional matroid ∆|A1 ∪{v2,1 } , so the h-vector will be the same as the one of ∆1 . We
will now use the recursive formula (1) to compute the h-vector of ∆1,2 . By Lemma 2.5 we have
link∆1,2 v2,i = A1 ,

∀ v2,i ∈ A2 .

So the h-vector of ∆|A1 ∪{v2,1 ,v2,2 } is computed as follows:
1 1 ... 1 1
1 1 1 ... 1 0
1 2 2 ... 2 1
where the first row represents the h-vector of ∆|A1 ∪{v2,1 } , the second row represents the h-vector
of the link, i.e. of ∆1 . The last row is the h-vector of ∆|A1 ∪{v2,1 ,v2,2 } . To compute the h-vector
of ∆|A1 ∪{v2,1 ,v2,2 ,v2,3 } we proceed in the same way. All together we have to apply this procedure

10

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

a2 − 1 times. This can be done also directly in the following way:
1
1

1

1
1
1

... 1 1 1
... 1 1 0
... 1 0 0
...

1 1 1 ... 1 0 ... 0 0 0
1 2 3 . . . a1 a1 . . . 3 2 1
The h-vector of ∆1,2,3 of is computed in a similar way. The only difference is that v3,1 will
no longer be a cone point. Thus the first row will be h∆1,2 and the number of shifted rows will
be a3 . Repeating this procedure, we can imagine that h∆ is computed summing the columns of
the staircase in Figure 1. Notice that the last nonzero entry of h∆ is p − 1.
✛

1 1 1
1 1 1 1

·

·

1
1 1
1 1 1
1 1 1 1

·
1
1
1
1

1
·
1
1
1
1

1
1
·
1
1
1
1

·

·

·

·

·

·

·

·

·

·

·

·

·

1
1
·
1
1
1
1

1
1
·
1
1
1
1

1
1
·
1
1
1
1

1
1
·
1
1
1
1

1
1
·
1
1
1
1

1
1
·
1
1
1
1

·

·

·

·

·

·

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

✲
a1
·
1 1 ✻
·
1 1
a2
·
· · · ·
·
·
1 1 ❄
1 1
·
· ·· · ·
·
1 1 ✻
·
1
·
·
ap
·
· · · ·
·
·
·
❄

Figure 1. Computing h∆ for d = 2
In Figure 2 we can see one example of how the corresponding order ideal is constructed in
the case when ∆ is the 1-dimensional matroid on 15 vertices, with 4-partition (3,3,4,5). Notice
that the columns contain monomials of the same degree and that the exponent of x is constant
on the rows. Depending on the order of the parallel classes we can build a total of 12 different
staircases, each one producing an order ideal. Eliminating the symmetry given by exchanging
x and y, we are left with 6 different order ideals with the right f -vector. For example ordering
the partition as (4, 3, 3, 5) we obtain the order ideal generated by {x4 y 9 , x7 y 6 , x10 y 3 }.
In higher dimensions the picture becomes more complicated. One can either imagine ddimensional staircases, where each cube has value 1, or 2-dimensional staircases, where each row
is the h-vector of the link of a parallel class. As we already saw, the order of the ai ’s plays no
role in the computation of h∆ , providing us with several ways to construct an order ideal with
the same f -vector. A complicated example in dimension 2, with 6-partite 1-skeleton shows that
unfortunately with this method there is no “canonical” choice. By canonical we understand a
construction that should be independent of the values of the ai ’s.

h-VECTORS OF MATROID COMPLEXES

11
x11 x11 y x11y 2

x10 x10 y x10y 2
x9
x8
x7
x6
x5
x4
x3

x3 y

x4 y

x5 y

x6 y

x7 y

x8 y

x9 y

x9 y 2

x8 y 2 x8 y 3 x8 y 4 x8 y 5

x7 y 2 x7 y 3 x7 y 4 x7 y 5

x6 y 2 x6 y 3 x6 y 4 x6 y 5

x5 y 2 x5 y 3 x5 y 4 x5 y 5

x4 y 2 x4 y 3 x4 y 4 x4 y 5 x4 y 6 x4 y 7 x4 y 8 x4 y 9

x3 y 2 x3 y 3 x3 y 4 x3 y 5 x3 y 6 x3 y 7 x3 y 8 x3 y 9

x2

x2 y x2 y 2 x2 y 3 x2 y 4 x2 y 5 x2 y 6 x2 y 7 x2 y 8 x2 y 9

x

xy

xy 2

xy 3

xy 4

xy 5

xy 6

xy 7

xy 8

1

y

y2

y3

y4

y5

y6

y7

y8

y9

h: 1

2

3

4

5

6

7

8

9

10 10

xy 9

9

6

3

Figure 2. One order ideal which produces h∆ the 4-partition (3, 3, 4, 5)
There is one case in which the choice of the order ideal is unique, namely the case when d = p.
As we will see in Remark 4.4, this is equivalent to J(∆) being Gorenstein.
Lemma 3.1. If ∆ is a (d − 1)-dimensional, d-partite matroid (so d = p) with partition
(a1 , . . . , ad ), then
h∆ = f (hy1a1 −1 · · · ydad −1 i).
Proof. The minimal generators of J(∆) are the monomials corresponding to the basic covers
of ∆. In this situation, A1 , . . . , Ad are the unique basic covers of ∆, so J(∆) is a complete
intersection with d generators of degrees a1 , . . . , ad . The conclusion follows because the h-vector
of a complete intersection depends only on the degree of its minimal generators.

We will now define a class of matroids and prove that the Stanley conjecture holds for this
class. When one fixes the dimension and the p-partition of the vertex set, these matroids will
have all the admissible faces, thus they are in a sense a generalization of the Gorenstein matroids.
Definition 3.2. Let ∆ be a d − 1-dimensional matroid on [n] with p-partite 1-skeleton. We say
that ∆ is a complete p-partite matroid if
Ai1 . . . Aid ∈ ∆,

for any subset {i1 , . . . , id } ⊂ {1, . . . , p}.

Whenever p is clear from the context, we will just call ∆ complete. Notice that a complete
matroid is uniquely determined by the cardinalities of the parallel classes a1 , . . . , ap and by d.
It is also clear that a matroid is complete iff its simplification si∆ is the uniform matroid Ud,p
(see [15, p. 17]). Complete matroids also generalize partition matroids (see [15, p. 18]), which
correspond to the case p = d. In Proposition 2.2 we proved that for d = 2 all matroids are
complete. For d > 2 this is no longer true, as the following easy example shows.
Example 3.3. Let n = 4 and ∆ = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}}. It is clear that ∆ is a matroid.
The 1-skeleton of ∆ is
∆1 = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}} = K4 ,
so it is a complete 4-partite graph. This means that a1 = a2 = a3 = a4 = 1. Clearly this
matroid is not complete, as the face {2, 3, 4} is missing. The complete 2-dimensional matroid
corresponding to the above ai ’s is ∆′ = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}.

12

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

Remark 3.4. Let ∆ be a complete p-partite matroid. We have
(i) For any subset of vertices M ⊂ [n] the restriction of ∆ to M is also a complete matroid.
(ii) For any parallel class Ai , the link in ∆ of any of its vertices link∆ Ai is also a complete
matroid.
Theorem 3.5. Let ∆ be a complete, (d − 1)-dimensional matroid with p-partition of the 1skeleton A1 , . . . , Ap . For i = 1, . . . , p we denote by ai = |Ai |. Let Γ be the pure multi-complex
on {y1 , . . . , yd } with facets
F(Γ) =

P
Pl2 −1
Pl1 −1
( pi=l
ai )−1
ai )−1
ai )−1 ( i=l
( i=l
d−1
1
0
· · · yd
y2
{y1

: ∀ 1 = l0 < l1 < l2 < . . . < ld−1 ≤ p}.

Then we have that
h∆ = f (Γ),
where h∆ is the h-vector of the algebra S/J(∆).
Before we start the proof, let us make a few easy remarks and introduce some notation. For
each i ∈ {d, . . . , p}, we denote the link of the i-parallel class in the restriction of ∆ to the first i
parallel classes by
Li = link∆1,...,i Ai .
Notice that Li is the (d− 2)-skeleton of ∆1,...,i−1 . We will write r(i) for the length of the h-vector
of Li . As the number of vertices of Li is a1 + . . . + ai−1 and its dimension is d − 2, we have that
r(i) = 2 − d +

i−1
X

aj .

j=1

Proof. We will prove this theorem by simultaneous induction on d and p − d. The case d = 1 is
trivially true and by Lemma 3.1 we know that the theorem is true for p = d.
For each i, denote by ΓLi the pure multi-complex corresponding to Li which is given by the
inductive hypothesis. We assume now that p > d > 1 and that h∆1,...,p−1 = f (Γp−1 ), where
Γp−1 =

P
Pl2 −1
Pl1 −1
( pi=l
ai )−1
( i=1
ai )−1 ( i=l1 ai )−1
d−2
· · · yd
hy1
y2

: ∀ 1 < l1 < l2 < . . . < ld−1 ≤ p − 1i.

We will use h∆1,...,p−1 and hLp to compute h∆ via the formula given in (1). Clearly this formula
has to be applied ap times, once for every vertex in Ap . So we obtain
ap −1
∆

(2)

h (j) = h

∆1,...,p−1

(j − ap ) +

X

hLp (j − k),

k=0

Pp

for all 0 ≤ j ≤ 1 − d + k=1 ak . To conclude we just need to check that the f -vectors of Γ, Γp−1
and ΓLp satisfy the same formula. To this purpose, for any j ∈ Z, let us denote Fj = {M ∈
Γ : deg M = j}, Gj = {M ∈ ΓLp : deg M = j} and Hj = {M ∈ Γp−1 : deg M = j}. Let us
furthermore partition Fj as


p −1
[ a[

Fj = Fj,≥ap
Fj,k  ,
k=0

a
yd p

where Fj,≥ap = {M ∈ Fj :
to check the bijections of sets

| M } and Fj,k = {M ∈ Fj : ydk | M and ydk+1 ∤ M }. It is easy
Gj−ap
M

∼
=

−
→ Fj,≥ap
7→

a

M · yd p

and, for all k = 0, . . . , ap − 1,
∼
=

Hj−k −
→ Fj,k
M

7→

M · ydk

h-VECTORS OF MATROID COMPLEXES

13

Therefore we get the formula
ap −1

X

fj (Γ) = fj−ap (Γp−1 ) +

fj−k (ΓLp ) ∀ j ∈ Z,

k=0

which, together with (2), yields the conclusion by induction.



Fixing two positive integers d and n and a vector a = (a1 , . . . , ap ) ∈ (Z+ )p such that p ≥ d,
a1 + . . . + ap = n, we introduce the class
M(d, p, a),
consisting of all (d − 1)-dimensional matroids with p-partite 1-skeleton, where the partition sets
Ai have cardinality ai for all i = 1, . . . , p. Note that the classes M(d, p, a) depend only on the set
{a1 , . . . , ap }. That is, M(d, p, a) coincides with M(d, p, aσ ) for any permutation σ of p elements
(aσ means (aσ(1) , . . . , aσ(p) )). Furthermore notice that, if d = 2 or p = d, M(d, p, a) consists of
a single matroid, but this happens only in these cases. To see this, it is enough to consider for
t = 0, . . . , d − 2, the following simplicial complexes
(3)

∆t (d, p, a) = h{v1 , v2 , . . . , vt , vi1 , . . . , vid−t } : t < i1 < . . . < id−t ≤ p where vi ∈ Ai i.

It is easy to see that ∆t (d, p, a) are elements of M(d, p, a). Moreover, one can show that, if
p > d, they are not isomorphic pairwise - the easiest way to show this is to notice that they
have a different number of facets. The matroid ∆0 (d, p, a) is just the complete p-partite matroid
whose partition sets A1 , . . . , Ap satisfy |Ai | = ai for all i = 1, . . . , p. Notice that, apart from the
case t = 0, the matroid ∆t (d, p, a) depends on the vector a, not just on the set of its entries.
Remark 3.6. For every t, d, n and a as above the matroids ∆t (d, p, a) are representable. To
see this it is enough to notice that their simplification satisfies
si

∆t (d, p, a) = {v1 , . . . , vt } ∗ Ud−t,p−t = h{v1 , . . . , vt } ∪ F : F ∈ F(Ud−t,p−t )i,

where the vi ’s are fixed vertices and Ud−t,p−t is the uniform matroid of rank d − t on p − t
vertices. Thus, a representation of ∆t (d, p, a) is obtained by taking ai copies of the ith column
(i = 1, . . . , p) in a representation of {v1 , . . . , vt } ∗ Ud−t,p−t . Furthermore, it is easy to check that
in order to obtain a representation over a field F, its cardinality has to be “large enough”.
As a first thing, we want to show that Stanley’s conjecture holds true for all ∆t (d, p, a).
Theorem 3.7. Let d, p ∈ N be such that p ≥ d ≥ 1 and a = (a1 , . . . , ap ) ∈ (Z+ )p . Then
h∆t (d,p,a) is a pure O-sequence for all t = 0, . . . , d − 2.
Proof. The case t = 0 has already been treated in Theorem 3.5. So, we will use induction
on t, assuming that t ≥ 1. Let us write ∆t for ∆t (d, p, a). The restricted simplicial complex
∆′t = (∆t )2,3,...,p is just ∆t−1 (d − 1, p − 1, ã), where ã = (a2 , . . . , ap ). Therefore, we know by
′
induction that h∆t is a pure O-sequence. Set A1 = {v1,1 , . . . , v1,a1 } and ∆it ⊂ ∆t the subcomplex induced by the vertices A2 ∪ . . . ∪ Ap ∪ {v1,1 , . . . , v1,i } for all i = 1, . . . , a1 . We have
1
′
′
h∆t = h∆t ∗a1,1 = h∆t . Moreover, for all i ≥ 2 and k ∈ Z, we have
i−1

i

′

h∆t (k) = h∆t (k − 1) + h∆t (k).
Particularly, since ∆t = ∆at 1 , we get
∆t

(4)

h

(k) =

aX
1 −1

′

h∆t (k − j)

∀ k ∈ Z.

j=0

′

′

We know that h∆t is a pure O-sequence, so let Γ′ be the order ideal such that fΓ′ = h∆t . Let
us suppose that the set of maximal degree monomials of Γ′ is
FΓ′ = {u1 , . . . , us : ui ∈ k[y2 , . . . , yd ] and deg(ui ) = a2 + . . . + ap − d + 1}.
Let Γ be the pure order ideal with the following set of maximal monomials:
F(Γ) = {u1 y1a1 −1 , . . . , us y1a1 −1 }.

14

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

One can easily see that
fΓ (k) =

aX
1 −1

∀ k ∈ Z,

fΓ′ (k − j),

j=0

so (4) yields the conclusion.



Putting together Theorem 3.5 and the proof of Theorem 3.7 we obtain an explicit construction
for an order ideal with the f -vector we are looking for. Namely, we obtain the following corollary.
Corollary 3.8. If we denote by Γt (d, p, a) the following order ideal:
P
Pl1 −1
( pi=l
ai )−1
a1 −1
at −1 ( i=t+1 ai )−1
d−t−1
· · · yd
hy1
· · · yt
yt+1

: ∀ t + 1 < l1 < l2 < . . . < ld−t−1 ≤ pi,

we have that
h∆t (d,p,a) = f (Γt (d, p, a)).
In particular,
(5)

type(S/J(∆t (d, p, a))) =




p−t−1
d−t−1

A consequence of Theorem 3.7 is the following interesting fact:
Corollary 3.9. Let d ≥ 1. For all a ∈ (Z+ )d+1 and ∆ ∈ M(d, d+1, a), h∆ is a pure O-sequence.
Proof. We want to show that ∆ actually is ∆t (d, p, a) for some t = 0, . . . , d − 2, so that Theorem
is
3.7 would give the thesis. Passing to si∆, a proof in the case a = 1 = (1, 1, . . . , 1) ∈ (Z)d+1
+
enough. Notice that any (d−1)-dimensional pure simplicial complex on the vertex set {1, . . . , d+
1} is a matroid. In order to have the complete graph on d + 1 vertices as 1-skeleton, si∆ must
have m ≥ 3 facets. Moreover, if ∆ is a (d − 1)-simplicial complex on d + 1 vertices with m ≥ 3
facets, then it is easy to prove that ∆ is isomorphic to the matroid ∆d−m+1 (d, d + 1, 1).

4. Minimal and maximal h-vectors
Among the matroids described in (3), two play a fundamental role:
(6)

∆max (d, p, a) = ∆0 (d, p, a),
∆min (d, p, a) = ∆d−2 (d, p, aσ ),

where σ is a permutation of p elements such that aσ(1) ≤ . . . ≤ aσ(p) . In this section we will see
that, for any ∆ ∈ M(d, p, a), we have
h∆min (d,p,a) ≤ h∆ ≤ h∆max (d,p,a)
component-wise.
Given a matroid ∆ with parallel classes A1 , . . . , Ap , we need to consider in the following
lemma the matroid ∆r↔s, where the parallel classes Ar and As are switched. Let us give a more
rigorous definition: The matroid ∆r↔s has as facets the subsets F = {vi1 , . . . , vid } of [n] such
that one of the following happens:
(i) |F ∩ (Ar ∪ As )| ∈ {0, 2} and F ∈ F(∆),
(ii) vij ∈ Ar , F ∩ As = ∅ and there exists v ∈ As such that (F \ {vij }) ∪ {v} ∈ F(∆),
(iii) vik ∈ As , F ∩ Ar = ∅ and there exists u ∈ Ar such that (F \ {vik }) ∪ {u} ∈ F(∆).
Lemma 4.1. Let p > d and a = (a1 , . . . , ap ) ∈ (Z+ )p be a vector such that a1 ≤ . . . ≤ ap . Let
∆ ∈ M(d, p, a) be a matroid such that Ap is a cone class for ∆ (i.e. it corresponds to a cone
point in si∆). Pick ℓ ∈ {1, . . . , p − 1} such that Aℓ is not a cone class for ∆ (it exists because
p > d). Then
h∆ℓ↔p ≤ h∆ .

h-VECTORS OF MATROID COMPLEXES

15

Proof. Set Lp = link∆ Ap and Lℓ = link∆ℓ↔p Aℓ . Furthermore, let L′p = Lp \ Aℓ and L′ ℓ = Lℓ \ Ap .
Notice that L′p ∼
= L′ ℓ and that T = linkLp Aℓ ∼
= linkL′ ℓ Ap = U . For all k ∈ Z, we have
ap −1

(7)

h∆ (k) =

X

′

hLp (k − aℓ − i) +

ap −1 aℓ
XX

hT (k − aℓ − i + j)

i=0 j=1

i=0

and
(8)

∆ℓ↔p

h

(k) =

aX
ℓ −1

L′ ℓ

h

(k − ap − i) +

i=0

ap
aX
ℓ −1 X

hU (k−ap −i+j ).

i=0 j=1

′

From the above discussion we have hLp (r) = hL ℓ (r) =: h′r and hT (r) = hU (r) =: h′′r for all
r ∈ Z. Let us set
ap −1 aℓ
ap −1
XX
X
′
h′′k−aℓ −i+j
hk−aℓ −i , M2 =
M1 =
′

i=0 j=1

i=0

and
N1 =

aX
ℓ −1

h′k−ap −i ,

N2 =

ap
aX
ℓ −1 X

h′′k−ap −i+j .

i=0 j=1

i=0

Because aℓ ≤ ap , obviously N1 ≤ M1 . Moreover we claim that N2 = M2 . To see this, it is
enough to notice that
h′′k−ap −i+j = h′′k−aℓ −(ap −j)+(aℓ −i) .
So, we get that (8) is less than or equal to (7).



We need one more technical lemma.
Lemma 4.2. Let A1 , . . . , Ap and B1 , . . . , Bq be partitions of {1, . . . , n} of cardinality |Ai | = ai
and |Bj | = bj , where p ≥ d and q ≥ d, such that
(i)
(ii)
(iii)
(iv)

a1 ≤ . . . ≤ ap ,
b1 ≤ . . . ≤ bq ,
S rj
Ai ,
Bj = k=1
Sd
Sd j,k
i=1 Ai ⊂
i=1 Bi .

Set ã = (a1 , a2 , . . . , ad−1 , ad + . . . + ap ) and b = (b1 , . . . , bq ). If Γ is the only (d − 1)-dimensional
matroid in M(d, d, ã), then
hΓ ≤ h∆

∀ ∆ ∈ M(d, q, b).

Proof. If q = d, then the assertion can be deduced by inspection on the h-vectors of ∆ and Γ,
described in Theorem 3.5. In fact, using this theorem, one can show a more general statement:
Let α = (α1 , . . . , αd ) ∈ (Z+ )d and β = (β1 , . . . , βd ) ∈ (Z+ )d be vectors such that α1 ≤ . . . ≤ αd ,
Pd
Pd
β1 ≤ . . . ≤ βd ,
i=1 αi =
i=1 βi and αi ≤ βi for all i = 1, . . . , d − 1. Then, the h-vector
of the only matroid in M(d, d, α) is less than or equal to the h-vector of the only matroid in
M(d, d, β). We leave the easy proof of this fact to the reader.
We will use induction on p. Notice that, as we always have d ≤ q ≤ p, the case p = d, implies
q = d, so we are done by the above discussion.
If p > d and q > d, then iq,k > d for all k = 1, . . . , rq . Consider the sub-complex Γ′ ⊂ Γ
induced by the vertices not in Bq and set L = linkΓ Bq . As Bq is a subset of a parallel class in
Γ, L is well defined and for all k ∈ Z we have
′

hΓ (k) = hΓ (k − bq ) +

bq
X
i=1

hL (k − bq + i).

16

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

In the same vein, we can consider the sub-complex ∆′ ⊂ ∆ induced by all the vertices of ∆
not in Bq and we set K = link∆ Bq . Once again we have, for all k ∈ Z,
∆′

∆

h (k) = h (k − bq ) +

bq
X

hK (k − bq + i).

i=1

By Lemma 4.1 we can assume that Bq is not a cone class of ∆, so that ∆′ has dimension d − 1.
′
′
Therefore by the induction on p we immediately get hΓ ≤ h∆ .
On the other hand, L is the unique (d−1)-partite (d−2)-dimensional matroid on the partition
(a1 , . . . , ad−1 ), whereas K is a (d − 2)-dimensional matroid on a certain partition C1 , . . . , Cr .
For sure r ≥ d − 1 and, provided that |C1 | ≤ . . . ≤ |Cr |, we get also that ai ≤ bi ≤ |Ci | for
all i = 1, . . . d − 1. Take a facet {vi1 , . . . , vid−1 } of K and suppose that each vik ∈ Cik . Then
the sub-complex K ′ ⊂ K induced by the vertices of Ci1 ∪ . . . ∪ Cid−1 is a complete (d − 1)partite (d − 2)-dimensional matroid. We can assume i1 < . . . < id , so that ak ≤ |Cik | for all
k = 1, . . . , d − 1. So we can choose ak vertices in each one of the Cik s. It turns out that L is
isomorphic to the sub-complex of K ′ induced by these vertices. Therefore L is isomorphic to an
induced sub-complex of K, which implies hL ≤ hK . So we can conclude.

Theorem 4.3. If d ≥ 1 and a = (a1 , . . . , ap ) ∈ (Z+ )p with p ≥ d, then
h∆min (d,p,a) ≤ h∆

∀ ∆ ∈ M(d, p, a).

Proof. Since neither the matroid ∆min (d, p, a) nor the set M(d, p, a) depend on the order of
a1 , . . . , ap , we are allowed to assume that a1 ≤ . . . ≤ ap . We induct on p. If p = d, then the
theorem is trivial, since M(d, d, a) consists of only one matroid, namely ∆min (d, d, a). If p > d,
let us set ∆min (d, p, a)′ ⊂ ∆min (d, p, a) and ∆′ ⊂ ∆ the sub-complexes induced by the vertices of
A1 ∪ . . . ∪ Ap−1 . Furthermore set a′ = (a1 , . . . , ap−1 ). We have that ∆min (d, p, a)′ = ∆min (d, p −
1, a′ ). Exploiting Lemma 4.1, we can assume that dim ∆′ = d − 1, so that ∆′ ∈ M(d, p − 1, a′ ).
So, by induction, we get
′
′
h∆min (d,p,a) ≤ h∆ .
Now set L = link∆min (d,p,a) Ap and K = link∆ Ap . It turns out that L is the unique (d − 1)-partite
(d − 2)-dimensional matroid on the partition (a1 , . . . , ad−2 , ad−1 + . . . + ap−1 ). Instead K will
be a (d − 2)-dimensional matroid on a certain partition (b1 , . . . , bq ). Such partitions satisfy the
hypotheses of Lemma 4.2, so we get
hL ≤ hK .
This yields the conclusion, since for all k ∈ Z
∆min (d,p,a)

h

∆min (d,p,a)′

(k) = h

(k − ap ) +

ap
X

hL (k − ap + i) and

i=1

ap
′

h∆ (k) = h∆ (k − ap ) +

X

hK (k − ap + i).

i=1


Remark 4.4. By Theorem 4.3 and (5) one has that, for all ∆ ∈ M(d, p, a),
(9)

type(S/J(∆)) ≥ p − d + 1.

This implies that, for any matroid ∆, S/I∆ is Gorenstein if and only if I∆ is a complete intersection if and only if p = d. So we recover [21, Theorem 4.4.10].
Equation (9) allows us to prove the following:
Theorem 4.5. If ∆ is a matroid on {1, . . . , n} such that type(S/I∆ ) ≤ 3, then h(∆) = h(k[∆])
is a pure O-sequence. Equivalently, if the h-vector of a matroid has the shape (1, h1 , . . . , hs ) with
hs ≤ 3, then it is a pure O-sequence.

h-VECTORS OF MATROID COMPLEXES

17

Proof. First of all we replace I∆ for J(∆). If type(S/J(∆)) ≤ 2, then ∆ has to belong or to
M(d, d, a) or to M(d, d + 1, a) thanks to Equation (9), so in these cases the statement follows at
once by Lemma 3.1 and Corollary 3.9. Thus we have only to care of the case type(S/J(∆)) = 3.
Again using Equation (9), Lemma 3.1 and Corollary 3.9, we can assume that ∆ is in M(d, d +
2, a). The Cohen-Macaulay type of S/J(∆) is the same as the one of S/J(si∆) by Proposition
2.8. But the dual of si∆ is a rank 2 matroid (possibly on less than d + 2 vertices), so it is some
si
complete p-partite graph G (see Proposition 2.2). Furthermore h ∆ = hG = (1, h1 , h2 ), where
h2 = e−v +1 (v denotes the number of vertices of G and e the number of its edges). But we want
h2 = 3, that is e = v + 2. It is easy to check that the only complete p-partite graph on v vertices
with v + 2 edges is the complete graph on 4 vertices. This means that si∆ = ∆d−2 (d, d + 2, 1),
so ∆ = ∆d−2 (d, d + 2, a). Now the conclusion follows from Theorem 3.7.

To show that ∆max (d, p, a) has maximal h-vector among the matroids ∆ ∈ M(d, p, a) is much
easier.
Theorem 4.6. If d ≥ 1 and a = (a1 , . . . , ap ) ∈ (Z+ )p with p ≥ d, then
h∆ ≤ h∆max (d,p,a)

∀ ∆ ∈ M(d, p, a).

Proof. It is harmless to assume that k is infinite; otherwise we can tensor with its algebraic
closure. Looking at the respective vertex covers, it is clear that J(∆max (d, p, a)) ⊂ J(∆) for
all ∆ ∈ M(d, p, a). Since both S/J(∆max (d, p, a)) and S/J(∆) are (n − d)-dimensional CohenMacaulay rings, we can choose n−d linear forms which are both S/J(∆max (d, p, a))- and S/J(∆)regular (the generic ones have this property). Passing to the Artinian reduction, the inclusion
is preserved, so we infer the desired inequality.

References
[1] M. Boij, J. Migliore, R. Mirò-Roig, U. Nagel, F. Zanello, On the shape of a pure O-sequence, to appear in
Mem. Amer. Math. Soc.
[2] W. Bruns, J. Herzog, Cohen-Macaulay rings, Cambridge Studies in Advanced Mathematics 39, 1993.
[3] M.K. Chari, Two decompositions in topological combinatorics with applications to matroid complexes, Trans.
Amer. Math. Soc. 349, no. 10, 3925–3943, 1997.
[4] CoCoATeam, CoCoA: a system for doing Computations in Commutative Algebra, available at
http://cocoa.dima.unige.it
[5] H.T. Hà, E. Stokes and F. Zanello, Pure O-sequences and matroid h-vectors, available at
http://arxiv.org/abs/1006.0325.
[6] R. Hartshorne, A property of A-sequences, Bull. de la S. M. F. 94, pp. 61–65, 1966.
[7] T. Hibi, What can be said about pure O-sequences?, J. Combin. Theory Ser. A 50 n.2, pp. 319–322, 1989.
[8] T. Hibi, Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings
of distributive lattices, Pacific J. Math. 154 n.2, pp. 253–264, 1992.
[9] A. Iarrobino, Compressed algebras: Artin algebras having given socle degrees and minimal length, Trans.
Amer. Math. Soc. 285, pp. 337–378, 1984.
[10] D. Massey, R. Simion, R. Stanley, D. Vertigan, D. Welsh, G. Ziegler, Lê numbers of arrangements and matroid
identities, J. Combin. Theory Ser. B 70 (1997), no. 1, 118–133.
[11] C. Merino, The chip firing game and matroid complexes, Discrete Math. Theor. Comput. Sci. Proc., AA,
Maison Inform. Math. Discrete (MIMD), Paris, pp. 245–255, 2001.
[12] C. Merino, Steven D. Noble, M. Ramirez-Ibanez, R. Villarroel, On the structure of the h-vector of a paving
matroid, available at http://arxiv.org/abs/1008.2031.
[13] N.C. Minh, N.V. Trung, Cohen-Macaulayness of monomial ideals and symbolic powers of Stanley-Reisner
ideals, Adv. Math. 226, pp. 1285–1306, 2011.
[14] S. Oh, Generalized permutohedra, h-vector of cotransversal matroids and pure O-sequences, preprint 2010,
(available at http://arxiv.org/abs/1005.5586).
[15] J. Oxley, Matroid theory Second edition. Oxford Graduate Texts in Mathematics, 21. Oxford University
Press, Oxford, (2011).
[16] U. Nagel, T. Römer, Glicci simplicial complexes, J. Pure Appl. Algebra 212, no. 10, 2250–2258, 2008.
[17] J. Schweig, On the h-Vector of a Lattice Path Matroid, Electron. J. Combin. 17 n.1, 2010.
[18] D. Speyer, A matroid invariant via the K-theory of the Grassmannian, Adv. Math. 221 (2009), no. 3, 882–913.
[19] R.P. Stanley, Cohen-Macaulay complexes, in Higher Combinatorics, Reidel, Dordrecht and Boston, pp. 51–62,
1977.
[20] R.P. Stanley, Combinatorics and Commutative Algebra, Birkhäuser, 1996.

18

ALEXANDRU CONSTANTINESCU AND MATTEO VARBARO

[21] E. Stokes, The h-vector of matroids and the arithmetic degree of squarefree strongly stable ideals, Ph.D. thesis,
University of Kentucky, 2008.
[22] E. Stokes, The h-vectors of 1-dimensional Matroid Complexes and a Conjecture of Stanley, preprint 2009,
(available at http://arxiv.org/abs/0903.3569).
[23] E. Swartz, Lower bounds for h-vectors of k-CM, independence, and broken circuit complexes, SIAM J. Discrete
Math. 18 (2004/05), no. 3, 647–661.
[24] M. Varbaro, Symbolic powers and matroids, Proc. Amer. Math. Soc. 139, n. 7, pp. 2357–2366, 2011.
Institut de Matématiques, Université de Neuchâtel, Emile-Argand 1, Neuchâtel, Switzerland
E-mail address: alexandru.constantinescu@unine.ch
URL: http://math.unibas.ch/institut/personen/profil/profil/person/constantinescu/
Dipartimento di Matematica, Università di Genova, Via Dodecaneso 35, Genova 16146, Italy
E-mail address: varbaro@dima.unige.it
URL: www.dima.unige.it/~varbaro/

