ENUMERATION OF POINTS, LINES, PLANES, ETC.

arXiv:1609.05484v3 [math.CO] 29 Jan 2017

JUNE HUH AND BOTONG WANG

1. I NTRODUCTION
One of the earliest results in enumerative combinatorial geometry is the following theorem
of de Bruijn and Erdős [dBE48]:
Every finite set of points E in a projective plane determines at least |E| lines, unless E
is contained in a line.
In other words, if E is not contained in a line, then the number of lines in the plane containing
at least two points in E is at least |E|. See [dW66, dW75] for an interesting account of its history
and a survey of known proofs.
The following more general statement, conjectured by Motzkin in [Mot36], was subsequently
proved by many in various settings:
Every finite set of points E in a projective space determines at least |E| hyperplanes,
unless E is contained in a hyperplane.
Motzkin proved the above for E in real projective spaces [Mot51]. Basterfield and Kelly [BK68]
showed the statement in general, and Greene [Gre70] strengthened the result by showing that
there is a matching from E to the set of hyperplanes determined by E, unless E is contained in a
hyperplane:
For every point in E one can choose a hyperplane containing the point in such a way
that no hyperplane is chosen twice.
Mason [Mas72] and Heron [Her73] obtained similar results by different methods.
Let P be the projectivization of an r-dimensional vector space over a field, E ⊆ P be a finite
subset not contained in any hyperplane, and L be the poset of subspaces of P spanned by the
subsets of E. The poset L is a graded lattice, and its rank function satisfies the submodular
inequality
rank(F1 ) + rank(F2 ) ≥ rank(F1 ∨ F2 ) + rank(F1 ∧ F2 ) for all F1 , F2 ∈ L .
For a nonnegative integer p, we write L p for the set of rank p elements in the lattice L . Thus
L 1 is the set of points in E, L 2 is the set of lines joining points in E, and L r is the set with
one element, P. Graded posets obtained in this way are standard examples of geometric lattices
[Wel76]. These include the lattice of all subsets of a finite set (Boolean lattices), the lattice of all
1

2

JUNE HUH AND BOTONG WANG

partitions of a finite set (partition lattices), and the lattice of all subspaces of a finite vector space
(projective geometries). In [DW75], Dowling and Wilson further generalized the above results
for geometric lattices:
For every nonnegative integer p less than 2r , there is a matching from the set of rank at
most p elements of L to the set of corank at most p elements of L .
The matching can be chosen to match the minimum of L to the maximum of L , and hence the
above statement covers all the results introduced above. Kung gave another proof of the same
result from the point of view of Radon transformations in [Kun79, Kun86].
In [DW74, DW75], Dowling and Wilson stated the following “top-heavy” conjecture.
Conjecture 1. Let L be a geometric lattice of rank r.
(1) For every nonnegative integer p less than 2r ,
|L p | ≤ |L r−p |.
In fact, there is an injective map ι : L p → L r−p satisfying x ≤ ι(x) for all x.
(2) For every nonnegative integer p less than 2r ,
|L p | ≤ |L p+1 |.
In fact, there is an injective map ι : L p → L p+1 satisfying x ≤ ι(x) for all x.
The conjecture was reproduced in [Sta12, Exercise 3.37] and [KRY09, Exercise 3.5.7]. For an
overview and related results, see [Aig87]. When L is a Boolean lattice or a projective geometry,
the validity of Conjecture 1 is a classical result. We refer to [HM+13] and [Sta13] for recent
expositions. In these cases, Conjecture 1 implies that L has the Sperner property:
The maximal number of incomparable elements in L is the maximum of |L p | over p.
Kung proved the second part of Conjecture 1 for partition lattices in [Kun93]. Later he showed
the second part of Conjecture 1 for p ≤ 2 when every line contains the same number of points
[Kun00].
We now state our main result. As before, we write P for the projectivization of an r-dimensional
vector space over a field.
Theorem 2. Let E ⊆ P be a finite subset not contained in any hyperplane, and L be the poset
of subspaces of P spanned by subsets of E.
(1) For all nonnegative integers p ≤ q satisfying p + q ≤ r,
|L p | ≤ |L r−q |.
In fact, there is an injective map ι : L p → L r−q satisfying x ≤ ι(x) for all x.

ENUMERATION OF POINTS, LINES, PLANES, ETC.

3

(2) For every positive integer p less than 2r ,

hpi
0 ≤ |L p+1 | − |L p | ≤ |L p | − |L p−1 |
.
Equivalently, |L 0 |, |L 1 | − |L 0 |, . . . , |L p+1 | − |L p | is the h-vector of a shellable simplicial
complex.
For undefined notions in the second statement, we refer to [Sta96, Chapter II].
The first part of Theorem 2 settles Conjecture 1 for all L realizable over some field. We
believe this to be a good demonstration of the power of the main ingredient in the proof, the
decomposition theorem package for intersection complexes [BBD82].
Example 3. Modular geometric lattices, such as Boolean lattices or finite projective geometries,
satisfies a stronger matching property:
For every p, there is an injective or surjective map ι : L p → L p+1 satisfying x ≤ ι(x).
As noted before, this implies that modular geometric lattices have the Sperner property.
Dilworth and Greene constructed in [DG71] a configuration of 21 points in any 10-dimensional
projective space over a field with the property that there is no injective or surjective map
ι : L 6 → L 7,

x ≤ ι(x).

Canfield [Can78] found such “no matching” successive rank level sets as above in partition lat20
tices with sufficiently many elements (exceeding 1010 ). These geometric lattices satisfy Conjecture 1 but do not have the Sperner property.
Rota conjectured that the sizes of the rank level sets of a geometric lattice form a unimodal
sequence [Rot71, RH71]:
|L 0 | ≤ · · · ≤ |L p−1 | ≤ |L p | ≥ |L p+1 | ≥ · · · ≥ |L r | for some p.
Stronger versions of this conjecture were proposed by Mason [Mas72]. The unimodality for the
“upper half” remains as an outstanding open problem.
Example 4. Let λ be a partition of a positive integer, which we view as a Young diagram [Ful97].
For example, the partition (4, 2, 1) of 7 corresponds to the Young diagram

Young’s lattice associated to λ is the graded poset Lλ of all partitions whose Young diagram
fit inside λ. The poset Lλ is usually not a geometric lattice, but Björner and Ekedahl [BE09]
showed that Lλ satisfies both conclusions of Conjecture 1 when r is the number of boxes in λ:
(1) For p less than 2r , there is an injective map ι : L p → L r−p satisfying x ≤ ι(x) for all x.
(2) For p less than 2r , there is an injective map ι : L p → L p+1 satisfying x ≤ ι(x) for all x.

4

JUNE HUH AND BOTONG WANG

However, according to Stanton [Sta90], Young’s lattice for the partition (8, 8, 4, 4) defines a
nonunimodal sequence



|Lλ0 |, |Lλ1 |, |Lλ2 |, . . . , |Lλ24 | =


1, 1, 2, 3, 5, 6, 9, 11, 15, 17, 21, 23, 27, 28, 31, 30, 31, 27, 24, 18, 14, 8, 5, 2, 1 .

Face lattices of simplicial polytopes behaves similarly, starting from dimension 20 [BL80, Bjö81].
See [Zie95, Chapter 8] for a discussion of unimodality in the case of polytopes.
2. T HE GRADED M ÖBIUS ALGEBRA
We use the language of matroids, and use [Wel76] and [Oxl11] as basic references. Let r and
n be positive integers, and let M be a rank r simple matroid on the ground set
E = {1, . . . , n}.
Write L for the lattice of flats of M. We define a graded analogue of the Möbius algebra for L .
Definition 5. Introduce symbols yF , one for each flat F of M, and construct vector spaces
M
M
B p (M) =
Q yF , B ∗ (M) =
Q yF .
F ∈L p

F ∈L

We equip B ∗ (M) with the structure of a commutative graded algebra over Q by setting

 yF ∨F
if rank(F1 ) + rank(F2 ) = rank(F1 ∨ F2 ),
1
2
yF1 yF2 =
 0
if rank(F ) + rank(F ) > rank(F ∨ F ).
1

2

1

2

For simplicity, we write y1 , . . . , yn instead of y{1} , . . . , y{n} .
Maeno and Numata introduced this algebra in a slightly different form in [MN12], who used
it to show that modular geometric lattices have the Sperner property. Note that B ∗ (M) is generated by B 1 (M) as an algebra: If IF is any basis of a flat F of M, then
Y
yF =
yi .
i∈IF

Unlike its ungraded counterpart, which is isomorphic to the product of Q’s as a Q-algebra
[Sol67], the graded Möbius algebra B ∗ (M) has a nontrivial algebra structure. Define
X
L=
yi .
i∈E

We deduce Theorem 2 from the following algebraic statement. Similar injectivity properties
have appeared in the context of Kac-Moody Schubert varieties [BE09] and toric hyperkähler
varieties [Hau05].

ENUMERATION OF POINTS, LINES, PLANES, ETC.

5

Theorem 6. For nonnegative integer p less than 2r , the multiplication map
B p (M) −→ B r−p (M),

ξ 7−→ Lr−2p ξ

is injective, when M is realizable over some field.
It follows that, for nonnegative integers p ≤ q satisfying p + q ≤ r, the multiplication map
B p (M) −→ B r−q (M),

ξ 7−→ Lr−p−q ξ

is injective, when M is realizable over some field. To deduce the first part of Theorem 2 from this,
consider the matrix of the multiplication map with respect to the standard bases of the source
and the target. Entries of this matrix are labeled by pairs of elements of L , and all the entries
corresponding to incomparable pairs are zero. The matrix has full rank, so there is a maximal
square submatrix with nonzero determinant. In the standard expansion of this determinant,
there must be a nonzero term, and the permutation corresponding to this term produces the
injective map ι. The second part of Theorem 2 also follows from Theorem 6. To see this, note
that the algebra B ∗ (M) is generated by its degree 1 elements, and apply Macaulay’s theorem to
the quotient of B ∗ (M) by the ideal generated by L [Sta96, Chapter II, Corollary 2.4].
Conjecture 7. Theorem 6 holds without the assumption of realizability.
Let M be as before, and let M be a simple matroid on the ground set
E = {0, 1, . . . , n}.
Let L be the lattice of flats of M. We suppose that M = M/0, that is, M is obtained from M by
contracting the element 0.
Definition 8. Introduce variables xF , one for each non-empty proper flat F of M, and set
SM = Q[xF ]F 6=∅,F 6=E,F ∈L .
The Chow ring A∗ (M) is the quotient of SM by the ideal generated by the linear forms
X
X
xF −
xF ,
i1 ∈F

i2 ∈F

one for each pair of distinct elements i1 and i2 of E, and the quadratic monomials
xF 1 xF 2 ,
one for each pair of incomparable non-empty proper flats of M.
The algebra A∗ (M) and its generalizations were studied by Feichtner and Yuzvinsky in [FY04].
For every i in E, we define an element of A1 (M) by setting
X
βi =
xF ,
F

6

JUNE HUH AND BOTONG WANG

where the sum is over all flats F of M that contain 0 and do not contain i. The linear relations
show that we may equivalently define
X
βi =
xF ,
F

where the sum is over all flats F of M that contain i and do not contain 0. We record here three
basic implications of the defining relations of A∗ (M):
(R1) When F is a non-empty proper flat of M containing exactly one of i and 0,
βi · xF = 0.
This follows from the quadratic monomial relations.
(R2) For every element i in E,
βi · βi = 0.
This follows from the previous statement.
(R3) For any two maximal chains of non-empty proper flats of M, say {F k }1≤k and {Gk }1≤k ,
r
Y

xF k =

k=1

r
Y

k=1

xGk 6= 0.

The proofs of (R1) and (R2) are straightforward. The proof of (R3) can be found in [AHK, Section
5].
Proposition 9. There is a unique injective graded Q-algebra homomorphism
ϕ : B ∗ (M) −→ A∗ (M),

yi 7−→ βi .

Proof. First, we show that there is a well-defined Q-linear map
Y
yF 7−→
ϕ : B ∗ (M) −→ A∗ (M),
βi ,
i∈IF

where IF is any basis of a flat F of M. In other words, if JF is any other basis of F , then
Y
Y
βi =
βi .
i∈IF

i∈JF

Since any basis of F can be obtained from any other basis of F by a sequence of elementary
exchanges, it is enough to check the equality in the special case when IF \JF = {1} and JF \IF =
{2}. Assuming that this is the case, we write the left-hand side of the claimed equality by
 Y
 X 
βi
xG ,
i∈IF ∩JF

G

where the sum is over all non-empty proper flats G of M that contain 0 and does not contain 1.
The relation (R1) shows that we may take the sum only over those G satisfying
0 ∈ G, 1 ∈
/ G, and IF ∩ JF ⊆ G.

ENUMERATION OF POINTS, LINES, PLANES, ETC.

7

Since IF ∪ {0} and JF ∪ {0} are bases of the same flat of M, the above condition is equivalent to
0 ∈ G, 2 ∈
/ G, and IF ∩ JF ⊆ G.
This proves the claimed equality, which shows that ϕ is a well-defined linear map.
Second, we show that ϕ is a ring homomorphism. Given flats F1 and F2 of M, we show
 Y  Y 
βi
βi = 0 when the rank of F1 ∨ F2 is less than |IF1 | + |IF2 |.
i∈IF1

i∈IF2

If the independent sets IF1 and IF2 intersect, this follows from the relation (R2). If otherwise,
the condition on the rank of F1 ∨ F2 implies that there are two distinct bases of F1 ∨ F2 contained
in IF1 ∪ IF2 , say
IF1 ∨F2 ⊆ IF1 ∪ IF2 and JF1 ∨F2 ⊆ IF1 ∪ IF2 .

Using the first part of the proof, once again from the relation (R2), we deduce that
 Y  Y   Y


Y
βi
βi =
βi
βi
i∈IF1

i∈IF2

i∈IF1 ∨F2

=



Y
i∈JF1 ∨F2

i∈IF1 ∪IF2 \IF1 ∨F2

βi



Y


βi = 0.

i∈IF1 ∪IF2 \IF1 ∨F2

This completes the proof that ϕ is a ring homomorphism.
Third, we show that ϕ is injective in degree r. Choose any ordered basis {i1 , . . . , ir } of M. For
each q = 1, . . . , r, we set
n
o
Gq = the closure of 0, i1 , . . . , iq−1 in M.
We deduce from the relation (R1) that




βi1 · · · βir−1 βir = βi1 · · · βir−1 xGr .
Similarly, for any positive integer q ≤ r, we have




βi1 · · · βiq−2 βiq−1 xGq = βi1 · · · βiq−2 xGq−1 xGq = xG1 · · · xGq−1 xGq ,
since Gq−1 is the only flat of M containing Gq−1 , comparable to Gq , and not containing iq−1 .
Combining the above formulas, we deduce from the relation (R3) that
βi1 · · · βir = xG1 · · · xGr 6= 0.
This proves that ϕ is injective in degree r.
Last, we show that ϕ is injective in any degree q less than r. For this we analyze the bilinear
map given by the multiplication

 M
ϕ B q (M) ×
Q xG −→ Aq+1 (M),
G

8

JUNE HUH AND BOTONG WANG

where the sum is over all rank q+1 flats G of M containing 0. For any independent set {i1 , . . . , iq }
of M, we claim that, for any G as in the previous sentence,


n
o
βi1 · · · βiq xG 6= 0 if and only if G is the closure of 0, i1 , . . . , iq in M.
The “if” statement follows from the analysis made above. For the “only if” statement, suppose
that the product is nonzero. Since G contains 0, it must contain i1 , . . . , iq by the relation (R1).
Since G and the closure both have the same rank, we have
n
o
G = the closure of 0, i1 , . . . , iq in M.
This proves the claimed equivalence, and it follows that the image of the basis {yF } of B q (M)
under ϕ is a linearly independent in Aq (M).

3. T HE SIMPLEX , THE CUBE , AND THE PERMUTOHEDRON
In this section, we give a toric preparation for the proof of our main result, Theorem 6. For
undefined terms in toric geometry and intersection theory, we refer to [Ful93] and [Ful98]. All
the Chow groups and rings will have rational coefficients.
As in the previous section, we fix a positive integer n and work with the sets
E = {1, . . . , n} and E = {0, 1, . . . , n}.
Let ZE be the abelian group generated by the basis vectors ei corresponding to i ∈ E. For an
arbitrary subset I ⊆ E, we define
X
eI =
ei .
i∈I

We associate to E the abelian group NE = Z /Z eE and the vector space NE,R = RE /R eE .
E

(1) Let Σ(Sn ) ⊆ NE,R be the image of the normal fan of the standard n-dimensional simplex
n
o
Sn = conv e0 , e1 , . . . , en ⊆ RE .
There are (n + 1) maximal cones in Σ(Sn ), one for each maximal proper subset I of E:
n
o
σI = cone ei | i ∈ I ⊆ NE,R .
This fan defines the n-dimensional projective space Pn , whose homogeneous coordinates
are labeled by i ∈ E.
(2) Let Σ(Cn ) ⊆ RE be the normal fan of the standard n-dimensional cube
n
o
Cn = conv ± e1 , . . . , ±en ⊆ RE .
There are 2n maximal cones in Σ(Cn ), one for each subset I of E:
n
o
n
o
σI = cone ei | i ∈ I − cone ei | i ∈
/ I ⊆ RE .
This fan defines the product of n projective lines (P1 )n , whose multi-homogeneous coordinates are labeled by i ∈ E.

ENUMERATION OF POINTS, LINES, PLANES, ETC.

9

(3) Let Σ(Pn ) ⊆ NE,R be the image of the normal fan of the n-dimensional permutohedron
n
o
Pn = conv (x0 , . . . , xn ) | x0 , . . . , xn is a permutation of 0, . . . , n ⊆ RE .
There are (n + 1)! maximal cones in Σ(Pn ), one for each maximal chain I in 2E :
n
o
σI = cone eI | I ∈ I ⊆ NE,R .
This fan defines the n-dimensional permutohedral space, denoted XAn . See [BB11] for a
detailed study of XAn and its analogues for other root systems.
The inclusion ZE ⊆ ZE induces an isomorphism
ψ −1 : RE −→ NE,R .
This identifies the underlying vector spaces of the normal fans Σ(Sn ), Σ(Pn ), Σ(Cn ):
NE,R
ψ

id

RE .

NE,R

We observe that id and ψ induce morphisms between the fans and their toric varieties
Σ(Pn )
p1

XAn
p2

Σ(Sn )

π1

Σ(Cn ),

π2

Pn

(P1 )n .

The morphism p1 is the standard barycentric subdivision. We check that p2 is a subdivision.
Proposition 10. The isomorphism ψ induces a morphism p2 .
In other words, the image of a cone in Σ(Pn ) under ψ is contained in a cone in Σ(Cn ).
Proof. For each i ∈ E, define ψi as the composition of ψ with the i-th projection
ψi = proji ◦ ψ,
For any subset I ⊆ E, we have



e

 i
ψi (eI ) = −ei



 0

proji : RE −→ R{i} ' R.

if I contains i and does not contain 0,
if I contains 0 and does not contain i,
if otherwise.

It is enough to check that ψi induces a morphism Σ(Pn ) −→ Σ(C1 ).
Recall that any nonzero cone in the normal fan of Pn is of the form
n
o
σI = cone eI | I ∈ I ,

10

JUNE HUH AND BOTONG WANG

where I is a non-empty chain in 2E . Viewing I as an ordered collection of sets, we see that

 ψi (σI ) is contained in the cone generated by ei if i appears before 0 in I , and
 ψ (σ ) is contained in the cone generated by −e if i appears after 0 in I .
i I
i
Thus the image of a cone in Σ(Pn ) under ψi is contained in a cone in Σ(C1 ), for each i ∈ E.



Geometrically, π1 is the blowup of all the torus-invariant points in Pn , all the strict transforms
of torus-invariant P1 ’s in Pn , all the strict transforms of torus-invariant P2 ’s in Pn , and so on. The
map π2 is the blowup of points 0n and ∞n , all the strict transforms of torus-invariant P1 ’s in
(P1 )n containing 0n or ∞n , all the strict transforms of torus-invariant (P1 )2 ’s in (P1 )n containing
0n or ∞n , and so on.
Remark 11. For later use, we record here a combinatorial description of the pullback of piecewise
linear functions under the linear map ψi = proji ◦ ψ:
Let α be the piecewise linear function on Σ(C1 ) determined by its values
α(ei ) = 1 and α(−ei ) = 0.
Then ψi∗ (α) is the piecewise linear function on Σ(Pn ) determined by its values

 1 if I contains i and does not contain 0,
ψi∗ (α)(eI ) =
 0 if otherwise.
Using the correspondence between piecewise linear functions on fans and torus-invariant divisors on toric varieties [Ful93, Chapter 3], the above can be used to describe the pullback homomorphism between the Chow rings
π2∗ : A∗ ((P1 )n ) −→ A∗ (XAn ).
Explicitly, writing yi for the divisor of ei in (P1 )n and xI for the divisor of eI in XAn ,
X
xI ,
π2∗ (yi ) =
I

where the sum is over all subsets I ⊆ E that contain i and do not contain 0.
4. P ROOF OF T HEOREM 6
Let M be a simple matroid on E, and let M be a simple matroid on E with M = M/0. For
simplicity, we take M to be the direct sum of M and the rank 1 matroid on {0}, so that M and M
share the same set of circuits.
Suppose that M is realizable over some field. Then M is realizable over some finite field
[Oxl11, Corollary 6.8.13], and hence over the algebraically closed field Fp for some prime number p. The matroid M is realizable over the same field, say by a spanning set of vectors
r+1

