Roots of Ehrhart polynomials arising from graphs
Tetsushi Matsui
, Akihiro Higashitani
, Yuuki Nagazawa
, Hidefumi Ohsugi
and Takayuki Hibi5
5Received: 30 April 2010 / Accepted: 13 April 2011 / Published online: 4 May 2011 \copyright Springer Science+Business Media, LLC 2011 Abstract Several polytopes arise from finite graphs. For edge and symmetric edge polytopes, in particular, exhaustive computation of the Ehrhart polynomials not merely supports the conjecture of Beck et al. that all roots lpha of Ehrhart polynomials of polytopes of dimension D satisfy - D \leq Re(lpha ) \leq D - 1, but also reveals some interesting phenomena for each type of polytope. Here we present two new conjectures: (1) the roots of the Ehrhart polynomial of an edge polytope for a complete multipartite graph of order d lie in the circle |z + d | \leq d or are negative integers, 4 4 and (2) a Gorenstein Fano polytope of dimension D has the roots of its Ehrhart polynomial in the narrower strip - D \leq Re(lpha ) \leq D - 1. Some rigorous results to sup- 2 2 T. Matsui \cdot A. Higashitani ( ) \cdot Y. Nagazawa \cdot T. Hibi Department of Pure and Applied Mathematics, Graduate School of Information Science and Technology, Osaka University, Toyonaka, Osaka 560-0043, Japan
DOI: 10.1007/s10801-011-0290-8
Abstract
Several polytopes arise from finite graphs. For edge and symmetric edge polytopes, in particular, exhaustive computation of the Ehrhart polynomials not merely supports the conjecture of Beck et al. that all roots α of Ehrhart polynomials of polytopes of dimension D satisfy - D\leq Re( α )\leq D - 1, but also reveals some interesting phenomena for each type of polytope. Here we present two new conjectures: (1) the roots of the Ehrhart polynomial of an edge polytope for a complete multipartite graph of order d lie in the circle | z+\frac d4 | \sterling \frac d4 |z+\frac{d}{4}| \le \frac{d}{4} or are negative integers, and (2) a Gorenstein Fano polytope of dimension D has the roots of its Ehrhart polynomial in the narrower strip -\frac D2 \sterling Re( a) \sterling \frac D2 -1 -\frac{D}{2} \leq \mathrm{Re}(α) \leq \frac{D}{2}-1. Some rigorous results to support them are obtained as well as for the original conjecture. The root distribution of Ehrhart polynomials of each type of polytope is plotted in figures.
Pages: 721–749
Keywords: keywords Ehrhart polynomial; edge polytope; Fano polytope; smooth polytope
Full Text: PDF
References
1. Ardila, F., Beck, M., Ho\?sten, S., Pfeifle, J., Seashore, K.: Root polytopes and growth series of root lattices. SIAM J. Discrete Math. 25, 360-378 (2011)
2. Batyrev, V.: Dual polyhedra and mirror symmetry for Calabi-Yau hypersurfaces in toric varieties. J. Algebr. Geom. 3, 493-535 (1994)
3. Beck, M., De Loera, J.A., Develin, M., Pfeifle, J., Stanley, R.P.: Coefficients and roots of Ehrhart polynomials. Contemp. Math. 374, 15-36 (2005).
4. Bey, C., Henk, M., Wills, J.M.: Notes on the roots of Ehrhart polynomials. Discrete Comput. Geom. 38, 81-98 (2007)
5. Braun, B.: Norm bounds for Ehrhart polynomial roots. Discrete Comput. Geom. 39, 191-193 (2008)
6. Braun, B., Develin, M.: Ehrhart polynomial roots and Stanley's non-negativity theorem. Contemp. Math. 452, 67-78 (2008).
7. CoCoATeam. CoCoA: a system for doing Computations in Commutative Algebra.
8. Cook, D. II: Nauty in Macaulay2. [math]
9. De Loera, J.A., Haws, D., Hemmecke, R., Huggins, P., Tauzer, J., Yoshida, R.: LattE.
10. Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation, pp. 43-74. Birkhäuser, Basel (2000)
11. Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
12. Harary, F., Palmer, E.M.: Graphical Enumeration. Academic Press, New York (1973)
13. Henk, M., Schürmann, A., Wills, J.M.: Ehrhart polynomials and successive minima. Mathematika 52, 1-16 (2005)
14. Hibi, T.: Algebraic Combinatorics of Convex Polytopes. Carslaw Publications, Glebe (1992)
15. Hibi, T.: Dual polytopes of rational convex polytopes. Combinatorica 12, 237-240 (1992)
16. Hibi, T.: A lower bound theorem for Ehrhart polynomials of convex polytopes. Adv. Math. 105, 162- 165 (1994)
17. Köppe, M.: LattE macchiato.
18. Matsui, T.: Development of NZMATH. In: Iglesias, A., Takayama, N. (eds.) Mathematical Software- ICMS
2006. Lecture Notes in Computer Science, vol. 4151, pp. 158-169. Springer, Berlin (2006)
19. Maxima.sourceforge.net. Maxima, a computer algebra system.
20. NZMATH development group. NZMATH.
21. Ohsugi, H., Hibi, T.: Normal polytopes arising from finite graphs. J. Algebra 207, 409-426 (1998)
22. Ohsugi, H., Hibi, T.: Compressed polytopes, initial ideals and complete multipartite graphs. Ill. J.
2. Batyrev, V.: Dual polyhedra and mirror symmetry for Calabi-Yau hypersurfaces in toric varieties. J. Algebr. Geom. 3, 493-535 (1994)
3. Beck, M., De Loera, J.A., Develin, M., Pfeifle, J., Stanley, R.P.: Coefficients and roots of Ehrhart polynomials. Contemp. Math. 374, 15-36 (2005).
4. Bey, C., Henk, M., Wills, J.M.: Notes on the roots of Ehrhart polynomials. Discrete Comput. Geom. 38, 81-98 (2007)
5. Braun, B.: Norm bounds for Ehrhart polynomial roots. Discrete Comput. Geom. 39, 191-193 (2008)
6. Braun, B., Develin, M.: Ehrhart polynomial roots and Stanley's non-negativity theorem. Contemp. Math. 452, 67-78 (2008).
7. CoCoATeam. CoCoA: a system for doing Computations in Commutative Algebra.
8. Cook, D. II: Nauty in Macaulay2. [math]
9. De Loera, J.A., Haws, D., Hemmecke, R., Huggins, P., Tauzer, J., Yoshida, R.: LattE.
10. Gawrilow, E., Joswig, M.: Polymake: a framework for analyzing convex polytopes. In: Kalai, G., Ziegler, G.M. (eds.) Polytopes-Combinatorics and Computation, pp. 43-74. Birkhäuser, Basel (2000)
11. Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
12. Harary, F., Palmer, E.M.: Graphical Enumeration. Academic Press, New York (1973)
13. Henk, M., Schürmann, A., Wills, J.M.: Ehrhart polynomials and successive minima. Mathematika 52, 1-16 (2005)
14. Hibi, T.: Algebraic Combinatorics of Convex Polytopes. Carslaw Publications, Glebe (1992)
15. Hibi, T.: Dual polytopes of rational convex polytopes. Combinatorica 12, 237-240 (1992)
16. Hibi, T.: A lower bound theorem for Ehrhart polynomials of convex polytopes. Adv. Math. 105, 162- 165 (1994)
17. Köppe, M.: LattE macchiato.
18. Matsui, T.: Development of NZMATH. In: Iglesias, A., Takayama, N. (eds.) Mathematical Software- ICMS
2006. Lecture Notes in Computer Science, vol. 4151, pp. 158-169. Springer, Berlin (2006)
19. Maxima.sourceforge.net. Maxima, a computer algebra system.
20. NZMATH development group. NZMATH.
21. Ohsugi, H., Hibi, T.: Normal polytopes arising from finite graphs. J. Algebra 207, 409-426 (1998)
22. Ohsugi, H., Hibi, T.: Compressed polytopes, initial ideals and complete multipartite graphs. Ill. J.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition