Abstract
We study the harmonic polytope, which arose in Ardila, Denham, and Huh’s work on the Lagrangian geometry of matroids. We describe its combinatorial structure, showing that it is a \((2n-2)\)-dimensional polytope with \((n!)^2\left( 1+\frac{1}{2}+\cdots +\frac{1}{n}\right) \) vertices and \(3^n-3\) facets. We also give a formula for its volume: it is a weighted sum of the degrees of the projective varieties of all the toric ideals of connected bipartite graphs with n edges; or equivalently, a weighted sum of the lattice point counts of all the corresponding trimmed generalized permutahedra.
Similar content being viewed by others
Notes
Of course, this is the same information as the relative order of the \(z_i\)s. We use the reverse order because it is consistent with our choice of working with inner normal fans.
This should not be confused with the permutohedron, which makes no further appearances in the paper.
References
Adiprasito, K., Huh, J., Katz, E.: Hodge theory for combinatorial geometries. Ann. Math. (2) 188(2), 381–452 (2018)
Ardila, F.: The geometry of matroids. Notices Am. Math. Soc. 65(8), 902–908 (2018)
Ardila, F.: The bipermutahedron. arXiv:2008.02295
Ardila, F., Denham, G., Huh, J.: Lagrangian geometry of matroids. arXiv:2004.13116
Ardila, F., Denham, G., Huh, J.: Lagrangian combinatorics of matroids. In preparation (2021)
Ardila, F., Klivans, C.J.: The Bergman complex of a matroid and phylogenetic trees. J. Comb. Theory Ser. B 96(1), 38–49 (2006)
Bárány, I., Füredi, Z.: Computing the volume is difficult. Discrete Comput. Geom. 2(4), 319–326 (1987)
Bernstein, D.N.: The number of roots of a system of equations. Funkcional. Anal. i Priložen. 9(3), 1–4 (1975)
Billera, L.J.: The algebra of continuous piecewise polynomials. Adv. Math. 76(2), 170–183 (1989)
Brion, M.: Piecewise polynomial functions, convex polytopes and enumerative geometry. In: Parameter Spaces (Warsaw, 1994), Banach Center Publ., vol. 36, pp. 25–44. Polish Acad. Sci. Inst. Math., Warsaw (1996)
Brylawski, T.: The Tutte polynomial part I: general theory. In: Matroid Theory and Its Applications, Volume 83 of C.I.M.E. Summer Sch., pp. 125–275. Springer, Heidelberg (2010)
Cox, D.A., Little, J.B., Schenck, H.K.: Toric Varieties, Volume 124 of Graduate Studies in Mathematics. American Mathematical Society, Providence (2011)
de Medrano, L.L., Rincón, F., Shaw, K.: Chern–Schwartz–MacPherson cycles of matroids. Proc. Lond. Math. Soc. (3) 120(1), 1–27 (2020)
Dawson, J.E.: A collection of sets related to the Tutte polynomial of a matroid. In: Graph Theory, Singapore 1983, Volume 1073 of Lecture Notes in Math., pp. 193–204. Springer, Berlin (1984)
Dyer, M.E.: The complexity of vertex enumeration methods. Math. Oper. Res. 8(3), 381–402 (1983)
Dyer, M.E., Frieze, A.M.: On the complexity of computing the volume of a polyhedron. SIAM J. Comput. 17(5), 967–974 (1988)
Feichtner, E.M., Yuzvinsky, S.: Chow rings of toric varieties defined by atomic lattices. Invent. Math. 155(3), 515–536 (2004)
Herzog, J., Hibi, T., Ohsugi, H.: Binomial Ideals, Volume 279 of Graduate Texts in Mathematics. Springer, Cham (2018)
Huh, J., Katz, E.: Log-concavity of characteristic polynomials and the Bergman fan of matroids. Math. Ann. 354(3), 1103–1116 (2012)
Huh, J.: Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs. J. Am. Math. Soc. 25(3), 907–927 (2012)
Huh, J.: h-vectors of matroids and logarithmic concavity. Adv. Math. 270, 49–59 (2015)
Linial, N.: Hard enumeration problems in geometry and combinatorics. SIAM J. Algebr. Discrete Methods 7(2), 331–335 (1986)
MacPherson, R.D.: Chern classes for singular algebraic varieties. Ann. Math. 2(100), 423–432 (1974)
McMullen, P.: Valuations and Euler-type relations on certain classes of convex polytopes. Proc. Lond. Math. Soc. (3) 35(1), 113–135 (1977)
Postnikov, A.: Permutohedra, associahedra, and beyond. Int. Math. Res. Notices (IMRN) 6, 1026–1106 (2009)
Stanley, R.P.: Enumerative Combinatorics. Volume 1, Volume 49 of Cambridge Studies in Advanced Mathematics, 2nd edn. Cambridge University Press, Cambridge (2012)
Sabbah, C.: Quelques remarques sur la géométrie des espaces conormaux. Number 130, pp. 161–192. 1985. Differential systems and singularities (Luminy, 1983)
Schwartz, M.-H.: Classes caractéristiques définies par une stratification d’une variété analytique complexe. I. C. R. Acad. Sci. Paris 260, 3262–3264 (1965)
Simis, A., Vasconcelos, W.V., Villarreal, R.H.: On the ideal theory of graphs. J. Algebra 167(2), 389–416 (1994)
Sturmfels, B.: Gröbner Bases and Convex Polytopes, Volume 8 of University Lecture Series. American Mathematical Society, Providence (1996)
Villarreal, R.H.: Rees algebras of edge ideals. Commun. Algebra 23(9), 3513–3524 (1995)
Ziegler, G.M.: Lectures on Polytopes, Volume 152 of Graduate Texts in Mathematics. Springer, New York (1995)
Acknowledgements
The first author would like to thank Graham Denham and June Huh for the very rewarding collaboration that led to the construction of the harmonic polytope. We would like to thank the anonymous referees for their careful reading of the work and their valuable suggestions to improve the exposition.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
F. Ardila: Partially supported by NSF Grant DMS-1855610 and Simons Fellowship 613384. L. Escobar: Partially supported by NSF Grant DMS-1855598.