A = {f0 , f1 , . . . , fn } ⊆ Fp

.

ENUMERATION OF POINTS, LINES, PLANES, ETC.

11

Dually, the realization A of M corresponds to an injective linear map between projective spaces
iA : Pr −→ Pn ,

iA = [f0 : f1 : · · · : fn ].

The collection A = {f1 , . . . , fn } is a realization of the matroid M.

The restriction of the torus-invariant hyperplanes of Pn to Pr defines an arrangement of hyperplanes in Pr , which we denote by the same symbol A . We use iA to construct the commutative diagram
XA

jA

XAn

π1A

Pr

iA

π2

π1

Pn

YA

(P1 )n ,

where XA is the strict transform of Pr under π1 and YA is the image of XA under π2 .
The induced map π1A is the blowup of all the zero-dimensional flats of A , all the strict transforms of one-dimensional flats of A , all the strict transforms of two-dimensional flats of A , and
so on. The variety XA is the wonderful model of A corresponding to the maximal building set
[dCP95a]. The variety YA is studied in [AB16], and its affine part centered at ∞n is the reciprocal plane in [EPW16, PS06]. To apply the decomposition theorem of [BBD82], we notice that all
varieties, maps, and sheaves under consideration may be defined over some finite extension of
Fp .
We know that the Chow ring of XA is determined by the matroid M: There is an isomorphism
of graded algebras
A∗ (M) ' A∗ (XA ),
where xF is identified with the class of the strict transform of the exceptional divisor produced when blowing up the flat of A corresponding to F . See [dCP95b, Section 1.1], and also
[dCP95a, FY04]. When M is the Boolean matroid B on E, this describes the Chow ring of the
permutohedral space A∗ (XAn ). In general, the pullback homomorphism
A∗ (B) ' A∗ (XAn )

∗
jA

A∗ (XA ) ' A∗ (M)

is determined by the assignment, for non-empty proper subsets I of E,

x
if I is a flat of M,
I
xI 7−→
 0 if I is a not flat of M.
Fix a prime number ` different from p, and consider the `-adic étale cohomology rings and
the `-adic étale intersection cohomology groups of the varieties in the diagram above. These are
Q` -vector spaces of the form
H∗ (X, Q` ) := H∗ (X, Q`,X ) and IH∗ (X, Q` ) := H∗ (X, ICX ),

12

JUNE HUH AND BOTONG WANG

where Q`,X and ICX are constructible complexes of Q` -sheaves on X as in [BBD82]. The blowup
construction of XA shows that the cycle class map induces an isomorphism of commutative
graded Q` -algebras
A∗ (XA ) ⊗Q Q` ' H2∗ (XA , Q` ),
see [Kee92, Appendix]. For the variety YA , which may be singular, we show in Theorem 14 that
there is an isomorphism of commutative graded Q` -algebras
B ∗ (M) ⊗Q Q` ' H2∗ (YA , Q` ).
In general, the intersection cohomology IH∗ (X, Q` ) is a module over the cohomology H∗ (X, Q` ),
satisfying the Poincaré duality and the hard Lefschetz theorems. See [dCM09] for an introduction and precise statements.
We obtain Theorem 6 from the following general observation. Let f be a proper map from an
r-dimensional smooth projective variety
f : X1 −→ X2 ,
and let L be a fixed ample line bundle on X2 . Consider the pullback homomorphism of cohomology in even degrees
H2∗ (X2 , Q` ) −→ H2∗ (X1 , Q` ).
The image of the pullback is a commutative graded algebra over Q` , denoted B ∗ (f )Q` :


