Abstract
A famous and wide-open problem, going back to at least the early 1970s, concerns the classification of chromatic polynomials of graphs. Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and we contribute such inequalities when a chromatic polynomial \(\chi _G(n)=\chi ^*_0\left( {\begin{array}{c}n+d\\ d\end{array}}\right) +\chi ^*_1\left( {\begin{array}{c}n+d-1\\ d\end{array}}\right) +\dots +\chi ^*_d\left( {\begin{array}{c}n\\ d\end{array}}\right) \) is written in terms of a binomial-coefficient basis. For example, we show that \(\chi ^*_j\le \chi ^*_{d-j}\), for \(0\le j\le d/2\). Similar results hold for flow and tension polynomials enumerating either modular or integral nowhere-zero flows/tensions of a graph. Our theorems follow from connections among chromatic, flow, tension, and order polynomials, as well as Ehrhart polynomials of lattice polytopes that admit unimodular triangulations. Our results use Ehrhart inequalities due to Athanasiadis and Stapledon and are related to recent work by Hersh–Swartz and Breuer–Dall, where inequalities similar to some of ours were derived using algebraic-combinatorial methods.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
A famous and wide-open problem, going back to at least [30], concerns the classification of chromatic polynomials of graphs. As is well known, for a given graph G, the number \(\chi _G(n)\) of proper colorings of G using n colors evaluates to a polynomial in n, and so a natural question is: which polynomials are chromatic?
Toward this classification problem, one may ask for necessary inequalities among the coefficients of a chromatic polynomial, and this paper gives one such set of inequalities. In enumerative combinatorics, there are three natural bases for the space of polynomials of degree at most d:
-
the monomials \(1, n, n^2, \dots , n^d\);
-
the binomial coefficients \(\left( {\begin{array}{c}n\\ d\end{array}}\right) , \left( {\begin{array}{c}n\\ d-1\end{array}}\right) , \dots , \left( {\begin{array}{c}n\\ 0\end{array}}\right) \);
-
the binomial coefficients \(\left( {\begin{array}{c}n+d\\ d\end{array}}\right) , \left( {\begin{array}{c}n+d-1\\ d\end{array}}\right) , \dots , \left( {\begin{array}{c}n\\ d\end{array}}\right) \).
It is well known that the coefficients of any chromatic polynomial in the monomial basis alternate in sign (this can be proved, e.g., by deletion–contraction), and that the coefficients in both binomial-coefficient bases are nonnegative (in the first case, this follows from considering proper colorings that use exactly k colors, for \(0 \le k \le d\), and this is closely connected to \(\sigma \)-polynomials [16]; in the second case, nonnegativity follows from Stanley’s work on order polynomials [23] and the natural decomposition of a chromatic polynomial into order polynomial—see (8) below; this was first spelled out in [19]).
We will work in the last basis and define the corresponding coefficients of the chromatic polynomial of a given graph G with d vertices via
We will collect the \(\chi ^*_j\)s in the polynomial \(\chi ^*_G(z) := \chi ^*_dz^d + \chi ^*_{ d-1 }z^{ d-1 } + \dots + \chi ^*_0\) (which might not have degree d) and note that this polynomial appears in the generating function of \(\chi _G(n)\), more precisely,
To the best of our knowledge, Linial [19] initiated the first study of the chromatic polynomial in the form of \(\chi ^*_G(z)\); see also [4, 9, 10, 28]. We think of the linear transformation going from \(\chi _G(n)\) to \(\chi ^*_G(z)\) as a tool that is useful beyond chromatic polynomials (in fact, as we will see below, it is a standard tool in Ehrhart theory), and so we suggest to call \(\chi ^*_G(z)\) the binomial transform of \(\chi _G(n)\).
The strongest known conditions on the coefficientsFootnote 1 of \(\chi ^*_G(z)\) are due to Hersh and Swartz [12, Thm. 15]: Defining \(h_0,h_1,\dots , h_d\) via
they proved that
from which one can now deduce inequalities for the \(\chi ^*_j\)s involving Eulerian numbers.
The natural dual situation concerns flows on a graph. Denote by \(\mathrm {H}= (\eta _{ v,e }) \in \{ 0, \pm 1 \}^{ V \times E } \) the signed incidence matrix of \(G = (V, E)\), i.e.,
where we equipped G with an (arbitrary but fixed) orientation. Let A be an Abelian group. A nowhere-zero A-flow on G is a mapping \(x:E\rightarrow A\setminus \{0 \}\) that is in the kernel of \(\mathrm {H}\). (See, e.g., [13, 22] for background on nowhere-zero flows.) Tutte [29] proved in 1947 that the number \(\phi _G(n)\) of nowhere-zero \({\mathbb {Z}}_n\)-flows on G is a polynomial in n. A more recent theorem of Kochol [14] says that the number \(f_G(n)\) of nowhere-zero \({\mathbb {Z}}\)-flows on G whose images satisfy \(|x(e)| < n\) is also a polynomial in n. (It is easy to see that both flow polynomials are independent of the chosen orientation.) While it has long been known that \(\phi _G(n)\) and \(f_G(n)\) have identical integer roots, they are rather different polynomials.
A nowhere-zero A-tension on G is a mapping \(x:E \rightarrow A \setminus \{ 0 \}\) that is in the row space of \(\mathrm {H}\). It is not hard to see that the number of nowhere-zero \({\mathbb {Z}}_n\)-tensions on G equals \(\chi _G(n)/n^c\) where c denotes the number of components of G. The situation for integer tensions is more interesting: Kochol [15] proved that the number \(t_G(n)\) of nowhere-zero \({\mathbb {Z}}\)-tensions on G with \(|x(e)|<n\) is a polynomial in n (which is quite different from \(\chi _G(n)\)).
As with the chromatic polynomials, we will express \(\phi _G(n)\), \(f_G(n)\), and \(t_G(z)\) in a binomial-coefficient basis (namely, \(\left( {\begin{array}{c}n+\xi \\ \xi \end{array}}\right) , \left( {\begin{array}{c}n+\xi -1\\ \xi \end{array}}\right) , \dots , \left( {\begin{array}{c}n\\ \xi \end{array}}\right) \)) and define their binomial transforms viaFootnote 2
where c denotes the number of components of G and \(\xi := |E| - d + c\) is the cyclomatic number of G.
Similarly to the chromatic situation, it is known [6, 14, 15] that the coefficients of \(\phi ^*_G (z)\), \(f^*_G(z)\), and \(t^*_G (z)\) are nonnegative. Breuer and Dall [5] proved the \({\mathbb {Z}}_n\)-flow analogues of the above-mentioned inequalities by Hersh and Swartz: Defining \(h_0, h_1, \dots , h_\xi \) via
we have
and again, from these one can deduce inequalities for the coefficients of \(\phi ^*_G(z)\) involving Eulerian numbers. Breuer and Dall gave some constraints also for \(f^*_G(z)\) and \(t^*_G(z)\) but these were not as clearly cut as for \(\phi ^*_G(z)\).
Our goal is to show how one can derive theorems similar to those by Hersh–Swartz and Breuer–Dall (including inequalities for \(f^*_G(n)\) and \(t^*_G(z)\)) through a discrete geometric setup. Our main result is as follows.
Theorem 1.1
Let G be a graph on d vertices with c components and cyclomatic number \(\xi \). Then
It is clear (though the details need some work) that the inequalities for \(\chi _G^*\) and \(\phi _G^*\) are closely related to the work of Hersh–Swartz and Breuer–Dall. At any rate, the methods in [5, 12] are from algebraic combinatorics: one constructs a simplicial complex whose h-vector satisfies certain inequalities (stemming from a convex-ear decomposition). Our approach, by contrast, is through Ehrhart polynomials of lattice polytopes, which we discuss in Sect. 2. A small subclass of lattice polytopes admit unimodular triangulations, and for this subclass, Athanasiadis [1] and Stapledon [27] proved inequalities for the binomial transforms of Ehrhart polynomials similar in spirit to Theorem 1.1.
While chromatic polynomials are not Ehrhart polynomials, they can be written as sums of order polynomials (by the afore-mentioned work of Stanley [23]), which we study in Sect. 3. Order polynomials, in turn, are Ehrhart polynomials in disguise, and so here is where we apply the Athanasiadis–Stapledon inequalities (with some tweaking); Theorem 3.1 below might be of interest on its own account.
The flow and tension inequalities in Theorem 1.1 follow in a similar fashion from writing the (two kinds of) flow and tension polynomials as sums of Ehrhart polynomials (and then using the Athanasiadis–Stapledon inequalities), as we illustrate in Sect. 4. For integral flows and tensions, this geometric setup was introduced by Kochol [14, 15], whereas for modular flows it is due to Breuer–Sanyal [6].
The underlying theme here is that one can interpret graph polynomials as certain combinations of Ehrhart polynomials of very nice polytopes (ones that admit unimodular triangulations), and thus these Ehrhart polynomials satisfy certain linear constraints, which then can be translated back into constraints for the graph polynomials.
2 Ehrhart theory and \(h^*\)-inequalities
Given a lattice polytope \({\mathscr {P}}\subset {\mathbb {R}}^d\), i.e., the convex hull of finitely many points in \({\mathbb {Z}}^d\), Ehrhart’s celebrated theorem [8] says that the counting function
for \(n \in {\mathbb {Z}}_{ >0 }\) extends to a polynomial in n of degree \(\dim {\mathscr {P}}\). (See, e.g., [2] for background on Ehrhart theory.) We will assume throughout that \({\mathscr {P}}\) is full dimensional, and so the degree of \({\text {ehr}}_{\mathscr {P}}(n)\) is d. An equivalent formulation of Ehrhart’s theorem is that the Ehrhart series \(1 + \sum _{ n \ge 1 } {\text {ehr}}_{\mathscr {P}}(n) \, z^n\) evaluates to a rational function of the form \({ h_{\mathscr {P}}^*(z)/(1-z)^{ d+1 } }\) for some polynomial \(h_{\mathscr {P}}^*(z)\) of degree \(s \le d\), the \(h^*\)-polynomial of \({\mathscr {P}}\)—a name for the binomial transform of an Ehrhart polynomial that has become somewhat of a standard. We are interested in (linear) constraints among the \(h^*\)-coefficients. Stanley [24] proved that the coefficients of \(h_{\mathscr {P}}^*(z)\) are nonnegative integers. We will use below the fact that the coefficient of \(z^d\) equals the number of interior lattice points of \({\mathscr {P}}\), and the constant term equals 1.
The Ehrhart–Macdonald reciprocity theorem [20] gives the algebraic relation
where \({\mathscr {P}}^\circ \) denotes the interior of \({\mathscr {P}}\). An equivalent version is
where the \(h^*\)-polynomial of \({\mathscr {P}}^\circ \) is defined through
Note that the degree of \(h^*_{ {\mathscr {P}}^\circ } (z)\) equals \(d+1\).
A triangulation of a d-dimensional polytope \({\mathscr {P}}\) is a collection of simplices such that their union is \({\mathscr {P}}\) and the intersection of two simplices is a face of both. (See, e.g., [7] for background on triangulations.) A triangulation of \({\mathscr {P}}\) is unimodular if all simplices have integer vertices and (minimal) volume 1/d!. A triangulation T comes with an f-polynomial
where \(f_j\) counts the number of j-dimensional faces of T (and we set \(f_{-1}=1\) for the empty face). We further define the h-polynomial of T to be
If \({\mathscr {P}}\) has a unimodular triangulation T, it is well known (see, e.g., [2, Chap. 10]) that the \(h^*\)-polynomial of \({\mathscr {P}}\) equals the h-polynomial of T.
Athanasiadis [1, Thm. 1.3] proved that, if \({\mathscr {P}}\) is a d-dimensional lattice polytope that admits a regular unimodular triangulation, then
Athanasiadis remarked in [1] that these inequalities had been independently proved by Hibi and Stanley (unpublished). Stapledon [27, Thm. 2.20] showed that (3) holds under the (weaker) assumption that the boundary of \({\mathscr {P}}\) admits a regular unimodular triangulation. Under the same condition, Stapledon proved that
We remark that Stapledon derived (3) and (5) from a broad set of \(h^*\)-inequalities, extending previous work of Betke–McMullen [3] and Payne [21].
3 Order and Chromatic Polynomials
Given a finite poset \((\varPi , \preceq )\) with \(|\varPi | = d\), the order polynomial \(\varOmega _\varPi ^\circ (n)\) counts all strictly order-preserving maps from \(\varPi \) to \([n] := \{ 1, 2, \dots , n \}\), i.e.,
Order polynomials first surfaced in [23]; we will encode them via
(See, e.g., [26] for background on posets and order polynomials.) Order polynomials are Ehrhart polynomials in disguise. We define the order polytope of \(\varPi \) as
This much-studied subpolytope of the unit cube in \({\mathbb {R}}^\varPi \) was introduced in [25]. From its definition we deduce that
This implies \(\varOmega ^*_\varPi (z) =h^*_{ {\mathscr {O}}^\circ } (z)/z = z^d h^*_{\mathscr {O}}(1/z)\), i.e.,
where the numbers on the right-hand side are the coefficients of \(h^*_{\mathscr {O}}(z)\). Note that \(\varOmega ^*_0 = h^*_d = 0\) (because \({\mathscr {O}}\) contains no interior lattice points) and \(\varOmega ^*_d = h^*_0 = 1\).
Theorem 3.1
Let \(\varPi \) be a poset on d elements and, as above, denote the binomial transform of its order polynomial by \(\varOmega ^*_\varPi (z) = \varOmega ^*_d z^d +\varOmega ^*_{ d-1 } z^{ d-1 } +\dots + \varOmega ^*_1 z\). Then
Proof
Let \(\mu :{\mathbb {R}}^d \rightarrow H_0 := \{ {\mathbf {x}}\in {\mathbb {R}}^d :x_1 + x_2 + \dots + x_d = 0\}\) be an orthogonal projection, and let L be the lattice in \(H_0\) generated by \(\mu ({\mathbf {e}}_1), \dots , \mu ({\mathbf {e}}_{d-1})\), i.e., \(L = \mu ({\mathbb {Z}}^d)\), and \(\mu ({\mathbf {e}}_d)=-\mu ({\mathbf {e}}_1) - \dots - \mu ({\mathbf {e}}_{ d-1 })\).
We claim that the order polytope \({\mathscr {O}}\) of \(\varPi \) and \(\mu ({\mathscr {O}})\) have the same \(h^*\)-polynomial. To see this, consider the canonical unimodular triangulation T of \({\mathscr {O}}\), using the hyperplanes \(x_j=x_k\). The image of each simplex \(\varDelta \in T\) under the projection \(\mu \) is a unimodular simplex in \(H_0\) (with respect to L), and the vertices \((0,\dots ,0)\) and \((1,\dots ,1)\) both get projected to the origin. This gives a unimodular triangulation \(T_\mu \) of \(\mu ({\mathscr {O}})\), and T is combinatorially a cone over \(T_\mu \); in particular, the f-vectors of T and \(T_\mu \) are related via
Because both triangulations are unimodular,Footnote 3
The coefficients of \(h^*_{ \mu ({\mathscr {O}}) } (z)\) satisfy the Athanasiadis–Stapledon inequalities (2)–(5), with d replaced by \(d-1\). Via (6), all the inequalities from the theorem follow and this finishes our proof. \(\square \)
Proof of the first two sets of inequalities in Theorem 1.1
Let A(G) be the set of all acyclic orientations of G.Footnote 4 Then the chromatic polynomial \(\chi _G(n)\) of G decomposes naturally into order polynomials as
Here we identify an acyclic orientation \(\varPi \) with its corresponding poset. (In this language, it is quite natural to think of \(\varOmega _\varPi ^\circ (n)\) as the chromatic polynomial of the digraph \(\varPi \).) Because every \(\varPi \in A(G)\) has d elements,
and so the first two sets of inequalities in Theorem 1.1 follow from Theorem 3.1. \(\square \)
4 Flow and Tension Polynomials
The inequalities for the coefficients of \(\phi ^*_G (z)\), \(f^*_G (z)\), and \(t^*_G (z)\) are proved in a similar way, except that now we do not have the luxury of the dimension reduction exhibited in the proof of Theorem 3.1.
Proof of the remaining inequalities in Theorem 1.1
We start by showing that each of \(\phi ^*_G (z)\), \(f^*_G (z)\), and \(t^*_G (z)\) is the sum of \(h^*\)-polynomials of open polytopes of the same dimension. (By an open polytope we simply mean the interior of a polytope.)
-
For \({\mathbb {Z}}_n\)-flows we use [6, Prop. 2.3], which expresses \(\phi _G(n)\) as a sum of Ehrhart polynomials of certain open polytopes, all of which have dimension \(\xi \). (Briefly, one replaces the flow equations over \({\mathbb {Z}}_n\) by a set of affine equations over \({\mathbb {R}}\), in which n now acts as a dilation parameter.) Thus \(\phi ^*_G(z)\) is a sum of \(h^*\)-polynomials of open polytopes of dimension \(\xi \).
-
For integer flows, we write, as in the proof of [14, Thm. 1],
$$\begin{aligned} f_G(n) \,= \sum _{ \varPi \in T(G) } p_\varPi (n), \end{aligned}$$where T(G) is the set of all totally cyclic orientations of G,Footnote 5 and \(p_\varPi (n)\) counts the \({\mathbb {Z}}\)-flows x on \(\varPi \) whose images satisfy \(0< x(e) < n\). As noted in [14], \(p_\varPi (n)\) is the Ehrhart polynomial of an open polytope with dimension \(\xi \), and so \(f^*_G(z)\) is a sum of \(h^*\)-polynomials of open polytopes.
-
Similarly, for integer tensions, we use [15, Sect. 4] to write
$$\begin{aligned} t_G(n) \, = \sum _{ \varPi \in A(G) } u_\varPi (n), \end{aligned}$$where, as above, A(G) is the set of all acyclic orientations of G, and \(u_\varPi (n)\) counts the \({\mathbb {Z}}\)-tensions x on \(\varPi \) with \(0<x(e)<n\). By [15], \(u_\varPi (n)\) is the Ehrhart polynomial of an open polytope with dimension \(d-c\), and so \(t^*_G(z)\) is a sum of \(h^*\)-polynomials of open polytopes.
In each of the above three cases, the polytopes in the decomposition admit regular unimodular triangulations (see, e.g., [5, 11]), so we can apply (2)–(5) and these inequalities will then extend linearly to the coefficients of \(\phi ^*_G (z)\), \(f^*_G (z)\), and \(t^*_G (z)\).
It remains to rewrite (2)–(5) for \(h^*_{ {\mathscr {P}}^\circ } (z)= \alpha _{ d+1 }z^{ d+1 } + \alpha _{ d } z^{ d } + \dots +\alpha _1 z\) (assuming the polytope in question has dimension d) via (1):
The remaining inequalities in Theorem 1.1 now follow from the first two sets of inequalities above. \(\square \)
Notes
If we do not specify a basis when talking about the coefficients of a polynomial, we are thinking of the standard monomial basis.
There is a subtlety here that differentiates \(\chi _G(n)\) from \(\phi _G(n)\), \(f_G(n)\), and \(t_G(z)\), and thus one needs to treat the accompanying generating functions with some care. Namely, \(\chi _G(n)\) has constant term 0, which is not true for \(\phi _G(n)\), \(f_G(n)\), and \(t_G(z)\). Note that we chose all of our generating functions to start with \(n=1\); the alternative choice of starting with \(n=0\) would result in a different definition of the binomial transform.
The equality (7) of \(h^*_{\mathscr {O}}(z)\) and \(h^*_{ \mu ({\mathscr {O}}) } (z)\) can be also seen by noticing that the triangulations T and \(T_\mu \) are regular and therefore shellable, and they have the same h-polynomial. See, e.g., [11] why order polytopes are compressed, and therefore have regular unimodular triangulations, and also how these properties are preserved under the projection \(\mu \). We also note that projected order polytopes are examples of alcoved polytopes [17].
An orientation is acyclic if it does not contain any coherently directed cycles.
An orientation is totally cyclic if every edge lies in a coherently directed cycle.
References
Athanasiadis, C.A.: \(h^\ast \)-Vectors, Eulerian polynomials and stable polytopes of graphs. Electron. J. Comb. 11(2), # R6 (2004/06)
Beck, M., Robins, S.: Computing the Continuous Discretely. Integer-Point Enumeration in Polyhedra. Undergraduate Texts in Mathematics. Springer, New York (2015)
Betke, U., McMullen, P.: Lattice points in lattice polytopes. Monatsh. Math. 99(4), 253–265 (1985)
Brenti, F.: Expansions of chromatic polynomials and log-concavity. Trans. Am. Math. Soc. 332(2), 729–756 (1992)
Breuer, F., Dall, A.: Bounds on the coefficients of tension and flow polynomials. J. Algebraic Comb. 33(3), 465–482 (2011)
Breuer, F., Sanyal, R.: Ehrhart theory, modular flow reciprocity, and the Tutte polynomial. Math. Z. 270(1–2), 1–18 (2012)
De Loera, J.A., Rambau, J., Santos, F.: Triangulations. Algorithms and Computation in Mathematics, vol. 25. Springer, Berlin (2010)
Ehrhart, E.: Sur les polyèdres rationnels homothétiques à \(n\) dimensions. C. R. Acad. Sci. Paris 254, 616–618 (1962)
Gansner, E.R., Vo, K.P.: The chromatic generating function. Linear Multilinear Algebra 22(1), 87–93 (1987)
Gessel, I.M.: Acyclic orientations and chromatic generating functions. Discret. Math. 232(1–3), 119–130 (2001)
Haase, C., Paffenholz, A., Piechnik, L.C., Santos, F.: Existence of unimodular triangulations—positive results (2014). arXiv:1405.1687
Hersh, P., Swartz, E.: Coloring complexes and arrangements. J. Algebraic Comb. 27(2), 205–214 (2008)
Jaeger, F.: Nowhere-zero flow problems. In: Selected Topics in Graph Theory, vol. 3, pp. 71–95. Academic Press, San Diego (1988)
Kochol, M.: Polynomials associated with nowhere-zero flows. J. Comb. Theory Ser. B 84(2), 260–269 (2002)
Kochol, M.: Tension polynomials of graphs. J. Graph Theory 40(3), 137–146 (2002)
Korfhage, R.R.: \(\sigma \)-Polynomials and graph coloring. J. Comb. Theory Ser. B 24(2), 137–153 (1978)
Lam, T., Postnikov, A.: Alcoved polytopes, I. Discret. Comput. Geom. 38(3), 453–478 (2007)
León, E.: Stapledon decompositions and inequalities for coefficients of chromatic polynomials. Sém. Lothar. Combin. 78B, # 24 (2017)
Linial, N.: Graph coloring and monotone functions on posets. Discret. Math. 58(1), 97–98 (1986)
Macdonald, I.G.: Polynomials associated with finite cell-complexes. J. Lond. Math. Soc. 4, 181–192 (1971)
Payne, S.: Ehrhart series and lattice triangulations. Discret. Comput. Geom. 40(3), 365–376 (2008)
Seymour, P.D.: Nowhere-zero flows. In: Handbook of Combinatorics, vol. 1, pp. 289–299. Elsevier, Amsterdam (1995)
Stanley, R.P.: A chromatic-like polynomial for ordered sets. In: 2nd Chapel Hill Conference on Combinatorial Mathematics and its Applications (Chapel Hill 1970), pp. 421–427. Univ. North Carolina, Chapel Hill (1970)
Stanley, R.P.: Decompositions of rational convex polytopes. Ann. Discret. Math. 6, 333–342 (1980)
Stanley, R.P.: Two poset polytopes. Discret. Comput. Geom. 1(1), 9–23 (1986)
Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge Studies in Advanced Mathematics, vol. 49. Cambridge University Press, Cambridge (2012)
Stapledon, A.: Inequalities and Ehrhart \(\delta \)-vectors. Trans. Am. Math. Soc. 361(10), 5615–5626 (2009)
Tomescu, I.: Graphical Eulerian numbers and chromatic generating functions. Discret. Math. 66(3), 315–318 (1987)
Tutte, W.T.: A ring in graph theory. Proc. Camb. Philos. Soc. 43, 26–40 (1947)
Wilf, H.S.: Which polynomials are chromatic? In: Colloquio Internazionale sulle Teorie Combinatorie (Roma 1973), vol. 1. Atti dei Convegni Lincei, vol. 17, pp. 247–256. Accad. Naz. Lincei, Rome (1976)
Acknowledgements
We thank Tristram Bogart, Tricia Hersh, Florian Kohl, Julián Pulido, Alan Stapledon, Tom Zaslavsky, and two anonymous referees for many useful conversations and comments. Also thanks to the organizers of ECCO 2016 (Escuela Colombiana de Combinatoria 2016 in Medellín, Colombia) where this research collaboration started, and to the Universidad de los Andes for their support.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: János Pach
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A preliminary version of this paper [18] appeared as an extended abstract in the conference proceedings for FPSAC 2017 (Formal Power Series and Combinatorics at Queen Mary University of London), published in Séminaire Lotharingien Combinatoire.
Rights and permissions
About this article
Cite this article
Beck, M., León, E. Binomial Inequalities for Chromatic, Flow, and Tension Polynomials. Discrete Comput Geom 66, 464–474 (2021). https://doi.org/10.1007/s00454-021-00314-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-021-00314-3
Keywords
- Chromatic polynomial
- Flow polynomial
- Tension polynomial
- Classification
- Binomial coefficient
- Binomial transform
- Lattice polytope
- Ehrhart polynomial
- \(h^*\)-polynomial
- Unimodular triangulation
- Order polynomial