Lagrangian geometry of matroids

Ardila, Federico; Denham, Graham; Huh, June

doi:10.1090/jams/1009

Lagrangian geometry of matroids
HTML articles powered by AMS MathViewer

by Federico Ardila, Graham Denham and June Huh

J. Amer. Math. Soc. 36 (2023), 727-794

DOI: https://doi.org/10.1090/jams/1009

Published electronically: September 9, 2022

HTML | PDF | Request permission

Abstract:

We introduce the conormal fan of a matroid $\operatorname {M}$, which is a Lagrangian analog of the Bergman fan of $\operatorname {M}$. We use the conormal fan to give a Lagrangian interpretation of the Chern–Schwartz–MacPherson cycle of $\operatorname {M}$. This allows us to express the $h$-vector of the broken circuit complex of $\operatorname {M}$ in terms of the intersection theory of the conormal fan of $\operatorname {M}$. We also develop general tools for tropical Hodge theory to prove that the conormal fan satisfies Poincaré duality, the hard Lefschetz theorem, and the Hodge–Riemann relations. The Lagrangian interpretation of the Chern–Schwartz–MacPherson cycle of $\operatorname {M}$, when combined with the Hodge–Riemann relations for the conormal fan of $\operatorname {M}$, implies Brylawski’s and Dawson’s conjectures that the $h$-vectors of the broken circuit complex and the independence complex of $\operatorname {M}$ are log-concave sequences.

References