B ∗ (f )Q` = im H2∗ (X2 , Q` ) −→ H2∗ (X1 , Q` ) .
B ∗ (f )Q` is the cyclic H2∗ (X2 , Q` )-submodule of H2∗ (X1 , Q` ) generated by the element 1.
Proposition 12. If f is birational onto its image, then the multiplication map
B p (f )Q` −→ B r−p (f )Q` ,

ξ 7−→ Lr−2p ξ

is injective for every nonnegative integer p less than 2r .
Proof. We reduce to the case when f is surjective. For this consider the factorization
X1

g

f (X1 )

h

X2 ,

f = h ◦ g.

Then B ∗ (f )Q` is a subalgebra of B ∗ (g)Q` , and hence the statement (f, L) follows from (g, h∗ L).
Suppose that f is surjective. The decomposition theorem [BBD82, Section 4.3] says that the
intersection complex of X2 appears as a direct summand of the direct image of the constant
sheaf Q` on X1 :
Rf∗ Q`,X1 ' ICX2 ⊕ C .
Taking cohomology of both sides, we obtain a splitting injection of H∗ (X2 , Q` )-modules
Φ : IH∗ (X2 , Q` ) −→ H∗ (X1 , Q` ).

ENUMERATION OF POINTS, LINES, PLANES, ETC.

13

Since Φ is an isomorphism in degree 0, it restricts to an isomorphism of commutative algebras


im H2∗ (X2 , Q` ) −→ IH2∗ (X2 , Q` ) ' B ∗ (f )Q` .
The conclusion follows from the hard Lefschetz theorem for L on IH2∗ (X2 , Q` ).



Theorem 6 will be deduced from the case when f is the map XA → (P1 )n . For each i ∈ E, let
fi be the composition of f with the i-th projection
fi = proji ◦ f,

proji : (P1 )n −→ P1 .

As in Proposition 9, for each i ∈ E, we write βi for the sum of xF over all flats F of M that
contain i and do not contain 0. As mentioned before, the blowup construction of XA shows
that the cycle class map induces an isomorphism of commutative graded Q` -algebras
A∗ (XA ) ⊗Q Q` ' H2∗ (XA , Q` ),
Let Ψ be the composition of isomorphisms
Ψ : A∗ (M) ⊗Q Q` ' A∗ (XA ) ⊗Q Q` ' H2∗ (XA , Q` ),
which maps xF to the class of the strict transform in XA of the exceptional divisor produced
when blowing up the flat of A in Pr corresponding to F .
Proposition 13. The element Ψ(βi ) is the pullback of the class of a point in P1 under fi .
Proof. We factor f into the composition
XA

jA

XAn

π2

(P1 )n .

As noted before, the pullback map associated to the inclusion jA satisfies

x
if I is a flat of M,
I
xI 7−→
 0 if I is a not flat of M.
Thus it is enough to prove the claim when XA = XAn . This is the case when M is the Boolean
matroid on E, and the claim in this case was proved in Remark 11 at the level of Chow rings. 
Since the cohomology ring of (P1 )n is generated by the pullbacks under fi , Propositions 9 and
13 together show that Ψ induces an isomorphism between B ∗ (M) ⊗Q Q` and B ∗ (f )Q` , which we
denote by Ψ0 . More precisely, there is a commutative diagram
A∗ (M) ⊗Q Q`

Ψ

H2∗ (XA , Q` )

ϕ ⊗Q Q`

B ∗ (M) ⊗Q Q`

Ψ0

B ∗ (f )Q` ,

where ϕ is the injective ring homomorphism of Proposition 9.

14

JUNE HUH AND BOTONG WANG

Proof of Theorem 6. It is enough to show that the multiplication map
B p (M) ⊗Q Q` −→ B r−p (M) ⊗Q Q` ,

ξ 7−→ Lr−2p ξ

is injective. Under the isomorphism Ψ0 , the statement to be proved translates to the conclusion
of Proposition 12 when f is the map XA → (P1 )n .

With more work, we can show that the graded Möbius algebra of the matroid M is isomorphic
to the cohomology ring of the variety YA . Write Li for the first Chern class of the pullback of
O(1) under the composition
(P1 )n

YA

proji

P1 .

Theorem 14. There is an isomorphism of commutative graded Q` -algebras
B ∗ (M) ⊗Q Q` ' H2∗ (YA , Q` ),

yi 7−→ Li .

In what follows, we write z0 , z1 , . . . , zn for the homogeneous coordinates of Pn , and write
(z1 , w1 ), . . . , (zn , wn ) for the multi-homogeneous coordinates of (P1 )n .
Proof. Recall that M and M share the same set of circuits. For every circuit C of M, there are
nonzero constants ac ∈ Fp , one for each element c ∈ C, such that
X
ac zc = 0 on the image of iA : Pr −→ Pn .
c∈C

The collection (ac )c∈C is uniquely determined by the circuit C, up to a common multiple.
A defining set of multi-homogeneous equations of YA is explicitly described by Ardila and
Boocher in [AB16, Theorem 1.3]:
(
)
 Y

X
YA =
ac zc
wd = 0, C is a circuit of M ⊆ (P1 )n .
c∈C

d∈C\c

This shows that YA has an algebraic cell decomposition in the sense of [BE09, Section 3],
a
YA =
Arank(F ) ,
F

