the Dowling–Wilson Conjecture?

The Dowling–Wilson conjecture is a fundamental inequality in combinatorial incidence geometry. The simplest special case answers the following question: given $n$ points in the plane which do not all lie on a line, how many unique lines can they determine? Since each pair of points determines a line, the number of lines is clearly at most $\binom{n}{2}$. A lower bound is less obvious: a 1948 theorem of de Bruijn and Erdős dBE48 shows that there must be at least $n$ lines. In fact, their proof is a clever counting argument that involves no geometry at all: they show that, given subsets $A_1, \dots , A_m$ of the $n$ points with the property that each pair of points is contained in exactly one of the subsets and no subset contains all of the points, it is necessary that $m \ge n$.

For a more general version of this problem, consider a finite subset $E$ of a vector space over a field $\mathbb{F}$, and let $d$ be the dimension of the vector space $V$ that they span. The $k$th Whitney number $W_k = W_k(E)$ is defined as the number of distinct $k$-dimensional linear subspaces of $V$ that can be obtained as the linear span of some subset of $E$. For example, we have $W_0 = W_d = 1$, corresponding to the zero subspace (spanned by the empty set) and $V$ (spanned by all of $E$), respectively. In addition, note that $W_1(E)\leq |E|$, with equality unless one of our vectors is a multiple of another. In the case $d=3$, the nonzero elements of $E$ determine $W_1$ points in the projective plane $\mathbb{FP}^2$. These $W_1$ points span a total of $W_2$ lines, and the de Bruijn–Erdős theorem is equivalent to the statement that $W_1 \le W_2$.

Since then, a number of successively more general results have appeared with the theme “$E$ determines more subspaces of large dimension than of small dimension.” In 1951, Motzkin Mot51 proved that $W_1\leq W_{d-1}$ in arbitrary ambient dimension $d$. In 1968, Basterfield and Kelly BK68 gave a combinatorial proof of this fact which does not use projective geometry. In 1975, Dowling and Wilson DW75 showed that

$$\begin{equation} W_0 + W_1 +\dots + W_k \le W_{d-k} + \dots + W_d {\tag{1}} \end{equation}$$

whenever $k \le d/2$, and in a related paper DW74 they made the following stronger conjecture.

Dowling–Wilson Conjecture.

For any $k \le d/2$, we have $W_k\le W_{d-k}$.

The Dowling–Wilson conjecture is also called the top heavy conjecture, because it says that the poset $\mathcal{L}= \mathcal{L}(E)$ of subspaces of $V$ spanned by elements of $E$, ranked by dimension, has more elements of high rank than of low rank. When $d=3$ the Dowling–Wilson conjecture, the inequality 1, and the de Bruijn–Erdős theorem are all equivalent.

Example 1.

Suppose that $|E| = n\geq d$, and that the vectors in $E$ are in general position in their span $V$, meaning that any subset of cardinality at most $d$ is linearly independent. In this case, we have $W_k(E) = \binom{n}{k}$ for all $k<d$, and the inequality $W_k \le W_{d-k}$ is easy to verify algebraically.

Example 2.

Let $b_1,\ldots ,b_n$ be the standard basis for $\mathbb{F}^n$, and let $E = \{b_i - b_j\mid i<j\in [n]\}$. These vectors span the $(n-1)$-dimensional subspace

$$V \coloneq \left\{(x_1,\ldots ,x_n)\in \mathbb{F}^n\Big {|} \sum x_i = 0\right\}.$$

Subspaces of $V$ spanned by subsets of $E$ are in bijection with partitions of the set $[n]$, where a subspace of dimension $k$ corresponds to a partition with $n - k$ parts. More precisely, if $S = \{S_1,\ldots ,S_r\}$ is an unordered collection of disjoint nonempty subsets of $[n]$ with $[n] = S_1\sqcup \cdots \sqcup S_r$, then we may define

$$V_S\coloneq \left\{(x_1,\ldots ,x_n)\in \mathbb{F}^n\Big {|} \sum _{i\in S_j} x_i = 0\text{ for all } j\right\},$$

which has dimension $n-r$ and is spanned by the vectors $\{b_i - b_j \mid i,j\in S_m\text{for some $m$}\}$. Thus $W_k(E)$ is equal to the Stirling number $S(n,n-k)$, which counts partitions of $[n]$ into $n-k$ parts. Already here, the Dowling–Wilson conjecture is not obvious; the resulting inequality on Stirling numbers was proved by Dobson and Rennie RD69, Theorem 2.

Matroids

In fact, Dowling and Wilson conjectured their inequality in a more general setting than the vector configurations we considered above. Just as the theorem of de Bruijn and Erdős can be stated and proved without reference to linear geometry, the Dowling–Wilson conjecture makes sense for arbitrary matroids, which give a combinatorial abstraction of linear independence and incidence geometry. We point to Oxl11 for a comprehensive treatment of the theory of matroids. Matroids famously have dozens of equivalent definitions, one of which we give below.

Definition.

A matroid is a pair $(E,\operatorname {rk})$, where $E$ is a finite set and $\operatorname {rk}$ is a function from the power set of $E$ to the natural numbers satisfying the following conditions:

•

$\operatorname {rk}(\emptyset ) = 0$.

•

For all $S\subset E$ and $e\in E$,$$\operatorname {rk}(S)\leq \operatorname {rk}(S\cup \{e\})\leq \operatorname {rk}(S)+1.$$

•

If $\operatorname {rk}(S\cup \{e\}) = \operatorname {rk}(S\cup \{f\}) = \operatorname {rk}(S)$, then$$\operatorname {rk}(S\cup \{e,f\})= \operatorname {rk}(S).$$

A subset $F\subset E$ is called a flat if it is maximal in its rank, meaning that $\operatorname {rk}(F\cup \{e\}) > \operatorname {rk}(F)$ for all $e\in E\setminus F$. We define the $k$th Whitney number $W_k(E,\operatorname {rk})$ to be the number of flats of rank $k$.

If $E$ is a finite subset of a vector space $V$, then we may define $\operatorname {rk}(S)$ to be the dimension of the linear span of $S$. In this case, a flat is a subset of $E$ with the property that no other element of $E$ is contained in its span. Thus flats of $(E,\operatorname {rk})$ correspond bijectively to subspaces of $V$ spanned by subsets of $E$, and we have an equality $W_k(E,\operatorname {rk}) = W_k(E)$ relating the two different notions of Whitney numbers.

A matroid that arises from a set (or multiset) of vectors is called realizable. Although it is somewhat difficult to come up with nonrealizable examples (the smallest is called the Vámos matroid, which has $|E|=8$), a theorem of Nelson Nel18 says that almost all matroids are nonrealizable. More precisely, the percentage of matroids with $E = [n]$ that are realizable goes to zero as $n$ goes to infinity.

The Dowling–Wilson conjecture is now a theorem. Huh and Wang HW17 used techniques from algebraic geometry to show that it holds for realizable matroids, and more recently Huh, Wang, and the authors BHM$^{+}$ showed that it holds for arbitrary matroids. June Huh’s work on the Dowling–Wilson conjecture was one of the many accomplishments highlighted in his 2022 Fields Medal citation.

The Möbius algebra and the graded Möbius algebra

Dowling and Wilson’s proof of the inequality 1 for arbitrary matroids can be expressed in an instructive way. For a matroid $M = (E, \operatorname {rk})$, the poset of flats $\mathcal{L}$ is a ranked lattice, and in particular it has a join operation sending flats $F, G$ to $F\vee G$, the unique smallest flat containing both $F$ and $G$. It has the property that

$$\begin{equation} \operatorname {rk}(F\vee G)\leq \operatorname {rk}(F) + \operatorname {rk}(G).{\tag{2}} \end{equation}$$

When the matroid is realized by a vector configuration, this operation corresponds to taking the sum of vector subspaces of $V$.

Consider the Möbius algebra of $\mathcal{L}$, which is the ${\mathbb{Q}}$-vector space with one basis element $y_F$ for each flat $F \in \mathcal{L}$, and with the multiplication $y_F\ast y_G = y_{F\vee G}$. Define a pairing by putting

$$\langle y_F, y_G\rangle = \begin{cases} 1 & \text{if $y_F \ast y_G = y_E$}\\ 0 &\text{otherwise,}\end{cases}$$

and extending linearly. Let $d = \operatorname {rk}(E)$. For any $k$, the inequality 2 implies that the subspace spanned by the elements $\{y_F \mid \operatorname {rk}F\leq k\}$ pairs trivially with the subspace spanned by $\{y_F\mid \operatorname {rk}F < d-k\}$. Dowling and Wilson deduced their theorem from a result which is equivalent to the statement that this pairing is nondegenerate, meaning that every nonzero element pairs nontrivially with something. This implies that the pairing induces an injection from the subspace spanned by $\{y_F \mid \operatorname {rk}F\leq k\}$ to the linear dual of the subspace spanned by $\{y_F\mid \operatorname {rk}F \geq d-k\}$, which implies the inequality 1.

In passing from the inequality 1 to the full conjecture, it is natural to pass from the Möbius algebra to the graded Möbius algebra $\operatorname {H}^*(M)$, which has the same underlying vector space, but with the modified multiplication

$$y_F\cdot y_G = \begin{cases} y_{F\vee G} &\text{if $\operatorname {rk}(F\vee G)= \operatorname {rk}(F) + \operatorname {rk}(G)$}\\ 0 &\text{otherwise.}\end{cases}$$

It is a graded algebra: if $\operatorname {H}^k(M)$ is the span of the $y_F$ with $\operatorname {rk}F = k$, then $\operatorname {H}^j(M) \cdot \operatorname {H}^k(M)\subset \operatorname {H}^{j+k}(M)$. (In technical language, it is the associated graded algebra obtained from a filtration of the Möbius algebra.) One can define a new pairing on $\operatorname {H}^*(M)$ in the same way as before, this time using the modified multiplication. However, this pairing cannot be nondegenerate because $\operatorname {H}^k(M)$ and $\operatorname {H}^{d-k}(M)$ do not have the same dimension.

To prove the Dowling–Wilson conjecture it would be enough to show that every nonzero element of $\operatorname {H}^k(M)$ pairs nontrivially with some element of $\operatorname {H}^{d-k}(M)$ whenever $k \le d/2$, or equivalently that the pairing induces an injection of $\operatorname {H}^k(M)$ into the linear dual of $\operatorname {H}^{d-k}(M)$ for all $k \le d/2$. This was proved by Kung when $k=1$ Kun79, Corollary 3.3, but the statement is false when $k=2$ (via an example communicated to us by Connor Simpson). Instead, HW17 and BHM$^{+}$ deduce the Dowling–Wilson conjecture from a different statement: if $L \in \operatorname {H}^1(M)$ is a positive combination of $y_F$ over all rank $1$ flats $F$, then for any $k \le d/2$, the multiplication

$$\begin{equation*} L^{d-2k}\colon \operatorname {H}^k(M) \to \operatorname {H}^{d-k}(M) \end{equation*}$$

is injective.

The proof in the realizable case

In the realizable case, this injectivity was proved by Huh and Wang by interpreting the graded Möbius algebra $\operatorname {H}^*(M)$ as the cohomology ring of an algebraic variety, which we now describe. We assume for simplicity that our matroid is realizable by vectors over the complex numbers $\mathbb{C}$; the case of arbitrary fields can be obtained by replacing singular cohomology with $\ell$-adic étale cohomology.

Let $V$ be a vector space over $\mathbb{C}$ spanned by a finite set of vectors $E$. Let $V^*$ be the linear dual of $V$, consisting of linear maps from $V$ to $\mathbb{C}$. We define a linear map $i\colon V^*\to \mathbb{C}^E$ whose $e$th coordinate is given by evaluation on the element $e\in E\subset V$. The fact that $V$ is spanned by $E$ implies that $i$ is an injection. Consider the Riemann sphere $\mathbb{CP}^1 = \mathbb{C} \cup \{\infty \}$, and let $Y$ be the closure of $i(V^*)$ inside of $(\mathbb{CP}^1)^E$. The algebraic variety $Y$ is called the arrangement Schubert variety of the pair $(V,E)$, in analogy with classical Schubert varieties in Lie theory. The connection between the geometry of $Y$ and the structure of the matroid $M$ represented by $E$ was first explored by Ardila and Boocher AB16.

The additive action of $V^*$ on itself extends to an action of $V^*$ on $Y$. This action has finitely many orbits, indexed by the flats of $M$, and each orbit is isomorphic to an affine space. More precisely, for any subset $S\subset E$, let $p_S\in (\mathbb{CP}^1)^E$ be the point whose $e$th coordinate is equal to $0$ if $e\in S$ and $\infty$ otherwise. Then:

•

The point $p_S$ lies in $Y$ if and only if $S$ is a flat of the matroid $M$.

•

If $F\subset E$ is a flat, then the stabilizer of $p_F$ in $V^*$ is equal to $\operatorname {Span}(F)^\perp$, and therefore its orbit is isomorphic to $V^*/\operatorname {Span}(F)^\perp \cong \operatorname {Span}(F)^*$. In particular, it is an affine space of dimension $\operatorname {rk}F$.

•

Every element of $Y$ lies in the orbit of exactly one point $p_F$.

Here is a schematic picture of the orbits of $Y$ for the vector arrangement of Example 2 with $n=3$:

In this figure, points are labeled by partitions of the set $[3]$, which correspond to flats. They are also labeled by triples of elements of $\mathbb{C}\mathbb{P}^1$ corresponding to the three vectors $b_1-b_2, b_1-b_3, b_2-b_3 \in V$. For example, the $b_1-b_2$ and $b_2-b_3$ coordinates of the point $p_{\{13,2\}}$ are equal to $\infty$, while the $b_1-b_3$ coordinate is equal to 0 because 1 and 3 lie in the same block of the partition.

Example 3.

