×

Hodge theory for combinatorial geometries. (English) Zbl 1442.14194

The notion of a matroid, which apriori was introduced as a structure characterizing independence of vector spaces and graphs [H. Whitney, Am. J. Math. 57, 509–533 (1935; Zbl 0012.00404)], is of fundamental importance in graph theory. A (finite) matroid \(M\) is given by a pair \((E,\ell)\), where \(E\) is a finite set, and \(\ell\) is a family of subsets of \(E\) (referred to as independent sets) which satisfy certain properties, namely the defining properties of a closure operator and the Mac Lane-Steinitz exchange property.
The chromatic polynomial \(\chi_G\) associated to a graph \(G\) (which is a function whose value at a positive integer \(q\), \(\chi_G(q)\) is the number of colorings of \(G\) using \(q\) colors) is generalised to the set up of matroids by Rota, and is known as the characteristic poynomial associated to a matroid \(M\) [G.-C. Rota, Z. Wahrscheinlichkeitstheor. Verw. Geb. 2, 340–368 (1964; Zbl 0121.02406)], defined by \[ \chi_M(\lambda) = \sum_{\ell \subset E} (-1)^{|\ell|} \lambda^{\mathrm{crk}(\ell)} \] where the sum is over all subsets \(\ell \subseteq E\) and \(\mathrm{crk}(\ell)\) is the corank of \(\ell\) in \(M\).
A fundamental conjecture that was open in matroid theory, stated in 70’s proposes that the absolute values of coefficients of the characteristic polynomial associated to a matroid \(M\) form a log-concave sequence. More precisely, writing \(r + 1\) for the rank of \(M\), which corresponds to the maximum size of an independent set in the matroid, and letting \(w_k(M)\) denote the absolute value of the coefficient of \(\lambda^{r-k+1}\) in the characteristic polynomial of \(M\), the log-concavity would imply: \[ w_{k-1}(M)w_{k+1}(M) \leq w_k(M)^2 ~ \text{ for all } 1 \leq k \leq r. \] A related conjecture which concerns the number of independent subsets of E of given cardinality was formulated by D. J. A. Welsh [in: Proceedings of a conference of combinatorial mathematics and its applications, 1969. London: Academic Press. 291–306 (1971; Zbl 0233.05001)] and J. H. Mason [“Matroids: unimodal conjectures and Motzkin’s theorem”, in: Proceedings of a conference of combinatorial mathematics and its applications, 1972. London: Academic Press. 207–220 (1972)]. The authors prove all these conjectures in full generality by constructing a “cohomology ring” associated to \(M\) that satisfies the hard Lefschetz theorem and the Hodge-Riemann relations.

MSC:

14T15 Combinatorial aspects of tropical varieties
05A99 Enumerative combinatorics
05E16 Combinatorial aspects of groups and algebras
14F99 (Co)homology theory in algebraic geometry

References:

