Essence of independence: Hodge theory of matroids since June Huh

Eur, Christopher

doi:10.1090/bull/1803

Essence of independence: Hodge theory of matroids since June Huh
HTML articles powered by AMS MathViewer

by Christopher Eur

Bull. Amer. Math. Soc. 61 (2024), 73-102

DOI: https://doi.org/10.1090/bull/1803

Published electronically: July 31, 2023

HTML | PDF | Request permission

Abstract:

Matroids are combinatorial abstractions of independence, a ubiquitous notion that pervades many branches of mathematics. June Huh and his collaborators recently made spectacular breakthroughs by developing a Hodge theory of matroids that resolved several long-standing conjectures in matroid theory. We survey the main results in this development and ideas behind them.

References

Marcelo Aguiar and Federico Ardila, Hopf monoids and generalized permutahedra, Memoirs of the American Mathematical Society (to appear).
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. MR 3439307, DOI 10.1007/s10801-015-0634-x
Federico Ardila, Graham Denham, and June Huh, Lagrangian geometry of matroids, J. Amer. Math. Soc. 36 (2023), no. 3, 727–794. MR 4583774, DOI 10.1090/jams/1009
Karim Adiprasito, June Huh, and Eric Katz, Hodge theory for combinatorial geometries, Ann. of Math. (2) 188 (2018), no. 2, 381–452. MR 3862944, DOI 10.4007/annals.2018.188.2.1
Federico Ardila and Caroline J. Klivans, The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B 96 (2006), no. 1, 38–49. MR 2185977, DOI 10.1016/j.jctb.2005.06.004
Dan Abramovich, Kalle Karu, Kenji Matsuki, and Jarosław Włodarczyk, Torification and factorization of birational maps, J. Amer. Math. Soc. 15 (2002), no. 3, 531–572. MR 1896232, DOI 10.1090/S0894-0347-02-00396-X
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, Log-concave polynomials II: High-dimensional walks and an FPRAS for counting bases of a matroid, STOC’19—Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2019, pp. 1–12. MR 4003314, DOI 10.1145/3313276.3316385
Paolo Aluffi, Differential forms with logarithmic poles and Chern-Schwartz-MacPherson classes of singular varieties, C. R. Acad. Sci. Paris Sér. I Math. 329 (1999), no. 7, 619–624 (English, with English and French summaries). MR 1717120, DOI 10.1016/S0764-4442(00)80012-9
Paolo Aluffi, Characteristic classes of singular varieties, Topics in cohomological studies of algebraic varieties, Trends Math., Birkhäuser, Basel, 2005, pp. 1–32. MR 2143071, DOI 10.1007/3-7643-7342-3_{1}
Omid Amini and Matthieu Piquerez, Hodge theory for tropical varieties, arXiv:2007.07826, 2020.
Federico Ardila, The geometry of matroids, Notices Amer. Math. Soc. 65 (2018), no. 8, 902–908. MR 3823027
Matthew Baker, Hodge theory in combinatorics, Bull. Amer. Math. Soc. (N.S.) 55 (2018), no. 1, 57–80. MR 3737210, DOI 10.1090/bull/1599
A. A. Beĭlinson, J. Bernstein, and P. Deligne, Faisceaux pervers, Analysis and topology on singular spaces, I (Luminy, 1981) Astérisque, vol. 100, Soc. Math. France, Paris, 1982, pp. 5–171 (French). MR 751966
Anders Björner and Torsten Ekedahl, On the shape of Bruhat intervals, Ann. of Math. (2) 170 (2009), no. 2, 799–817. MR 2552108, DOI 10.4007/annals.2009.170.799
Spencer Backman, Christopher Eur, and Connor Simpson, Simplicial generation of Chow rings of matroids, Sém. Lothar. Combin. 84B (2020), Art. 52, 11. MR 4138680
Andrew Berget, Christopher Eur, Hunter Spink, and Dennis Tseng, Tautological classes of matroids, Invent. Math. 233 (2023), no. 2, 951–1039. MR 4607725, DOI 10.1007/s00222-023-01194-5
Petter Brändén and June Huh, Lorentzian polynomials, Ann. of Math. (2) 192 (2020), no. 3, 821–891. MR 4172622, DOI 10.4007/annals.2020.192.3.4
Tom Braden, June Huh, Jacob Matherne, Nicholas Proudfoot, and Botong Wang, Singular Hodge theory for combinatorial geometries, arXiv:2010.06088, 2020
Tom Braden, June Huh, Jacob P. Matherne, Nicholas Proudfoot, and Botong Wang, A semi-small decomposition of the Chow ring of a matroid. part A, Adv. Math. 409 (2022), no. part A, Paper No. 108646, 49. MR 4477425, DOI 10.1016/j.aim.2022.108646
Petter Brändén and Jonathan Leake, Lorentzian polynomials on cones and the Heron-Rota-Welsh conjecture, arXiv:2110.00487, 2021.
Thomas Brylawski and James Oxley, The Tutte polynomial and its applications, Matroid applications, Encyclopedia Math. Appl., vol. 40, Cambridge Univ. Press, Cambridge, 1992, pp. 123–225. MR 1165543, DOI 10.1017/CBO9780511662041.007
Francesco Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Jerusalem combinatorics ’93, Contemp. Math., vol. 178, Amer. Math. Soc., Providence, RI, 1994, pp. 71–89. MR 1310575, DOI 10.1090/conm/178/01893
Michel Brion, Piecewise polynomial functions, convex polytopes and enumerative geometry, Parameter spaces (Warsaw, 1994) Banach Center Publ., vol. 36, Polish Acad. Sci. Inst. Math., Warsaw, 1996, pp. 25–44. MR 1481477
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
Thomas Brylawski, The Tutte polynomial. I. General theory, Matroid theory and its applications, Liguori, Naples, 1982, pp. 125–275. MR 863010
Andrew Berget, Hunter Spink, and Dennis Tseng, Log-concavity of matroid h-vectors and mixed eulerian numbers, arXiv:2005.01937, 2020.
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
D. Cohen, G. Denham, M. Falk, and A. Varchenko, Critical points and resonance of hyperplane arrangements, Canad. J. Math. 63 (2011), no. 5, 1038–1057. MR 2866070, DOI 10.4153/CJM-2011-028-8
David A. Cox, John B. Little, and Henry K. Schenck, Toric varieties, Graduate Studies in Mathematics, vol. 124, American Mathematical Society, Providence, RI, 2011. MR 2810322, DOI 10.1090/gsm/124
Henry H. Crapo, The Tutte polynomial, Aequationes Math. 3 (1969), 211–229. MR 262095, DOI 10.1007/BF01817442
V. I. Danilov, The geometry of toric varieties, Uspekhi Mat. Nauk 33 (1978), no. 2(200), 85–134, 247 (Russian). MR 495499
Jeremy E. Dawson, A collection of sets related to the Tutte polynomial of a matroid, Graph theory, Singapore 1983, Lecture Notes in Math., vol. 1073, Springer, Berlin, 1984, pp. 193–204. MR 761018, DOI 10.1007/BFb0073117
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). MR 28289
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
Pierre Deligne, Théorie de Hodge. II, Inst. Hautes Études Sci. Publ. Math. 40 (1971), 5–57 (French). MR 498551, DOI 10.1007/BF02684692
Graham Denham, Mehdi Garrousian, and Mathias Schulze, A geometric deletion-restriction formula, Adv. Math. 230 (2012), no. 4-6, 1979–1994. MR 2927361, DOI 10.1016/j.aim.2012.04.003
Alexandru Dimca, Hyperplane arrangements, Universitext, Springer, Cham, 2017. An introduction. MR 3618796, DOI 10.1007/978-3-319-56221-6
Alexandru Dimca and Stefan Papadima, Hypersurface complements, Milnor fibers and higher homotopy groups of arrangments, Ann. of Math. (2) 158 (2003), no. 2, 473–507. MR 2018927, DOI 10.4007/annals.2003.158.473
Jeshu Dastidar and Dustin Ross, Matroid psi classes, Selecta Math. (N.S.) 28 (2022), no. 3, Paper No. 55, 38. MR 4405747, DOI 10.1007/s00029-022-00771-5
Thomas A. Dowling and Richard M. Wilson, The slimmest geometric lattices, Trans. Amer. Math. Soc. 196 (1974), 203–215. MR 345849, DOI 10.1090/S0002-9947-1974-0345849-8
Thomas A. Dowling and Richard M. Wilson, Whitney number inequalities for geometric lattices, Proc. Amer. Math. Soc. 47 (1975), 504–512. MR 354422, DOI 10.1090/S0002-9939-1975-0354422-3
David Eisenbud and Joe Harris, 3264 and all that—a second course in algebraic geometry, Cambridge University Press, Cambridge, 2016. MR 3617981, DOI 10.1017/CBO9781139062046
Christopher Eur, June Huh, and Matt Larson, Stellahedral geometry of matroids, arXiv:2207.10605, 2022.
Ben Elias, Nicholas Proudfoot, and Max Wakefield, The Kazhdan-Lusztig polynomial of a matroid, Adv. Math. 299 (2016), 36–70. MR 3519463, DOI 10.1016/j.aim.2016.05.005
Christopher Eur, Divisors on matroids and their volumes, J. Combin. Theory Ser. A 169 (2020), 105135, 31. MR 4011081, DOI 10.1016/j.jcta.2019.105135
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
William Fulton and Bernd Sturmfels, Intersection theory on toric varieties, Topology 36 (1997), no. 2, 335–353. MR 1415592, DOI 10.1016/0040-9383(96)00016-X
William Fulton, Introduction to toric varieties, Annals of Mathematics Studies, vol. 131, Princeton University Press, Princeton, NJ, 1993. The William H. Roever Lectures in Geometry. MR 1234037, DOI 10.1515/9781400882526
William Fulton, Intersection theory, 2nd ed., Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 2, Springer-Verlag, Berlin, 1998. MR 1644323, DOI 10.1007/978-1-4612-1700-8
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
I. M. Gel′fand, R. M. Goresky, R. D. MacPherson, and V. V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. in Math. 63 (1987), no. 3, 301–316. MR 877789, DOI 10.1016/0001-8708(87)90059-4
Mark Goresky and Robert MacPherson, Intersection homology. II, Invent. Math. 72 (1983), no. 1, 77–129. MR 696691, DOI 10.1007/BF01389130
Robin Hartshorne, Algebraic geometry, Graduate Texts in Mathematics, No. 52, Springer-Verlag, New York-Heidelberg, 1977. MR 463157, DOI 10.1007/978-1-4757-3849-0
A. P. Heron, Matroid polynomials, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) Inst. Math. Appl., Southend-on-Sea, 1972, pp. 164–202. MR 340058
Takayuki Hibi, Flawless $O$-sequences and Hilbert functions of Cohen-Macaulay integral domains, J. Pure Appl. Algebra 60 (1989), no. 3, 245–251. MR 1021849, DOI 10.1016/0022-4049(89)90085-6
Takayuki Hibi, Face number inequalities for matroid complexes and Cohen-Macaulay types of Stanley-Reisner rings of distributive lattices, Pacific J. Math. 154 (1992), no. 2, 253–264. MR 1159510, DOI 10.2140/pjm.1992.154.253
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
S. G. Hoggar, Chromatic polynomials and logarithmic concavity, J. Combinatorial Theory Ser. B 16 (1974), 248–254. MR 342424, DOI 10.1016/0095-8956(74)90071-9
June Huh and Bernd Sturmfels, Likelihood geometry, Combinatorial algebraic geometry, Lecture Notes in Math., vol. 2108, Springer, Cham, 2014, pp. 63–117. MR 3329087, DOI 10.1007/978-3-319-04870-3_{3}
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, The maximum likelihood degree of a very affine variety, Compos. Math. 149 (2013), no. 8, 1245–1266. MR 3103064, DOI 10.1112/S0010437X13007057
June Huh, $h$-vectors of matroids and logarithmic concavity, Adv. Math. 270 (2015), 49–59. MR 3286530, DOI 10.1016/j.aim.2014.11.002
June Huh, Tropical geometry of matroids, Current developments in mathematics 2016, Int. Press, Somerville, MA, 2018, pp. 1–46. MR 3837872
June Huh, Combinatorics and Hodge theory, 2022.
Daniel Huybrechts, Complex geometry, Universitext, Springer-Verlag, Berlin, 2005. An introduction. MR 2093043
June Huh and Botong Wang, Enumeration of points, lines, planes, etc, Acta Math. 218 (2017), no. 2, 297–317. MR 3733101, DOI 10.4310/ACTA.2017.v218.n2.a2
Ilia Itenberg, Ludmil Katzarkov, Grigory Mikhalkin, and Ilia Zharkov, Tropical homology, Math. Ann. 374 (2019), no. 1-2, 963–1006. MR 3961331, DOI 10.1007/s00208-018-1685-9
Martina Juhnke-Kubitzke and Dinh Van Le, Flawlessness of $h$-vectors of broken circuit complexes, Int. Math. Res. Not. IMRN 5 (2018), 1347–1367. MR 3801465, DOI 10.1093/imrn/rnw284
Eric Katz, Matroid theory for algebraic geometers, Nonarchimedean and tropical geometry, Simons Symp., Springer, [Cham], 2016, pp. 435–517. MR 3702317
Eric Katz and Sam Payne, Piecewise polynomials, Minkowski weights, and localization on toric varieties, Algebra Number Theory 2 (2008), no. 2, 135–155. MR 2377366, DOI 10.2140/ant.2008.2.135
L. Lafforgue, Chirurgie des grassmanniennes, CRM Monograph Series, vol. 19, American Mathematical Society, Providence, RI, 2003 (French). MR 1976905, DOI 10.1090/crmm/019
Robert Lazarsfeld, Positivity in algebraic geometry. I, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 48, Springer-Verlag, Berlin, 2004. Classical setting: line bundles and linear series. MR 2095471, DOI 10.1007/978-3-642-18808-4
Robert Lazarsfeld, Positivity in algebraic geometry. II, Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], vol. 49, Springer-Verlag, Berlin, 2004. Positivity for vector bundles, and multiplier ideals. MR 2095472, DOI 10.1007/978-3-642-18808-4
Lucía López de Medrano, Felipe Rincón, and Kristin Shaw, Chern-Schwartz-MacPherson cycles of matroids, Proc. Lond. Math. Soc. (3) 120 (2020), no. 1, 1–27. MR 3999674, DOI 10.1112/plms.12278
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
R. D. MacPherson, Chern classes for singular algebraic varieties, Ann. of Math. (2) 100 (1974), 423–432. MR 361141, DOI 10.2307/1971080
J. H. Mason, Matroids: unimodal conjectures and Motzkin’s theorem, Combinatorics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972) Inst. Math. Appl., Southend-on-Sea, 1972, pp. 207–220. MR 349445
Peter McMullen, On simple polytopes, Invent. Math. 113 (1993), no. 2, 419–444. MR 1228132, DOI 10.1007/BF01244313
Diane Maclagan and Bernd Sturmfels, Introduction to tropical geometry, Graduate Studies in Mathematics, vol. 161, American Mathematical Society, Providence, RI, 2015. MR 3287221, DOI 10.1090/gsm/161
Peter Nelson, Almost all matroids are nonrepresentable, Bull. Lond. Math. Soc. 50 (2018), no. 2, 245–248. MR 3830117, DOI 10.1112/blms.12141
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
Peter Orlik and Hiroaki Terao, Arrangements of hyperplanes, Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 300, Springer-Verlag, Berlin, 1992. MR 1217488, DOI 10.1007/978-3-662-02772-1
James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
Nicholas Proudfoot, The algebraic geometry of Kazhdan-Lusztig-Stanley polynomials, EMS Surv. Math. Sci. 5 (2018), no. 1-2, 99–127. MR 3880222, DOI 10.4171/EMSS/28
Nicholas Proudfoot and David Speyer, A broken circuit ring, Beiträge Algebra Geom. 47 (2006), no. 1, 161–166. MR 2246531
Nicholas Proudfoot, Yuan Xu, and Ben Young, The $Z$-polynomial of a matroid, Electron. J. Combin. 25 (2018), no. 1, Paper No. 1.26, 21. MR 3785005, DOI 10.37236/7105
Ronald C. Read, An introduction to chromatic polynomials, J. Combinatorial Theory 4 (1968), 52–71. MR 224505, DOI 10.1016/S0021-9800(68)80087-0
Gian-Carlo Rota, Combinatorial theory, old and new, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars Éditeur, Paris, 1971, pp. 229–233. MR 505646
Werner Schwärzler, The coefficients of the Tutte polynomial are not unimodal, J. Combin. Theory Ser. B 58 (1993), no. 2, 240–242. MR 1223696, DOI 10.1006/jctb.1993.1040
David E. Speyer, Tropical linear spaces, SIAM J. Discrete Math. 22 (2008), no. 4, 1527–1558. MR 2448909, DOI 10.1137/080716219
Richard P. Stanley, The number of faces of a simplicial convex polytope, Adv. in Math. 35 (1980), no. 3, 236–238. MR 563925, DOI 10.1016/0001-8708(80)90050-X
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
Bernd Sturmfels, Solving systems of polynomial equations, CBMS Regional Conference Series in Mathematics, vol. 97, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2002. MR 1925796, DOI 10.1090/cbms/097
Ed Swartz, $g$-elements of matroid complexes, J. Combin. Theory Ser. B 88 (2003), no. 2, 369–375. MR 1983365, DOI 10.1016/S0095-8956(03)00038-8
Hiroaki Terao, Algebras generated by reciprocals of linear forms, J. Algebra 250 (2002), no. 2, 549–558. MR 1899865, DOI 10.1006/jabr.2001.9121
Jenia Tevelev, Compactifications of subvarieties of tori, Amer. J. Math. 129 (2007), no. 4, 1087–1104. MR 2343384, DOI 10.1353/ajm.2007.0029
W. T. Tutte, On dichromatic polynominals, J. Combinatorial Theory 2 (1967), 301–320. MR 223272, DOI 10.1016/S0021-9800(67)80032-2
A. Varchenko, Critical points of the product of powers of linear functions and families of bases of singular vectors, Compositio Math. 97 (1995), no. 3, 385–401. MR 1353281
Claire Voisin, Hodge theory and complex algebraic geometry. I, Cambridge Studies in Advanced Mathematics, vol. 76, Cambridge University Press, Cambridge, 2002. Translated from the French original by Leila Schneps. MR 1967689, DOI 10.1017/CBO9780511615344
Andrzej Weber, Pure homology of algebraic varieties, Topology 43 (2004), no. 3, 635–644. MR 2041634, DOI 10.1016/j.top.2003.09.001
D. J. A. Welsh, Combinatorial problems in matroid theory, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) Academic Press, London-New York, 1971, pp. 291–306. MR 278975
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 427112
Hassler Whitney, The coloring of graphs, Ann. of Math. (2) 33 (1932), no. 4, 688–718. MR 1503085, DOI 10.2307/1968214
Jarosław Włodarczyk, Decomposition of birational toric maps in blow-ups & blow-downs, Trans. Amer. Math. Soc. 349 (1997), no. 1, 373–411. MR 1370654, DOI 10.1090/S0002-9947-97-01701-7
Thomas Zaslavsky, The Möbius function and the characteristic polynomial, Combinatorial geometries, Encyclopedia Math. Appl., vol. 29, Cambridge Univ. Press, Cambridge, 1987, pp. 114–138. MR 921071
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