PDFLINK |

# the Dowling–Wilson Conjecture?

Communicated by *Notices* Associate Editor Emilie Purvine

The Dowling–Wilson conjecture is a fundamental inequality in combinatorial incidence geometry. The simplest special case answers the following question: given 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 A lower bound is less obvious: a 1948 theorem of de Bruijn and Erdős .

For a more general version of this problem, consider a finite subset of a vector space over a field and let , be the dimension of the vector space that they span. The th**Whitney number** is defined as the number of distinct linear subspaces of -dimensional that can be obtained as the linear span of some subset of For example, we have . corresponding to the zero subspace (spanned by the empty set) and , (spanned by all of respectively. In addition, note that ), with equality unless one of our vectors is a multiple of another. In the case , the nonzero elements of , determine points in the projective plane These . points span a total of lines, and the de Bruijn–Erdős theorem is equivalent to the statement that .

Since then, a number of successively more general results have appeared with the theme “ determines more subspaces of large dimension than of small dimension.” In 1951, Motzkin

whenever and in a related paper ,

The Dowling–Wilson conjecture is also called the **top heavy conjecture**, because it says that the poset of subspaces of spanned by elements of ranked by dimension, has more elements of high rank than of low rank. When , the Dowling–Wilson conjecture, the inequality 1, and the de Bruijn–Erdős theorem are all equivalent.

### 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

If is a finite subset of a vector space then we may define , to be the dimension of the linear span of In this case, a flat is a subset of . with the property that no other element of is contained in its span. Thus flats of correspond bijectively to subspaces of spanned by subsets of and we have an equality , 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 a theorem of Nelson ),*almost all* matroids are nonrealizable. More precisely, the percentage of matroids with that are realizable goes to zero as goes to infinity.

The Dowling–Wilson conjecture is now a theorem. Huh and Wang

### 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 the poset of flats , is a ranked lattice, and in particular it has a join operation sending flats to the unique smallest flat containing both , and It has the property that .

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

Consider the **Möbius algebra** of which is the , space with one basis element -vector for each flat and with the multiplication , Define a pairing by putting .

and extending linearly. Let For any . the inequality ,2 implies that the subspace spanned by the elements pairs trivially with the subspace spanned by 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 . to the linear dual of the subspace spanned by 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** which has the same underlying vector space, but with the modified multiplication ,

It is a graded algebra: if is the span of the with then , (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 . in the same way as before, this time using the modified multiplication. However, this pairing cannot be nondegenerate because and do not have the same dimension.

To prove the Dowling–Wilson conjecture it would be enough to show that every nonzero element of pairs nontrivially with some element of whenever or equivalently that the pairing induces an injection of , into the linear dual of for all This was proved by Kung when .

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 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 the case of arbitrary fields can be obtained by replacing singular cohomology with ; étale cohomology. -adic

Let be a vector space over spanned by a finite set of vectors Let . be the linear dual of consisting of linear maps from , to We define a linear map . whose coordinate is given by evaluation on the element th The fact that . is spanned by implies that is an injection. Consider the Riemann sphere and let , be the closure of inside of The algebraic variety . is called the **arrangement Schubert variety** of the pair in analogy with classical Schubert varieties in Lie theory. The connection between the geometry of , and the structure of the matroid represented by was first explored by Ardila and Boocher

The additive action of on itself extends to an action of on This action has finitely many orbits, indexed by the flats of . and each orbit is isomorphic to an affine space. More precisely, for any subset , let , be the point whose coordinate is equal to th if and otherwise. Then:

- •
The point lies in if and only if is a flat of the matroid .

- •
If is a flat, then the stabilizer of in is equal to and therefore its orbit is isomorphic to , In particular, it is an affine space of dimension . .

- •
Every element of lies in the orbit of exactly one point .

Here is a schematic picture of the orbits of for the vector arrangement of Example 2 with :

In this figure, points are labeled by partitions of the set which correspond to flats. They are also labeled by triples of elements of , corresponding to the three vectors For example, the . and coordinates of the point are equal to while the , coordinate is equal to 0 because 1 and 3 lie in the same block of the partition.

The decomposition of into affine spaces is a topological cell decomposition with all cells of even dimension. In particular, it implies that the cohomology vanishes in odd degrees, and that the dimension of is the Whitney number th In fact, we have a stronger statement: as a ring, . is isomorphic to the graded Möbius algebra 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 is singular, it is natural to consider its **intersection cohomology** which is a graded module over , 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 . is a projective complex algebraic variety, it satisfies the **hard Lefschetz property**: If is ample, then for any the multiplication map ,

is an isomorphism.

Because is a proper variety which has a decomposition into affine spaces, an argument of Björner and Ekedahl

Since the source and target have dimension and respectively, we obtain the inequality , .

### The proof for general matroids

The proof of the full Dowling–Wilson conjecture in **intersection cohomology module** of the matroid and to show that it satisfies the conditions needed for the argument in the previous section: ,

- •
has a submodule isomorphic to .

- •
satisfies the hard Lefschetz property.

The first condition is immediate from the definition of (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 that are simultaneously proved

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

## References

[ AB16] - Federico Ardila and Adam Boocher,
*The closure of a linear space in a product of lines*, J. Algebraic Combin.**43**(2016), no. 1, 199–235, DOI 10.1007/s10801-015-0634-x. MR3439307,## Show rawAMSref

`\bib{AB}{article}{ author={Ardila, Federico}, author={Boocher, Adam}, title={The closure of a linear space in a product of lines}, date={2016}, issn={0925-9899,1572-9192}, journal={J. Algebraic Combin.}, volume={43}, number={1}, pages={199\ndash 235}, doi={10.1007/s10801-015-0634-x}, review={\MR {3439307}}, }`

[ BK68] - J. G. Basterfield and L. M. Kelly,
*A characterization of sets of points which determine hyperplanes*, Proc. Cambridge Philos. Soc.**64**(1968), 585–588, DOI 10.1017/s0305004100043243. MR233719,## Show rawAMSref

`\bib{BK}{article}{ author={Basterfield, J.~G.}, author={Kelly, L.~M.}, title={A characterization of sets of {$n$} points which determine {$n$} hyperplanes}, date={1968}, issn={0008-1981}, journal={Proc. Cambridge Philos. Soc.}, volume={64}, pages={585\ndash 588}, doi={10.1017/s0305004100043243}, review={\MR {233719}}, }`

[ BE09] - Anders Björner and Torsten Ekedahl,
*On the shape of Bruhat intervals*, Ann. of Math. (2)**170**(2009), no. 2, 799–817, DOI 10.4007/annals.2009.170.799. MR2552108,## Show rawAMSref

`\bib{BE}{article}{ author={Bj\"{o}rner, Anders}, author={Ekedahl, Torsten}, title={On the shape of Bruhat intervals}, journal={Ann. of Math. (2)}, volume={170}, date={2009}, number={2}, pages={799--817}, issn={0003-486X}, review={\MR {2552108}}, doi={10.4007/annals.2009.170.799}, }`

[ BHM] - Tom Braden, June Huh, Jacob Matherne, Nicholas Proudfoot, and Botong Wang,
*Singular Hodge theory for combinatorial geometries*, Preprint, arXiv:2010.06088v4.,## Show rawAMSref

`\bib{BHMPW2}{eprint}{ author={Braden, Tom}, author={Huh, June}, author={Matherne, Jacob}, author={Proudfoot, Nicholas}, author={Wang, Botong}, title={{Singular Hodge theory for combinatorial geometries}}, arxiv={2010.06088v4}, }`

[ dBE48] - N. G. de Bruijn and P. Erdös,
*On a combinatorial problem*, Nederl. Akad. Wetensch., Proc.**51**(1948), 1277–1279 = Indagationes Math. 10, 421–423 (1948). MR28289,## Show rawAMSref

`\bib{dBE}{article}{ author={de Bruijn, N. G.}, author={Erd\"{o}s, P.}, title={On a combinatorial problem}, journal={Nederl. Akad. Wetensch., Proc.}, volume={51}, date={1948}, pages={1277--1279 = Indagationes Math. 10, 421--423 (1948)}, issn={0370-0348}, review={\MR {28289}}, }`

[ DW74] - Thomas A. Dowling and Richard M. Wilson,
*The slimmest geometric lattices*, Trans. Amer. Math. Soc.**196**(1974), 203–215, DOI 10.2307/1997023. MR345849,## Show rawAMSref

`\bib{DW1}{article}{ author={Dowling, Thomas~A.}, author={Wilson, Richard~M.}, title={The slimmest geometric lattices}, date={1974}, issn={0002-9947}, journal={Trans. Amer. Math. Soc.}, volume={196}, pages={203\ndash 215}, doi={10.2307/1997023}, review={\MR {345849}}, }`

[ DW75] - Thomas A. Dowling and Richard M. Wilson,
*Whitney number inequalities for geometric lattices*, Proc. Amer. Math. Soc.**47**(1975), 504–512, DOI 10.2307/2039773. MR354422,## Show rawAMSref

`\bib{DW2}{article}{ author={Dowling, Thomas A.}, author={Wilson, Richard M.}, title={Whitney number inequalities for geometric lattices}, journal={Proc. Amer. Math. Soc.}, volume={47}, date={1975}, pages={504--512}, issn={0002-9939}, review={\MR {354422}}, doi={10.2307/2039773}, }`

[ EW14] - Ben Elias and Geordie Williamson,
*The Hodge theory of Soergel bimodules*, Ann. of Math. (2)**180**(2014), no. 3, 1089–1136, DOI 10.4007/annals.2014.180.3.6. MR3245013,## Show rawAMSref

`\bib{EW}{article}{ author={Elias, Ben}, author={Williamson, Geordie}, title={The Hodge theory of Soergel bimodules}, journal={Ann. of Math. (2)}, volume={180}, date={2014}, number={3}, pages={1089--1136}, issn={0003-486X}, review={\MR {3245013}}, doi={10.4007/annals.2014.180.3.6}, }`

[ HW17] - June Huh and Botong Wang,
*Enumeration of points, lines, planes, etc*, Acta Math.**218**(2017), no. 2, 297–317, DOI 10.4310/ACTA.2017.v218.n2.a2. MR3733101,## Show rawAMSref

`\bib{HW}{article}{ author={Huh, June}, author={Wang, Botong}, title={Enumeration of points, lines, planes, etc}, journal={Acta Math.}, volume={218}, date={2017}, number={2}, pages={297--317}, issn={0001-5962}, review={\MR {3733101}}, doi={10.4310/ACTA.2017.v218.n2.a2}, }`

[ Kar04] - Kalle Karu,
*Hard Lefschetz theorem for nonrational polytopes*, Invent. Math.**157**(2004), no. 2, 419–447, DOI 10.1007/s00222-004-0358-3. MR2076929,## Show rawAMSref

`\bib{Karu}{article}{ author={Karu, Kalle}, title={Hard Lefschetz theorem for nonrational polytopes}, journal={Invent. Math.}, volume={157}, date={2004}, number={2}, pages={419--447}, issn={0020-9910}, review={\MR {2076929}}, doi={10.1007/s00222-004-0358-3}, }`

[ Kun79] - Joseph P. S. Kung,
*The Radon transforms of a combinatorial geometry. I*, J. Combin. Theory Ser. A**26**(1979), no. 2, 97–102, DOI 10.1016/0097-3165(79)90059-1. MR530281,## Show rawAMSref

`\bib{KungRadonI}{article}{ author={Kung, Joseph P. S.}, title={The Radon transforms of a combinatorial geometry. I}, journal={J. Combin. Theory Ser. A}, volume={26}, date={1979}, number={2}, pages={97--102}, issn={0097-3165}, review={\MR {530281}}, doi={10.1016/0097-3165(79)90059-1}, }`

[ Mot51] - Th. Motzkin,
*The lines and planes connecting the points of a finite set*, Trans. Amer. Math. Soc.**70**(1951), 451–464, DOI 10.2307/1990609. MR41447,## Show rawAMSref

`\bib{Motzkin}{article}{ author={Motzkin, Th.}, title={The lines and planes connecting the points of a finite set}, journal={Trans. Amer. Math. Soc.}, volume={70}, date={1951}, pages={451--464}, issn={0002-9947}, review={\MR {41447}}, doi={10.2307/1990609}, }`

[ Nel18] - Peter Nelson,
*Almost all matroids are nonrepresentable*, Bull. Lond. Math. Soc.**50**(2018), no. 2, 245–248, DOI 10.1112/blms.12141. MR3830117,## Show rawAMSref

`\bib{Nelson}{article}{ author={Nelson, Peter}, title={Almost all matroids are nonrepresentable}, journal={Bull. Lond. Math. Soc.}, volume={50}, date={2018}, number={2}, pages={245--248}, issn={0024-6093}, review={\MR {3830117}}, doi={10.1112/blms.12141}, }`

[ Oxl11] - James Oxley,
*Matroid theory*, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011, DOI 10.1093/acprof:oso/9780198566946.001.0001. MR2849819,## Show rawAMSref

`\bib{Oxley}{book}{ author={Oxley, James}, title={Matroid theory}, series={Oxford Graduate Texts in Mathematics}, volume={21}, edition={2}, publisher={Oxford University Press, Oxford}, date={2011}, pages={xiv+684}, isbn={978-0-19-960339-8}, review={\MR {2849819}}, doi={10.1093/acprof:oso/9780198566946.001.0001}, }`

[ RD69] - B. C. Rennie and A. J. Dobson,
*On Stirling numbers of the second kind*, J. Combinatorial Theory**7**(1969), 116–121. MR241310,## Show rawAMSref

`\bib{DR}{article}{ author={Rennie, B. C.}, author={Dobson, A. J.}, title={On Stirling numbers of the second kind}, journal={J. Combinatorial Theory}, volume={7}, date={1969}, pages={116--121}, issn={0021-9800}, review={\MR {241310}}, }`

## Credits

Figure is courtesy of Tom Braden, Jacob P. Matherne, and Nicholas Proudfoot.

Photo of Tom Braden is courtesy of Michael Becker.

Photo of Jacob P. Matherne is courtesy of Maitreyee Kulkarni.

Photo of Nicholas Proudfoot is courtesy of the University of Oregon Communications.