[1] Adiprasito, Karim A.; Bj\"orner, Anders, Filtered geometric lattices and {L}efschetz section theorems over the tropical semiring, (2014)
[2] Adiprasito, A. Karim; Sanyal, Raman, Log-concavity of {W}hitney numbers via measure concentration, (2016)
[3] Aigner, Martin, Whitney numbers. Combinatorial Geometries, Encyclopedia Math. Appl., 29, 139-160, (1987) · Zbl 0631.05015 · doi:10.1017/CBO9781107325715.010
[4] Aigner, Martin, A Course in Enumeration, Grad. Texts in Math., 238, x+561 pp., (2007) · Zbl 1123.05001 · doi:10.1007/978-3-540-39035-0
[5] Ardila, Federico; Klivans, Caroline J., The {B}ergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B. Journal of Combinatorial Theory. Series B, 96, 38-49, (2006) · Zbl 1082.05021 · doi:10.1016/j.jctb.2005.06.004
[6] Babaee, Farhad; Huh, June, A tropical approach to a generalized {H}odge conjecture for positive currents, Duke Math. J.. Duke Mathematical Journal, 166, 2749-2813, (2017) · Zbl 1396.14064 · doi:10.1215/00127094-2017-0017
[7] Batyrev, Victor; Blume, Mark, The functor of toric varieties associated with {W}eyl chambers and {L}osev-{M}anin moduli spaces, Tohoku Math. J. (2). The Tohoku Mathematical Journal. Second Series, 63, 581-604, (2011) · Zbl 1255.14041 · doi:10.2748/tmj/1325886282
[8] Bifet, Emili; De Concini, Corrado; Procesi, Claudio, Cohomology of regular embeddings, Adv. Math.. Advances in Mathematics, 82, 1-34, (1990) · Zbl 0743.14018 · doi:10.1016/0001-8708(90)90082-X
[9] Billera, Louis J., The algebra of continuous piecewise polynomials, Adv. Math.. Advances in Mathematics, 76, 170-183, (1989) · Zbl 0703.13015 · doi:10.1016/0001-8708(89)90047-9
[10] Birkhoff, George D., A determinant formula for the number of ways of coloring a map, Ann. of Math. (2). Annals of Mathematics. Second Series, 14, 42-46, (1912/13) · JFM 43.0574.02 · doi:10.2307/1967597
[11] Bj{\"o}rner, Anders, The homology and shellability of matroids and geometric lattices. Matroid Applications, Encyclopedia Math. Appl., 40, 226-283, (1992) · Zbl 0772.05027 · doi:10.1017/CBO9780511662041.008
[12] Brion, Michel, Piecewise polynomial functions, convex polytopes and enumerative geometry. Parameter Spaces, Banach Center Publ., 36, 25-44, (1996) · Zbl 0878.14035
[13] Brylawski, Tom, The broken-circuit complex, Trans. Amer. Math. Soc.. Transactions of the American Mathematical Society, 234, 417-433, (1977) · Zbl 0368.05022 · doi:10.2307/1997928
[14] Cattani, Eduardo, Mixed {L}efschetz theorems and {H}odge-{R}iemann bilinear relations, Int. Math. Res. Not. IMRN. International Mathematics Research Notices. IMRN, 025-20, (2008) · Zbl 1149.32014 · doi:10.1093/imrn/rnn025
[15] de Cataldo, Mark Andrea A.; Migliorini, Luca, The hard {L}efschetz theorem and the topology of semismall maps, Ann. Sci. \'Ecole Norm. Sup. (4). Annales Scientifiques de l’\'Ecole Normale Sup\'erieure. Quatri\`“‘eme S\'”’erie, 35, 759-772, (2002) · Zbl 1021.14004 · doi:10.1016/S0012-9593(02)01108-4
[16] Danilov, V. I., The geometry of toric varieties, Uspekhi Mat. Nauk. Akademiya Nauk SSSR i Moskovskoe Matematicheskoe Obshchestvo. Uspekhi Matematicheskikh Nauk, 33, 85-134, (1978) · Zbl 0425.14013 · doi:10.1070/RM1978v033n02ABEH002305
[17] De Concini, C.; Procesi, C., Wonderful models of subspace arrangements, Selecta Math. (N.S.). Selecta Mathematica. New Series, 1, 459-494, (1995) · Zbl 0842.14038 · doi:10.1007/BF01589496
[18] Ewald, G\"unter, Combinatorial Convexity and Algebraic Geometry, Grad. Texts in Math., 168, xiv+372 pp., (1996) · Zbl 0869.52001 · doi:10.1007/978-1-4612-4044-0
[19] Feichtner, Eva Maria; Yuzvinsky, Sergey, Chow rings of toric varieties defined by atomic lattices, Invent. Math.. Inventiones Mathematicae, 155, 515-536, (2004) · Zbl 1083.14059 · doi:10.1007/s00222-003-0327-2
[20] Fulton, William, Introduction to Toric Varieties. The William H. Roever Lectures in Geometry, Ann. of Math. Stud., 131, xii+157 pp., (1993) · Zbl 0813.14039 · doi:10.1515/9781400882526
[21] Fulton, W.; MacPherson, R.; Sottile, F.; Sturmfels, B., Intersection theory on spherical varieties, J. Algebraic Geom.. Journal of Algebraic Geometry, 4, 181-193, (1995) · Zbl 0819.14019
[22] Fulton, William; Sturmfels, Bernd, Intersection theory on toric varieties, Topology. Topology. An International Journal of Mathematics, 36, 335-353, (1997) · Zbl 0885.14025 · doi:10.1016/0040-9383(96)00016-X
[23] Gel{\cprime}fand, I. M.; MacPherson, R. D., A combinatorial formula for the {P}ontrjagin classes, Bull. Amer. Math. Soc. (N.S.). American Mathematical Society. Bulletin. New Series, 26, 304-309, (1992) · Zbl 0756.57015 · doi:10.1090/S0273-0979-1992-00282-3
[24] Goresky, Mark; MacPherson, Robert, Stratified {M}orse {T}heory, Ergeb. Math. Grenzgeb., 14, xiv+272 pp., (1988) · Zbl 0639.14012 · doi:10.1007/978-3-642-71714-7
[25] Gibney, Angela; Maclagan, Diane, Lower and upper bounds on nef cones, Inter. Math. Res. Not. IMRN, 3224-3255, (2012) · Zbl 1284.14020 · doi:10.1093/imrn/rnr121
[26] Heron, A. P., Matroid polynomials. Combinatorics ({P}roc. {C}onf. {C}ombinatorial {M}ath., {M}ath. {I}nst., {O}xford, 1972), 164-202, (1972)
[27] Hoggar, S. G., Chromatic polynomials and logarithmic concavity, J. Combinatorial Theory Ser. B. Journal of Combinatorial Theory. Series B, 16, 248-254, (1974) · Zbl 0268.05104 · doi:10.1016/0095-8956(74)90071-9
[28] Huh, June, Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, J. Amer. Math. Soc.. Journal of the American Mathematical Society, 25, 907-927, (2012) · Zbl 1243.14005 · doi:10.1090/S0894-0347-2012-00731-0
[29] Huh, June; Katz, Eric, Log-concavity of characteristic polynomials and the {B}ergman fan of matroids, Math. Ann.. Mathematische Annalen, 354, 1103-1116, (2012) · Zbl 1258.05021 · doi:10.1007/s00208-011-0777-6
[30] Hrushovski, Ehud, Unimodular minimal structures, J. London Math. Soc. (2). Journal of the London Mathematical Society. Second Series, 46, 385-396, (1992) · Zbl 0761.05008 · doi:10.1112/jlms/s2-46.3.385
[31] Itenberg, Ilya; Katzarkov, Ludmil; Mikhalkin, Grigory; Zharkov, Ilya, Tropical homology, (2016) · Zbl 1460.14146
[32] Jacobson, Nathan, Basic Algebra I, Second edition, (1985) · Zbl 0557.16001
[33] Katz, Eric; Payne, Sam, Realization spaces for tropical fans. Combinatorial Aspects of Commutative Algebra and Algebraic Geometry, Abel Symp., 6, 73-88, (2011) · Zbl 1248.14066 · doi:10.1007/978-3-642-19492-4_6
[34] Kozlov, Dmitry, Combinatorial Algebraic Topology, Algorithms Comput. Math., 21, xx+389 pp., (2008) · Zbl 1157.57300 · doi:10.1007/978-3-540-71962-5
[35] Kung, Joseph P. S., A Source Book in Matroid Theory. with a foreword by Gian-Carlo Rota, 413 pp., (1986) · Zbl 0597.05019 · doi:10.1007/978-1-4684-9199-9
[36] Kung, Joseph P. S., The geometric approach to matroid theory. Gian-{C}arlo {R}ota on Combinatorics, Contemp. Mathematicians, 604-622, (1995)
[37] Lazarsfeld, Robert, Positivity in Algebraic Geometry. {II}. Positivity for Vector Bundles, and Multiplier Ideals, Ergeb. Math. Grenzgeb., 49, xviii+385 pp., (2004) · Zbl 1093.14500 · doi:10.1007/978-3-642-18810-7
[38] Lee, C. W., P.{L}.-spheres, convex polytopes, and stress, Discrete Comput. Geom.. Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science, 15, 389-421, (1996) · Zbl 0856.52009 · doi:10.1007/BF02711516
[39] Lenz, Matthias, The {\(f\)}-vector of a representable-matroid complex is log-concave, Adv. in Appl. Math.. Advances in Applied Mathematics, 51, 543-545, (2013) · Zbl 1301.05382 · doi:10.1016/j.aam.2013.07.001
[40] Mason, J. H., Matroids: unimodal conjectures and {M}otzkin’s theorem. Combinatorics, 207-220, (1972)
[41] McDaniel, Chris, The strong {L}efschetz property for coinvariant rings of finite reflection groups, J. Algebra. Journal of Algebra, 331, 68-95, (2011) · Zbl 1244.13005 · doi:10.1016/j.jalgebra.2010.11.007
[42] McMullen, Peter, The polytope algebra, Adv. Math.. Advances in Mathematics, 78, 76-130, (1989) · Zbl 0686.52005 · doi:10.1016/0001-8708(89)90029-7
[43] McMullen, Peter, On simple polytopes, Invent. Math.. Inventiones Mathematicae, 113, 419-444, (1993) · Zbl 0803.52007 · doi:10.1007/BF01244313
[44] McMullen, P., Weights on polytopes, Discrete Comput. Geom.. Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science, 15, 363-388, (1996) · Zbl 0849.52011 · doi:10.1007/BF02711515
[45] Meyer, Dagmar M.; Smith, Larry, Poincar\'e Duality Algebras, {M}acaulay’s Dual Systems, and {S}teenrod Operations, Cambridge Tracts in Math., 167, viii+193 pp., (2005) · Zbl 1083.13003 · doi:10.1017/CBO9780511542855
[46] Miller, Ezra; Sturmfels, Bernd, Combinatorial Commutative Algebra, Grad. Texts in Math., 227, xiv+417 pp., (2005) · Zbl 1066.13001 · doi:10.1007/b138602
[47] von Neumann, John, Continuous Geometry, Princeton Landmarks in Mathematics, xiv+299 pp., (1998) · Zbl 0919.51002 · doi:10.1515/9781400883950
[48] Oda, Tadao, Convex Bodies and Algebraic Geometry, Ergeb. Math. Grenzgeb., 15, viii+212 pp., (1988) · Zbl 0628.52002
[49] Orlik, Peter; Terao, Hiroaki, Arrangements of Hyperplanes, Grundlehren Math. Wiss., 300, xviii+325 pp., (1992) · Zbl 0757.55001 · doi:10.1007/978-3-662-02772-1
[50] Oxley, James G., Matroid Theory, Oxford Sci. Publ., xii+532 pp., (1992) · Zbl 0784.05002
[51] Pillay, Anand, Geometric Stability Theory, Oxford Logic Guides, 32, x+361 pp., (1996) · Zbl 0871.03023
[52] Read, Ronald C., An introduction to chromatic polynomials, J. Combinatorial Theory, 4, 52-71, (1968) · Zbl 0173.26203
[53] Rota, Gian-Carlo, On the foundations of combinatorial theory. {I}. {T}heory of {M}\"obius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 2, 340-368, (1964) · Zbl 0121.02406 · doi:10.1007/BF00531932
[54] Rota, Gian-Carlo, Combinatorial theory, old and new. Actes du {C}ongr\`“‘es {I}nternational des {M}ath\'”’ematiciens. {T}ome 3, 229-233, (1971) · Zbl 0362.05044
[55] Stanley, Richard P., An introduction to hyperplane arrangements. Geometric Combinatorics, IAS/Park City Math. Ser., 13, 389-496, (2007) · Zbl 1136.52009
[56] Welsh, D. J. A., Combinatorial problems in matroid theory. Combinatorial {M}athematics and its {A}pplications, 291-306, (1971) · Zbl 0233.05001
[57] Welsh, D. J. A., Matroid Theory, L. M. S. Monographs, No. 8, xi+433 pp., (1976) · Zbl 0343.05002
[58] White, Neil, Combinatorial Geometries, Encyclopedia Math. Appl., 29, (1987) · Zbl 0626.00007 · doi:10.1017/CBO9781107325715
[59] Whitney, Hassler, A logical expansion in mathematics, Bull. Amer. Math. Soc.. Bulletin of the American Mathematical Society, 38, 572-579, (1932) · JFM 58.0647.19 · doi:10.1090/S0002-9904-1932-05460-X
[60] Whitney, Hassler, On the abstract properties of linear dependence, Amer. J. Math.. American Journal of Mathematics, 57, 509-533, (1935) · JFM 61.0073.03 · doi:10.2307/2371182
[61] Zaslavsky, Thomas, The {M}\"obius function and the characteristic polynomial. Combinatorial Geometries, Encyclopedia Math. Appl., 29, 114-138, (1987) · Zbl 0632.05017 · doi:10.1017/CBO9781107325715.009
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.