where the disjoint union is over all flats F of M, and Arank(F ) is the intersection of YA with the
affine space
n
o
A|F | = wi = 0 if and only if i is not in F ⊆ (P1 )n .
The existence of the cell decomposition has the following implications [BE09, Theorem 3.1]:
(CD1) The natural map H2∗ (YA , Q` ) −→ IH2∗ (YA , Q` ) is injective.
(CD2) The dimension of H2k (YA , Q` ) is the number of k-dimensional cells in YA for all k.

ENUMERATION OF POINTS, LINES, PLANES, ETC.

15

All the odd cohomology groups of YA are zero. When combined with the decomposition theorem for XA → YA , the statement (CD1) shows that the pullback homomorphism in cohomology
H2∗ (YA , Q` ) −→ H2∗ (XA , Q` )
is injective. According to Proposition 13, the pullback of Li in the cohomology of XA is Ψ(βi ),
and hence the previous sentence implies that there is an injective graded ring homomorphism
B ∗ (f )Q` −→ H2∗ (YA , Q` ),

Ψ(βi ) 7−→ Li .

Composing with the isomorphism Ψ0 , we get the injective graded ring homomorphism
B ∗ (M) ⊗Q Q` −→ H2∗ (YA , Q` ),

yi 7−→ Li .

The statement (CD2) shows that the source and the target are Q` -vector spaces of the same
dimension, which is the number of flats of M. Therefore, the map must be an isomorphism. 
Remark 15. Let M be a simple matroid on E = {1, . . . , n} with rank r ≥ 2. We write “deg” for
the isomorphism
deg : B r (M) −→ Q,

yE 7−→ 1.

Let HR(M) be the symmetric n × n matrix with entries

 0
if i = j,
HR(M)ij =
 b (M) if i 6= j,
ij
where bij (M) is the number of bases of M containing i and j. The matrix HR(M) represents the
Hodge-Riemann form
B 1 (M) × B 1 (M) −→ Q,

(ξ1 , ξ2 ) 7−→ deg(Lr−2 ξ1 ξ2 ),

with respect to the standard basis y1 , . . . , yn . It can be shown that the matrix HR(M) has exactly
one positive eigenvalue [HW].
Consider the restriction of HR(M) to the three dimensional subspace of B 1 (M) spanned by
yi , yj , and L. The one positive eigenvalue condition says that the determinant of the resulting
symmetric 3 × 3 matrix is nonnegative, and this implies
2 > b(M)bij (M)/bi (M)bj (M),
where b(M) is the number of bases of M and bi (M) is the number of bases of M containing i.
More detailed arguments will be given in [HW].
Question: How large can the ratio b(M)bij (M)/bi (M)bj (M) be?
For graphic matroids, the work of Kirchhoff on electric circuits shows that the ratio is bounded
above by 1, see [FM92]. In other words, for a randomly chosen spanning tree of a graph, the
presence of an edge can only make any other edge less likely. It was once conjectured that this
is the case for all matroids, but Seymour and Welsh found an example with the ratio ' 1.02
[SW75].

16

JUNE HUH AND BOTONG WANG

Acknowledgements. We thank Petter Brändén, Jeff Kahn, Satoshi Murai, Yasuhide Numata,
Nick Proudfoot, Dave Wagner, and Geordie Williamson for helpful conversations. Special
thanks go to two anonymous referees, who made very useful suggestions. This research started
while Botong Wang was visiting Korea Institute for Advanced Study in summer 2016. We thank
KIAS for excellent working conditions. June Huh was supported by a Clay Research Fellowship
and NSF Grant DMS-1128155.
R EFERENCES
[AHK] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries. arXiv:1511.02888.
[Aig87] Martin Aigner, Whitney numbers. Combinatorial geometries, 139–160, Encyclopedia Math. Appl. 29, Cambridge Univ. Press, Cambridge, 1987.
[AB16] Federico Ardila and Adam Boocher, The closure of a linear space in a product of lines. J. Algebraic Combin. 43
(2016), 199–235.
J. G. Basterfield and L. M. Kelly, A characterization of sets of n points which determine n hyperplanes. Proc. Cambridge Philos. Soc. 64 (1968), 585–588.
[BB11] Victor Batyrev and Mark Blume, The functor of toric varieties associated with Weyl chambers and Losev-Manin
moduli spaces. Tohoku Math. J. (2) 63 (2011), 581–604.
[BBD82] Alexander Beilinson, Joseph Bernstein, and Pierre Deligne, Faisceaux pervers. Astérisque 100, Paris, Soc. Math.
Fr. 1982.
[BL80] Louis Billera and Carl Lee, Sufficiency of McMullen’s conditions for f -vectors of simplicial polytopes. Bulletin Amer.

[BK68]

Math. Soc. 2 (1980), 181–185.
Anders Björner, The unimodality conjecture for convex polytopes, Bulletin of the American Mathematical Society
4 (1981), 187–188.
[BE09] Anders Björner and Torsten Ekedahl, On the shape of Bruhat intervals. Ann. of Math. (2) 170 (2009), 799–817.
[Can78] Rodney Canfield, On a problem of Rota. Bull. Amer. Math. Soc. 84 (1978), 164.
[dBE48] Nicolaas de Bruijn and Paul Erdős, On a combinatorial problem. Indagationes Math. 10 (1948), 421–423.
[dCM09] Mark de Cataldo and Luca Migliorini, The decomposition theorem, perverse sheaves and the topology of algebraic
[Bjö81]

maps. Bull. Amer. Math. Soc. (N.S.) 46 (2009), 535–633.
[dCP95a] Corrado de Concini and Claudio Procesi, Wonderful models of subspace arrangements. Selecta Math. (N.S.) 1
(1995), 459–494.
[dCP95b] Corrado de Concini and Claudio Procesi, Hyperplane arrangements and holonomy equations. Selecta Math. (N.S.)
1 (1995), no. 3, 495?535.
[dW66] Paul de Witte, Combinatorial properties of finite linear spaces. I. Bull. Soc. Math. Belg. 18 (1966), 133–141.
[dW75] Paul de Witte, Combinatorial properties of finite linear spaces. II. Bull. Soc. Math. Belg. 27 (1975), 115–155.
[DG71] Robert Dilworth and Curtis Greene, A counterexample to the generalization of Sperner’s theorem. J. Combinatorial
Theory Ser. A 10 (1971), 18–21.
[DW74] Thomas Dowling and Richard Wilson, The slimmest geometric lattices. Trans. Amer. Math. Soc. 196 (1974), 203–
215.
[DW75] Thomas Dowling and Richard Wilson, Whitney number inequalities for geometric lattices. Proc. Amer. Math. Soc.
47 (1975), 504–512.
[EPW16] Ben Elias, Nicholas Proudfoot, and Max Wakefield, The Kazhdan-Lusztig polynomial of a matroid. Adv. Math. 299
[FM92]
[FY04]

(2016), 36–70.
Tomás Feder and Milena Mihail, Balanced matroids. Proceedings of the 24th ACM Symposium on Theory of
Computing (1992), 26–38.
Eva Maria Feichtner and Sergey Yuzvinsky, Chow rings of toric varieties defined by atomic lattices. Invent. Math.
155 (2004), 515–536.

ENUMERATION OF POINTS, LINES, PLANES, ETC.

[Ful93]
[Ful97]
[Ful98]

17

William Fulton, Introduction to toric varieties. Annals of Mathematics Studies 131, Princeton University Press,
Princeton, NJ, 1993.
William Fulton, Young tableaux. London Mathematical Society Student Texts 35, Cambridge University Press,
1997.
William Fulton, Intersection theory. Second edition. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3.
Folge. A Series of Modern Surveys in Mathematics 2, Springer-Verlag, Berlin, 1998.

[Gre70] Curtis Greene, A rank inequality for finite geometric lattices. J. Combinatorial Theory 9 (1970), 357–364.
[HM+13] Tadahito Harima, Toshiaki Maeno, Hideaki Morita, Yasuhide Numata, Akihito Wachi, and Junzo Watanabe,
The Lefschetz properties. Lecture Notes in Mathematics 2080, Springer, Heidelberg, 2013.
[Hau05] Tamás Hausel, Quarternionic geometry of matroids. Cent. Eur. J. Math. 3 (2005), 26–38.
[Her73] A.P. Heron, A property of the hyperplanes of a matroid and an extension of Dilworth’s theorem. J. Math. Anal. Appl.
42 (1973), 119–131.
[HW]
June Huh and Botong Wang, Mason’s conjecture and the Hodge-Riemann relations for matroids, in preparation.
[Kee92] Sean Keel, Intersection theory of moduli space of stable n-pointed curves of genus zero. Trans. Amer. Math. Soc. 330
(1992), 545–574.
[Kun79] Joseph Kung, The Radon transforms of a combinatorial geometry. I. J. Combin. Theory Ser. A 26 (1979), 97–102.
[Kun86] Joseph Kung, Radon transforms in combinatorics and lattice theory. Combinatorics and ordered sets (Arcata, Calif.,
1985), 33–74, Contemp. Math. 57 Amer. Math. Soc., Providence, RI, 1986.
[Kun93] Joseph Kung, The Radon transforms of a combinatorial geometry. II. Partition lattices. Adv. Math. 101 (1993), 114–
132.
[Kun00] Joseph Kung, On the lines-planes inequality for matroids. In memory of Gian-Carlo Rota. J. Combin. Theory Ser.
A 91 (2000), 363–368.
[KRY09] Joseph Kung, Gian-Carlo Rota, and Catherine Yan, Combinatorics: the Rota way. Cambridge Mathematical Library, Cambridge University Press, Cambridge, 2009.
[MN12] Toshiaki Maeno and Yasuhide Numata, Sperner property, matroids and finite-dimensional Gorenstein algebras,
Tropical geometry and integrable systems, Contemp. Math. 580 (2012), 73–84.
[Mas72] John Mason, Matroids: unimodal conjectures and Motzkin’s theorem. Combinatorics (Proc. Conf. Combinatorial
Math., Math. Inst., Oxford, 1972), 207–220, Inst. Math. Appl., Southend-on-Sea, 1972.
[Mot36] Theodore Motzkin, Beiträge zur Theorie der linearen Ungleichungen. Dissertation, Basel, Jerusalem, 1936.
[Mot51] Theodore Motzkin, The lines and planes connecting the points of a finite set. Trans. Amer. Math. Soc. 70 (1951),
451–464.
[Oxl11] James Oxley, Matroid theory. Second edition. Oxford Graduate Texts in Mathematics 21, Oxford University
Press, Oxford, 2011.
[PS06] Nicholas Proudfoot and David Speyer, A broken circuit ring. Beiträge Algebra Geom. 47 (2006), 161–166.
[Rot71] Gian-Carlo Rota, Combinatorial theory, old and new. Actes du Congrès International des Mathématiciens (Nice,
1970), Tome 3, pp. 229–233. Gauthier-Villars, Paris, 1971.
[RH71] Gian-Carlo Rota and Lawrence Harper, Matching theory, an introduction. Advances in Probability and Related
Topics, Vol. 1 pp. 169–215 Dekker, New York, 1971.
[SW75] Paul Seymour and Dominic Welsh, Combinatorial applications of an inequality from statistical mechanics. Math.
Proc. Cambridge Philos. Soc. 77 (1975), 485–495.
[Sol67] Louis Solomon, The Burnside algebra of a finite group. J. Combin. Theory 2 (1967), 603–615.
[Sta96]
[Sta12]
[Sta13]
[Sta90]

Richard Stanley, Combinatorics and commutative algebra. Second edition. Progress in Mathematics 41, Birkhäuser,
Boston, MA, 1996.
Richard Stanley, Enumerative combinatorics. Volume 1. Second edition. Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, Cambridge, 2012
Richard Stanley, Algebraic combinatorics. Undergraduate Texts in Mathematics, Springer, New York, 2013.
Dennis Stanton, Unimodality and Young’s lattice. J. Combin. Theory Ser. A 54 (1990), 41–53.

18

JUNE HUH AND BOTONG WANG

[Wel76] Dominic Welsh, Matroid theory. London Mathematical Society Monographs 8, Academic Press, London-New
York, 1976.
[Zie95] Günter Ziegler, Lectures on polytopes. Graduate Texts in Mathematics, 152, Springer-Verlag, New York, 1995.
I NSTITUTE FOR A DVANCED S TUDY, F ULD H ALL , 1 E INSTEIN D RIVE , P RINCETON , NJ, USA.
K OREA I NSTITUTE FOR A DVANCED S TUDY, 85 H OEGIRO , D ONGDAEMUN - GU , S EOUL 130-722, K OREA
E-mail address: huh@princeton.edu
U NIVERSITY OF W ISCONSIN -M ADISON , VAN V LECK H ALL , 480 L INCOLN D RIVE , M ADISON , WI, USA.
E-mail address: bwang274@wisc.edu