Ahmed Umer Ashraf and Spencer Backman, Matroid Chern-Schwartz-MacPherson cycles and Tutte activities, arXiv:2007.10278, 2020.
Federico Ardila and Laura Escobar, The harmonic polytope, Selecta Math. (N.S.) 27 (2021), no. 5, Paper No. 91, 31. MR 4314249, DOI 10.1007/s00029-021-00687-6
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
James W. Alexander, The combinatorial theory of complexes, Ann. of Math. (2) 31 (1930), no. 2, 292–320. MR 1502943, DOI 10.2307/1968099
Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant, Log-concave polynomials III: Mason’s ultra-log-concavity conjecture for independent sets of matroids, arXiv:1811.01600, 2018.
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, Limits of Chow groups, and a new construction of Chern-Schwartz-MacPherson classes, Pure Appl. Math. Q. 2 (2006), no. 4, Special Issue: In honor of Robert D. MacPherson., 915–941. MR 2282409, DOI 10.4310/PAMQ.2006.v2.n4.a2
Paolo Aluffi, Grothendieck classes and Chern classes of hyperplane arrangements, Int. Math. Res. Not. IMRN 8 (2013), 1873–1900. MR 3047491, DOI 10.1093/imrn/rns100
Federico Ardila, The geometry of matroids, Notices Amer. Math. Soc. 65 (2018), no. 8, 902–908. MR 3823027
Federico Ardila, The bipermutahedron, Combinatorial Theory, to appear, arXiv:2008.02295, 2022.
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
Alexandre V. Borovik, I. M. Gelfand, and Neil White, Coxeter matroids, Progress in Mathematics, vol. 216, Birkhäuser Boston, Inc., Boston, MA, 2003. MR 1989953, DOI 10.1007/978-1-4612-2066-4
Petter Brändén and June Huh, Hodge–Riemann relations for Potts model partition functions, arXiv:1811.01696, 2018.
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, A semi-small decomposition of the Chow ring of a matroid, arXiv:2002.03341, 2020.
Louis J. Billera, The algebra of continuous piecewise polynomials, Adv. Math. 76 (1989), no. 2, 170–183. MR 1013666, DOI 10.1016/0001-8708(89)90047-9
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
Mats Boij, Juan C. Migliore, Rosa M. Miró-Roig, Uwe Nagel, and Fabrizio Zanello, On the shape of a pure $O$-sequence, Mem. Amer. Math. Soc. 218 (2012), no. 1024, viii+78. MR 2931681, DOI 10.1090/S0065-9266-2011-00647-7
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
M. Brion, Equivariant Chow groups for torus actions, Transform. Groups 2 (1997), no. 3, 225–267. MR 1466694, DOI 10.1007/BF01234659
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 part I: General theory [MR0863010], Matroid theory and its applications, C.I.M.E. Summer Sch., vol. 83, Springer, Heidelberg, 2010, pp. 125–275. MR 2768784, DOI 10.1007/978-3-642-11110-5_{3}
J.-P. Brasselet and M.-H. Schwartz, Sur les classes de Chern d’un ensemble analytique complexe, The Euler-Poincaré characteristic (French), Astérisque, vol. 82, Soc. Math. France, Paris, 1981, pp. 93–147 (French). MR 629125
Andrew Berget, Hunter Spink, and Dennis Tseng, Log-concavity of matroid $h$-vectors and mixed Eulerian numbers, arXiv:2005.01937, 2020.
Dustin Cartwright, Combinatorial tropical surfaces, arXiv:1506.02023, 2015.
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
Manoj K. Chari, Two decompositions in topological combinatorics with applications to matroid complexes, Trans. Amer. Math. Soc. 349 (1997), no. 10, 3925–3943. MR 1422892, DOI 10.1090/S0002-9947-97-01921-1
Eduardo Cattani, Aroldo Kaplan, and Wilfried Schmid, $L^2$ and intersection cohomologies for a polarizable variation of Hodge structure, Invent. Math. 87 (1987), no. 2, 217–252. MR 870728, DOI 10.1007/BF01389415
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
Charles J. Colbourn, The combinatorics of network reliability, International Series of Monographs on Computer Science, The Clarendon Press, Oxford University Press, New York, 1987. MR 902584
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
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
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
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, 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
Christopher Eur and June Huh, Logarithmic concavity for morphisms of matroids, Adv. Math. 367 (2020), 107094, 19. MR 4078485, DOI 10.1016/j.aim.2020.107094
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
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
Andreas Gathmann, Michael Kerber, and Hannah Markwig, Tropical fans and the moduli spaces of tropical curves, Compos. Math. 145 (2009), no. 1, 173–195. MR 2480499, DOI 10.1112/S0010437X08003837
I. M. Gel′fand, M. M. Kapranov, and A. V. Zelevinsky, Discriminants, resultants, and multidimensional determinants, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1994. MR 1264417, DOI 10.1007/978-0-8176-4771-1
Angela Gibney and Diane Maclagan, Lower and upper bounds for nef cones, Int. Math. Res. Not. IMRN 14 (2012), 3224–3255. MR 2946224, DOI 10.1093/imrn/rnr121
Mark Goresky and William Pardon, Chern classes of automorphic vector bundles, Invent. Math. 147 (2002), no. 3, 561–612. MR 1893006, DOI 10.1007/s002220100184
A. Grothendieck, Éléments de géométrie algébrique. II. Étude globale élémentaire de quelques classes de morphismes, Inst. Hautes Études Sci. Publ. Math. 8 (1961), 222 (French). MR 217084
Andreas Gross and Farbod Shokrieh, Cycles, cocycles, and duality on tropical manifolds, Proc. Amer. Math. Soc. 149 (2021), no. 6, 2429–2444. MR 4246795, DOI 10.1090/proc/15468
Tamás Hausel, Quaternionic geometry of matroids, Cent. Eur. J. Math. 3 (2005), no. 1, 26–38. MR 2110782, DOI 10.2478/BF02475653
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 0340058
Takayuki Hibi, What can be said about pure $O$-sequences?, J. Combin. Theory Ser. A 50 (1989), no. 2, 319–322. MR 989204, DOI 10.1016/0097-3165(89)90025-3
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, 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
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
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 0349445
Peter McMullen, On simple polytopes, Invent. Math. 113 (1993), no. 2, 419–444. MR 1228132, DOI 10.1007/BF01244313
Grigory Mikhalkin, Tropical geometry and its applications, International Congress of Mathematicians. Vol. II, Eur. Math. Soc., Zürich, 2006, pp. 827–852. MR 2275625
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
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
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, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 2 (1964), 340–368 (1964). MR 174487, DOI 10.1007/BF00531932
Gian-Carlo Rota, Combinatorial theory, old and new, Actes du Congrès International des Mathématiciens (Nice, 1970) Gauthier-Villars, Paris, 1971, pp. 229–233. MR 0505646
C. Sabbah, Quelques remarques sur la géométrie des espaces conormaux, Astérisque 130 (1985), 161–192 (French). Differential systems and singularities (Luminy, 1983). MR 804052
Marie-Hélène Schwartz, Classes caractéristiques définies par une stratification d’une variété analytique complexe. I, C. R. Acad. Sci. Paris 260 (1965), 3262–3264 (French). MR 212842
Kristin Shaw, Tropical surfaces, arXiv:1506.07407, 2015.
Richard P. Stanley, Cohen-Macaulay complexes, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 51–62. MR 0572989
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
Richard P. Stanley, Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 295–319. MR 1754784
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
V. A. Timorin, An analogue of the Hodge-Riemann relations for simple convex polyhedra, Uspekhi Mat. Nauk 54 (1999), no. 2(326), 113–162 (Russian); English transl., Russian Math. Surveys 54 (1999), no. 2, 381–426. MR 1711255, DOI 10.1070/rm1999v054n02ABEH000134
Angelo Vistoli, Alexander duality in intersection theory, Compositio Math. 70 (1989), no. 3, 199–225. MR 1002043
D. J. A. Welsh, Combinatorial problems in matroid theory, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969) Academic Press, London, 1971, pp. 291–306. MR 0278975
D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
Hassler Whitney, A logical expansion in mathematics, Bull. Amer. Math. Soc. 38 (1932), no. 8, 572–579. MR 1562461, DOI 10.1090/S0002-9904-1932-05460-X
Neil White (ed.), Combinatorial geometries, Encyclopedia of Mathematics and its Applications, vol. 29, Cambridge University Press, Cambridge, 1987. MR 921064, DOI 10.1017/CBO9781107325715
Herbert S. Wilf, Which polynomials are chromatic?, Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973) Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, Rome, 1976, pp. 247–256 (English, with Italian summary). MR 0453579
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
Günter M. Ziegler, Matroid shellability, $\beta$-systems, and affine hyperplane arrangements, J. Algebraic Combin. 1 (1992), no. 3, 283–300. MR 1194080, DOI 10.1023/A:1022492019120