Consider the vector configuration from Example 2. We may regard $V^*$ as the space of ordered $n$-tuples of points in $\mathbb{C}$ up to simultaneous translation. Under this identification, the element $b_i-b_j\in E$ is identified with the linear functional that takes an $n$-tuple of complex numbers to the difference between the $i$th and $j$th points, and the compactification $Y$ of $V^*$ is obtained by allowing these distances to go to $\infty$. Recall from Example 2 that flats are in bijection with partitions of the set $[n]$. If $F$ is the flat corresponding to the partition $[n] = S_1\sqcup \cdots \sqcup S_r$, then the orbit containing $p_F$ consists of all tuples for which the distance between the $i$th and $j$th points is finite if and only if $i$ and $j$ lie in the same part of the partition.

The decomposition of $Y$ into affine spaces is a topological cell decomposition with all cells of even dimension. In particular, it implies that the cohomology $\operatorname {H}^*(Y; {\mathbb{Q}})$ vanishes in odd degrees, and that the dimension of $\operatorname {H}^{2k}(Y; {\mathbb{Q}})$ is the $k$th Whitney number $W_k(M)$. In fact, we have a stronger statement: as a ring, $\operatorname {H}^*(Y; {\mathbb{Q}})$ is isomorphic to the graded Möbius algebra $\operatorname {H}^*(M)$, with degrees doubled. (This is not needed to prove the Dowling–Wilson conjecture in the realizable case, but it is key to generalizing it to all matroids.)

Because the variety $Y$ is singular, it is natural to consider its intersection cohomology $\operatorname {IH}^*(Y; {\mathbb{Q}})$, which is a graded module over $\operatorname {H}^*(Y; {\mathbb{Q}})$. For smooth algebraic varieties, intersection cohomology is isomorphic to ordinary cohomology, while for singular varieties the intersection cohomology retains many of the important properties of the cohomology of smooth varieties. In particular, since $Y$ is a projective complex algebraic variety, it satisfies the hard Lefschetz property: If $L\in \operatorname {H}^2(Y; {\mathbb{Q}})$ is ample, then for any $j\leq d = \dim Y$, the multiplication map

$$\begin{equation} L^{d-j}\colon \operatorname {IH}^{j}(Y; {\mathbb{Q}})\to \operatorname {IH}^{2d-j}(Y;{\mathbb{Q}}) {\tag{3}} \end{equation}$$

is an isomorphism.

Because $Y$ is a proper variety which has a decomposition into affine spaces, an argument of Björner and Ekedahl BE09 implies that the graded $\operatorname {H}^*(Y;{\mathbb{Q}})$-module $\operatorname {IH}^*(Y;{\mathbb{Q}})$ has a graded submodule isomorphic to $\operatorname {H}^*(Y;{\mathbb{Q}})$, regarded as a module over itself. This is the last ingredient that we needed to prove the Dowling–Wilson conjecture! Indeed, let $L$ be an ample class in $\operatorname {H}^2(Y;{\mathbb{Q}})$. Restricting the isomorphism 3 to the submodule $\operatorname {H}^*(Y;{\mathbb{Q}})$ gives an injection

$$\operatorname {H}^{2k}(Y; {\mathbb{Q}})\to \operatorname {H}^{2d-2k}(Y;{\mathbb{Q}}).$$

Since the source and target have dimension $W_k(M)$ and $W_{d-k}(M)$, respectively, we obtain the inequality $W_k(M) \le W_{d-k}(M)$.

The proof for general matroids

The proof of the full Dowling–Wilson conjecture in BHM$^{+}$ follows the same basic plan as the proof in the realizable case. Although there is no analogue of the variety $Y$ for general matroids, we still have an analogue of its cohomology ring $\operatorname {H}^*(Y;{\mathbb{Q}})$, namely the graded Möbius algebra $\operatorname {H}^*(M)$. What is needed is to define a graded module $\operatorname {IH}^*(M)$ over the graded ring $\operatorname {H}^*(M)$, called the intersection cohomology module of the matroid $M$, and to show that it satisfies the conditions needed for the argument in the previous section:

•

$\operatorname {IH}^*(M)$ has a submodule isomorphic to $\operatorname {H}^*(M)$.

•

$\operatorname {IH}^*(M)$ satisfies the hard Lefschetz property.

The first condition is immediate from the definition of $\operatorname {IH}^*(M)$ (which we will not give here). The second condition is proved via an elaborate induction in which the hard Lefschetz property is one of fifteen different properties of the module $\operatorname {IH}^*(M)$ that are simultaneously proved BHM$^{+}$, Theorem 3.16. For a diagram depicting the structure of this induction, see BHM$^{+}$, Figure 1.

Many of the steps of the induction are motivated by statements that are known geometrically in the realizable case. There are also strong similarities with two other notable examples where “intersection cohomology” has been defined and Hodge-theoretic statements such as hard Lefschetz have been proved for a nonexistent variety: the intersection cohomology of nonrational fans of Karu Kar04, and Elias and Williamson’s Hodge theory of Soergel bimodules EW14.