Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)

 
 

 

Hodge theory in combinatorics


Author: Matthew Baker
Journal: Bull. Amer. Math. Soc. 55 (2018), 57-80
MSC (2010): Primary 05B35, 58A14
DOI: https://doi.org/10.1090/bull/1599
Published electronically: September 11, 2017
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, Preprint. Available at arxiv:math.CO/1511.02888, 61 pages, 2015.
  • [2] Karim Adiprasito, June Huh, and Eric Katz, Hodge theory of matroids, Notices Amer. Math. Soc. 64 (2017), no. 1, 26-30. MR 3586249, https://doi.org/10.1090/noti1463
  • [3] Christos A. Athanasiadis, Characteristic polynomials of subspace arrangements and finite fields, Adv. Math. 122 (1996), no. 2, 193-233. MR 1409420, https://doi.org/10.1006/aima.1996.0059
  • [4] 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.
  • [5] Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159-183. MR 570784, https://doi.org/10.2307/1999881
  • [6] 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, https://doi.org/10.1017/CBO9780511662041.008
  • [7] Tom Brylawski, The broken-circuit complex, Trans. Amer. Math. Soc. 234 (1977), no. 2, 417-433. MR 468931, https://doi.org/10.2307/1997928
  • [8] Eduardo Cattani, Mixed Lefschetz theorems and Hodge-Riemann bilinear relations, Int. Math. Res. Not. IMRN 10 (2008), Art. ID rnn025, 20. MR 2429243, https://doi.org/10.1093/imrn/rnn025
  • [9] 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, https://doi.org/10.1016/S0012-9593(02)01108-4
  • [10] 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, https://doi.org/10.1090/S0273-0979-09-01260-9
  • [11] C. De Concini and C. Procesi, Wonderful models of subspace arrangements, Selecta Math. (N.S.) 1 (1995), no. 3, 459-494. MR 1366622, https://doi.org/10.1007/BF01589496
  • [12] 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, https://doi.org/10.5802/afst.1408
  • [13] Ben Elias and Geordie Williamson, The Hodge theory of Soergel bimodules, Ann. of Math. (2) 180 (2014), no. 3, 1089-1136. MR 3245013, https://doi.org/10.4007/annals.2014.180.3.6
  • [14] 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, https://doi.org/10.1007/s00222-003-0327-2
  • [15] Alex Fink, Tropical cycles and Chow polytopes, Beitr. Algebra Geom. 54 (2013), no. 1, 13-40. MR 3027663, https://doi.org/10.1007/s13366-012-0122-6
  • [16] Balin Fleming and Kalle Karu, Hard Lefschetz theorem for simple polytopes, J. Algebraic Combin. 32 (2010), no. 2, 227-239. MR 2661416, https://doi.org/10.1007/s10801-009-0212-1
  • [17] 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, https://doi.org/10.1090/S0894-0347-2012-00731-0
  • [18] 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, https://doi.org/10.1007/s00208-011-0777-6
  • [19] 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.
  • [20] Eric Katz, Matroid theory for algebraic geometers, Non-Archimedean and Tropical Geometry, Springer, 2016, pp. 435-517.
  • [21] 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, https://doi.org/10.1016/j.aam.2013.07.001
  • [22] Peter McMullen, On simple polytopes, Invent. Math. 113 (1993), no. 2, 419-444. MR 1228132, https://doi.org/10.1007/BF01244313
  • [23] Peter Nelson, Almost all matroids are non-representable, Preprint. Available at arxiv:math.CO/1605.04288, 4 pages, 2016.
  • [24] Peter Orlik and Louis Solomon, Combinatorics and topology of complements of hyperplanes, Invent. Math. 56 (1980), no. 2, 167-189. MR 558866, https://doi.org/10.1007/BF01392549
  • [25] James G. Oxley, Matroid theory, Oxford Science Publications, The Clarendon Press, Oxford University Press, New York, 1992. MR 1207587
  • [26] Adrien Saumard and Jon A. Wellner, Log-concavity and strong log-concavity: a review, Stat. Surv. 8 (2014), 45-114. MR 3290441, https://doi.org/10.1214/14-SS107
  • [27] 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, https://doi.org/10.1111/j.1749-6632.1989.tb16434.x
  • [28] D. J. A. Welsh, Matroid theory, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. MR 0427112
  • [29] Neil White (ed.), Combinatorial geometries, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge University Press, Cambridge, 1987. MR 921064
  • [30] Günter M. Ziegler, Lectures on polytopes, Graduate Texts in Mathematics, vol. 152, Springer-Verlag, New York, 1995. MR 1311028

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (2010): 05B35, 58A14

Retrieve articles in all journals with MSC (2010): 05B35, 58A14


Additional Information

Matthew Baker
Affiliation: School of Mathematics, Georgia Institute of Technology, Atlanta GA 30332-0160, USA
Email: mbaker@math.gatech.edu

DOI: https://doi.org/10.1090/bull/1599
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.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society