Bounds on the coefficients of tension and flow polynomials
Felix Breuer
and Aaron Dall
DOI: 10.1007/s10801-010-0254-4
Abstract
The goal of this article is to obtain bounds on the coefficients of modular and integral flow and tension polynomials of graphs. To this end we use the fact that these polynomials can be realized as Ehrhart polynomials of inside-out polytopes. Inside-out polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polynomials.
Pages: 465–482
Keywords: keywords Ehrhart polynomial; inside-out polytope; convex ear decomposition; regular subdivision; polytopal complex; $M$-vector
Full Text: PDF
References
1. Beck, M., Robins, S.: Computing the Continuous Discretely. Undergraduate Texts in Mathematics. Springer, New York (2007)
2. Beck, M., Zaslavsky, T.: Inside-out polytopes. Adv. Math. 205(1), 134-162 (2006)
3. Beck, M., Zaslavsky, T.: The number of nowhere-zero flows on graphs and signed graphs. J. Comb. Theory Ser. B 96(6), 901-918 (2006)
4. Billera, L.J., Björner, A.: Face Numbers of Polytopes and Complexes, 2nd edn., pp. 407-430. Chapman & Hall/CRC Press, London/Boca Raton (2004). Chap. 18 J Algebr Comb (2011) 33: 465-482
5. Breuer, F.: Ham sandwiches, staircases and counting polynomials. Ph.D. thesis, Freie Universität, Berlin (2009)
6. Breuer, F., Dall, A.: Viewing counting polynomials as Hilbert functions via Ehrhart theory. In: 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010). DMTCS, pp. 413-424 (2010)
7. Breuer, F., Sanyal, R.: Ehrhart theory, modular flow reciprocity, and the Tutte polynomial. (2009)
8. Bruns, W., Gubeladze, J.: Polytopes, Rings, and k-Theory. Springer Monographs in Mathematics. Springer, Berlin (2009)
9. Bruns, W., Römer, T.: h-Vectors of Gorenstein polytopes. J. Combin. Theory, Ser. A 114(1), 65-76 (2007)
10. Chari, M.K.: Two decompositions in topological combinatorics with applications to matroid complexes. Trans. Am. Math. Soc. 349(10), 3925-3943 (1997)
11. Chen, B.: Orientations, lattice polytopes, and group arrangements i: Chromatic and tension polynomials of graphs. Ann. Combin. 13(4), 425-452 (2010)
12. Dall, A.: The flow and tension complexes. Master's thesis, San Francisco State University (2008)
13. Felsner, S., Knauer, K.: Distributive lattices, polyhedra, and generalized flow. No- vember 2008
14. Haase, C., Paffenholz, A.: Quadratic Gröbner bases for smooth 3 \times 3 transportation polytopes. J. Al- gebraic Combin. 30(4), 477-489 (2009)
15. Hersh, P., Swartz, E.: Coloring complexes and arrangements. J. Algebraic Combin. 27(2), 205-214 (2008)
16. Hibi, T.: Dual polytopes of rational convex polytopes. Combinatorica 12(2), 237-240 (1992)
17. Hultman, A.: Link complexes of subspace arrangements. Eur. J. Combin. 28(3), 781-790 (2007)
18. Jonsson, J.: The topology of the coloring complex. J. Algebraic Combin. 21, 311-329 (2005)
19. Kochol, M.: Polynomials associated with nowhere-zero flows. J. Combin. Theory Ser. B 84(2), 260- 269 (2002)
20. Lee, C.W.: Subdivisions and Triangulations of Polytopes, 2nd edn., pp. 383-406. Chapman & Hall/CRC Press, London/Boca Raton (2004). Chap. 17
21. Ohsugi, H., Hibi, T.: Convex polytopes all of whose reverse lexicographic initial ideals are squarefree. Proc. Am. Math. Soc. 129(9), 2541-2546 (2001)
22. Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)
23. Sloane, N.J.A.: The on-line encyclopedia of integer sequences.
24. Stanley, R.P.: A monotonicity property of h-vectors and h* -vectors. Eur. J. Combin. 14(3), 251-258 (1993)
25. Stanley, R.P.: Combinatorics and Commutative Algebra, 2nd edn. Birkhäuser, Basel (1996)
26. Steingrímsson, E.: The coloring ideal and coloring complex of a graph. J. Algebraic Combin. 14, 73-84 (2001)
27. Sturmfels, B.: Gröbner Bases and Convex Polytopes. University Lecture Series, vol.
8. Am. Math.
2. Beck, M., Zaslavsky, T.: Inside-out polytopes. Adv. Math. 205(1), 134-162 (2006)
3. Beck, M., Zaslavsky, T.: The number of nowhere-zero flows on graphs and signed graphs. J. Comb. Theory Ser. B 96(6), 901-918 (2006)
4. Billera, L.J., Björner, A.: Face Numbers of Polytopes and Complexes, 2nd edn., pp. 407-430. Chapman & Hall/CRC Press, London/Boca Raton (2004). Chap. 18 J Algebr Comb (2011) 33: 465-482
5. Breuer, F.: Ham sandwiches, staircases and counting polynomials. Ph.D. thesis, Freie Universität, Berlin (2009)
6. Breuer, F., Dall, A.: Viewing counting polynomials as Hilbert functions via Ehrhart theory. In: 22nd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2010). DMTCS, pp. 413-424 (2010)
7. Breuer, F., Sanyal, R.: Ehrhart theory, modular flow reciprocity, and the Tutte polynomial. (2009)
8. Bruns, W., Gubeladze, J.: Polytopes, Rings, and k-Theory. Springer Monographs in Mathematics. Springer, Berlin (2009)
9. Bruns, W., Römer, T.: h-Vectors of Gorenstein polytopes. J. Combin. Theory, Ser. A 114(1), 65-76 (2007)
10. Chari, M.K.: Two decompositions in topological combinatorics with applications to matroid complexes. Trans. Am. Math. Soc. 349(10), 3925-3943 (1997)
11. Chen, B.: Orientations, lattice polytopes, and group arrangements i: Chromatic and tension polynomials of graphs. Ann. Combin. 13(4), 425-452 (2010)
12. Dall, A.: The flow and tension complexes. Master's thesis, San Francisco State University (2008)
13. Felsner, S., Knauer, K.: Distributive lattices, polyhedra, and generalized flow. No- vember 2008
14. Haase, C., Paffenholz, A.: Quadratic Gröbner bases for smooth 3 \times 3 transportation polytopes. J. Al- gebraic Combin. 30(4), 477-489 (2009)
15. Hersh, P., Swartz, E.: Coloring complexes and arrangements. J. Algebraic Combin. 27(2), 205-214 (2008)
16. Hibi, T.: Dual polytopes of rational convex polytopes. Combinatorica 12(2), 237-240 (1992)
17. Hultman, A.: Link complexes of subspace arrangements. Eur. J. Combin. 28(3), 781-790 (2007)
18. Jonsson, J.: The topology of the coloring complex. J. Algebraic Combin. 21, 311-329 (2005)
19. Kochol, M.: Polynomials associated with nowhere-zero flows. J. Combin. Theory Ser. B 84(2), 260- 269 (2002)
20. Lee, C.W.: Subdivisions and Triangulations of Polytopes, 2nd edn., pp. 383-406. Chapman & Hall/CRC Press, London/Boca Raton (2004). Chap. 17
21. Ohsugi, H., Hibi, T.: Convex polytopes all of whose reverse lexicographic initial ideals are squarefree. Proc. Am. Math. Soc. 129(9), 2541-2546 (2001)
22. Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics. Wiley, Chichester (1986)
23. Sloane, N.J.A.: The on-line encyclopedia of integer sequences.
24. Stanley, R.P.: A monotonicity property of h-vectors and h* -vectors. Eur. J. Combin. 14(3), 251-258 (1993)
25. Stanley, R.P.: Combinatorics and Commutative Algebra, 2nd edn. Birkhäuser, Basel (1996)
26. Steingrímsson, E.: The coloring ideal and coloring complex of a graph. J. Algebraic Combin. 14, 73-84 (2001)
27. Sturmfels, B.: Gröbner Bases and Convex Polytopes. University Lecture Series, vol.
8. Am. Math.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition