## Hodge theory in combinatorics

HTML articles powered by AMS MathViewer

- by Matthew Baker PDF
- Bull. Amer. Math. Soc.
**55**(2018), 57-80 Request permission

## Abstract:

If $G$ is a finite graph, a *proper coloring* of $G$ is a way to color the vertices of the graph using $n$ colors so that no two vertices connected by an edge have the same color. (The celebrated four-color theorem asserts that if $G$ is planar, then there is at least one proper coloring of $G$ with four colors.) By a classical result of Birkhoff, the number of proper colorings of $G$ with $n$ colors is a polynomial in $n$, called the *chromatic polynomial* of $G$. Read conjectured in 1968 that for any graph $G$, the sequence of absolute values of coefficients of the chromatic polynomial is *unimodal*: it goes up, hits a peak, and then goes down. Read’s conjecture was proved by June Huh in a 2012 paper making heavy use of methods from algebraic geometry. Huh’s result was subsequently refined and generalized by Huh and Katz (also in 2012), again using substantial doses of algebraic geometry. Both papers in fact establish log-concavity of the coefficients, which is stronger than unimodality.

The breakthroughs of the Huh and Huh–Katz papers left open the more general Rota–Welsh conjecture, where graphs are generalized to (not necessarily representable) matroids, and the chromatic polynomial of a graph is replaced by the characteristic polynomial of a matroid. The Huh and Huh–Katz techniques are not applicable in this level of generality, since there is no underlying algebraic geometry to which to relate the problem. But in 2015 Adiprasito, Huh, and Katz announced a proof of the Rota–Welsh conjecture based on a novel approach motivated by but not making use of any results from algebraic geometry. The authors first prove that the Rota–Welsh conjecture would follow from combinatorial analogues of the hard Lefschetz theorem and Hodge–Riemann relations in algebraic geometry. They then implement an elaborate inductive procedure to prove the combinatorial hard Lefschetz theorem and Hodge–Riemann relations using purely combinatorial arguments.

We will survey these developments.

## References

- Karim Adiprasito, June Huh, and Eric Katz,
*Hodge theory for combinatorial geometries*, Preprint. Available at arxiv:math.CO/1511.02888, 61 pages, 2015. - Karim Adiprasito, June Huh, and Eric Katz,
*Hodge theory of matroids*, Notices Amer. Math. Soc.**64**(2017), no. 1, 26–30. MR**3586249**, DOI 10.1090/noti1463 - Christos A. Athanasiadis,
*Characteristic polynomials of subspace arrangements and finite fields*, Adv. Math.**122**(1996), no. 2, 193–233. MR**1409420**, DOI 10.1006/aima.1996.0059 - Farhad Babaee and June Huh,
*A tropical approach to the strongly positive Hodge conjecture*, To appear in*Duke Math. J.*Preprint available at arxiv:math.AG/1502.00299, 50 pages, 2015. - Anders Björner,
*Shellable and Cohen-Macaulay partially ordered sets*, Trans. Amer. Math. Soc.**260**(1980), no. 1, 159–183. MR**570784**, DOI 10.1090/S0002-9947-1980-0570784-2 - Anders Björner,
*The homology and shellability of matroids and geometric lattices*, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 226–283. MR**1165544**, DOI 10.1017/CBO9780511662041.008 - Tom Brylawski,
*The broken-circuit complex*, Trans. Amer. Math. Soc.**234**(1977), no. 2, 417–433. MR**468931**, DOI 10.1090/S0002-9947-1977-0468931-6 - Eduardo Cattani,
*Mixed Lefschetz theorems and Hodge-Riemann bilinear relations*, Int. Math. Res. Not. IMRN**10**(2008), Art. ID rnn025, 20. MR**2429243**, DOI 10.1093/imrn/rnn025 - Mark Andrea A. de Cataldo and Luca Migliorini,
*The hard Lefschetz theorem and the topology of semismall maps*, Ann. Sci. École Norm. Sup. (4)**35**(2002), no. 5, 759–772 (English, with English and French summaries). MR**1951443**, DOI 10.1016/S0012-9593(02)01108-4 - Mark Andrea A. de Cataldo and Luca Migliorini,
*The decomposition theorem, perverse sheaves and the topology of algebraic maps*, Bull. Amer. Math. Soc. (N.S.)**46**(2009), no. 4, 535–633. MR**2525735**, DOI 10.1090/S0273-0979-09-01260-9 - C. De Concini and C. Procesi,
*Wonderful models of subspace arrangements*, Selecta Math. (N.S.)**1**(1995), no. 3, 459–494. MR**1366622**, DOI 10.1007/BF01589496 - Graham Denham,
*Toric and tropical compactifications of hyperplane complements*, Ann. Fac. Sci. Toulouse Math. (6)**23**(2014), no. 2, 297–333 (English, with English and French summaries). MR**3205595**, DOI 10.5802/afst.1408 - Ben Elias and Geordie Williamson,
*The Hodge theory of Soergel bimodules*, Ann. of Math. (2)**180**(2014), no. 3, 1089–1136. MR**3245013**, DOI 10.4007/annals.2014.180.3.6 - Eva Maria Feichtner and Sergey Yuzvinsky,
*Chow rings of toric varieties defined by atomic lattices*, Invent. Math.**155**(2004), no. 3, 515–536. MR**2038195**, DOI 10.1007/s00222-003-0327-2 - Alex Fink,
*Tropical cycles and Chow polytopes*, Beitr. Algebra Geom.**54**(2013), no. 1, 13–40. MR**3027663**, DOI 10.1007/s13366-012-0122-6 - Balin Fleming and Kalle Karu,
*Hard Lefschetz theorem for simple polytopes*, J. Algebraic Combin.**32**(2010), no. 2, 227–239. MR**2661416**, DOI 10.1007/s10801-009-0212-1 - June Huh,
*Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs*, J. Amer. Math. Soc.**25**(2012), no. 3, 907–927. MR**2904577**, DOI 10.1090/S0894-0347-2012-00731-0 - June Huh and Eric Katz,
*Log-concavity of characteristic polynomials and the Bergman fan of matroids*, Math. Ann.**354**(2012), no. 3, 1103–1116. MR**2983081**, DOI 10.1007/s00208-011-0777-6 - June Huh and Botong Wang,
*Enumeration of points, lines, planes etc.*, To appear in*Acta Mathematica*. Preprint available at arxiv:math.CO/1609.05484, 17 pages, 2016. - Eric Katz,
*Matroid theory for algebraic geometers*, Non-Archimedean and Tropical Geometry, Springer, 2016, pp. 435–517. - Matthias Lenz,
*The $f$-vector of a representable-matroid complex is log-concave*, Adv. in Appl. Math.**51**(2013), no. 5, 543–545. MR**3118543**, DOI 10.1016/j.aam.2013.07.001 - Peter McMullen,
*On simple polytopes*, Invent. Math.**113**(1993), no. 2, 419–444. MR**1228132**, DOI 10.1007/BF01244313 - Peter Nelson,
*Almost all matroids are non-representable*, Preprint. Available at arxiv:math.CO/1605.04288, 4 pages, 2016. - Peter Orlik and Louis Solomon,
*Combinatorics and topology of complements of hyperplanes*, Invent. Math.**56**(1980), no. 2, 167–189. MR**558866**, DOI 10.1007/BF01392549 - James G. Oxley,
*Matroid theory*, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR**1207587** - Adrien Saumard and Jon A. Wellner,
*Log-concavity and strong log-concavity: a review*, Stat. Surv.**8**(2014), 45–114. MR**3290441**, DOI 10.1214/14-SS107 - Richard P. Stanley,
*Log-concave and unimodal sequences in algebra, combinatorics, and geometry*, Graph theory and its applications: East and West (Jinan, 1986) Ann. New York Acad. Sci., vol. 576, New York Acad. Sci., New York, 1989, pp. 500–535. MR**1110850**, DOI 10.1111/j.1749-6632.1989.tb16434.x - D. J. A. Welsh,
*Matroid theory*, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR**0427112** - Neil White (ed.),
*Combinatorial geometries*, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge University Press, Cambridge, 1987. MR**921064**, DOI 10.1017/CBO9781107325715 - Günter M. Ziegler,
*Lectures on polytopes*, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR**1311028**, DOI 10.1007/978-1-4613-8431-1

## Additional Information

**Matthew Baker**- Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta GA 30332-0160, USA
- MR Author ID: 638188
- Email: mbaker@math.gatech.edu
- Received by editor(s): May 15, 2017
- Published electronically: September 11, 2017
- Additional Notes: The author’s research was supported by the National Science Foundation research grant DMS-1529573.
- © Copyright 2017 American Mathematical Society
- Journal: Bull. Amer. Math. Soc.
**55**(2018), 57-80 - MSC (2010): Primary 05B35, 58A14
- DOI: https://doi.org/10.1090/bull/1599
- MathSciNet review: 3737210