1 Introduction
The investigation of graphs in combination with polytopes has a long tradition. Graphs arising from polytopes are a classical, intensively studied topic in discrete geometry and optimization and remain an active area of research (see, e.g., [Reference Blind and Mani-Levitska4, Reference Dantzig9, Reference Santos33, Reference Steinitz38]). On the other hand, a variety of polytope constructions arising from graphs have led to interesting examples and new insights in combinatorics, graph theory, geometry and algebra (see, e.g., [Reference Deza and Laurent11, Reference Lovász24]). An important class of examples constitute edge polytopes which were introduced by Hibi and Ohsugi [Reference Ohsugi and Hibi30]. Of current particular interest due to their intimate relation to matroid polytopes and generalized permutahedra are root polytopes, a reincarnation of edge polytopes for bipartite graphs, introduced by Postnikov [Reference Postnikov32]. For further reading on edge polytopes we refer to [Reference Dupont and Villarreal12, Reference Hibi, Li and Zhang19, Reference Tran and Ziegler40].
The focus of the present article is symmetric edge polytopes, a symmetrized version of edge polytopes that were introduced in [Reference Matsui, Higashitani, Nagazawa, Ohsugi and Hibi26]. We study fundamental geometric and arithmetic properties of symmetric edge polytopes by combining geometric, algebraic, combinatorial and analytic methods of recent special interest: half-open decomposition, Gröbner bases and interlacing polynomials. For a simple graph
$G$
, that is, without loops or multiple edges, with vertex set
$V$
and edge set
$E$
, the symmetric edge polytope is defined as
$$\begin{eqnarray}P_{G}:=\text{conv}(e_{v}-e_{w},e_{w}-e_{v}:vw\in E)\subset \mathbb{R}^{V},\end{eqnarray}$$
where
$e_{v}\in \mathbb{R}^{V}$
is the unit vector indexed by the vertex
$v$
of
$G$
. By definition,
$P_{G}$
is a centrally symmetric lattice polytope. Moreover,
$P_{G}$
belongs to the class of reflexive and terminal polytopes [Reference Higashitani20] that play a prominent role in algebraic geometry via mirror symmetry [Reference Batyrev1]. A fundamental arithmetic invariant of a lattice polytope is the Ehrhart polynomial which encodes the number of lattice points in its integer dilates [Reference Ehrhart13]. A fundamental question in Ehrhart theory is to characterize Ehrhart polynomials. Of current particular interest are roots of Ehrhart polynomials and their closely related
$h^{\ast }$
-polynomials. Using orthogonal polynomial techniques, it was recently proved that the Ehrhart polynomial of the symmetric edge polytope for complete bipartite graphs
$K_{a,b}$
exhibits behavior similar to the Riemann
$\unicode[STIX]{x1D701}$
-function whenever
$a\leqslant 3$
[Reference Higashitani, Kummer and Michałek21] extending investigations initiated by Bump et al [Reference Bump, Choi, Kurlberg and Vaaler6]. More precisely, all roots lie on the complex line
$\{z\in \mathbb{C}:\Re (z)=-\frac{1}{2}\}$
, where
$\Re (z)$
denotes the real part of
$z$
, and, moreover, the roots interlace on that line. Interlacing polynomials currently receive considerable attention due to their significance in a recent proof of the Kadison–Singer problem [Reference Marcus, Spielman and Srivastava25]. In the light of Stanley’s unimodality conjecture [Reference Stanley37] of current great interest in Ehrhart theory are real-rooted
$h^{\ast }$
-polynomials, and here recent success was made using interlacing polynomials techniques [Reference Beck, Jochemko and McCullough2, Reference Jochemko22, Reference Savage and Visontai34, Reference Solus35]. Combining algebraic, geometric and combinatorial counting arguments, we obtain our first main theorem—the following simple description for
$h^{\ast }$
-polynomials of symmetric edge polytopes of complete bipartite graphs.
Theorem. For all
$a,b\geqslant 0$
let
$h_{a,b}^{\ast }(t)$
denote the
$h^{\ast }$
-polynomial of
$P_{K_{a+1,b+1}}$
. Then
$$\begin{eqnarray}\displaystyle h_{a,b}^{\ast }(t)=\mathop{\sum }_{i=0}^{\min (a,b)}\binom{2i}{i}\binom{a}{i}\binom{b}{i}t^{i}(1+t)^{a+b+1-2i}. & & \displaystyle \nonumber\end{eqnarray}$$
Our result generalizes [Reference Higashitani, Kummer and Michałek21, Proposition 4.4], where the case
$\min (a,b)\leqslant 3$
was studied. From the formula it is apparent that the
$h^{\ast }$
-polynomial is palindromic, that is,
$t^{a+b+1}h_{a,b}^{\ast }(1/t)=h_{a,b}^{\ast }(t)$
which reflects that
$P_{K_{a+1,b+1}}$
is reflexive by a famous theorem of Hibi [Reference Hibi18]. Stronger, our theorem shows that
$h_{a,b}^{\ast }(t)$
is
$\unicode[STIX]{x1D6FE}$
-positive. Since every triangulation of the symmetric edge polytope using all lattice points is unimodular [Reference Matsui, Higashitani, Nagazawa, Ohsugi and Hibi26], the
$h^{\ast }$
-polynomial agrees with the
$h$
-polynomial of any such triangulation. This directly relates to open question in topological combinatorics: since
$h_{a,b}^{\ast }(t)$
is
$\unicode[STIX]{x1D6FE}$
-positive, we answer Gal’s conjecture [Reference Gal17, Conjecture 2.1.7] in the affirmative for all flag triangulations of
$\unicode[STIX]{x2202}P_{K_{a+1,b+1}}$
, that is, in particular, for the triangulation obtained from the explicit description of the Gröbner basis (Theorem 3.9). In [Reference Nevo and Petersen28, Conjecture 6.3] Nevo and Petersen moreover conjecture that the
$\unicode[STIX]{x1D6FE}$
-vector of any flag simplicial sphere is the
$f$
-vector of a balanced simplicial complex, or equivalently, that its entries satisfy the Frankl–Füredi–Kalai inequalities. Both Gal’s conjecture and the conjecture by Nevo-Petersen are strengthenings of a conjecture of Charney and Davis [Reference Charney and Davis7, Conjecture D], which was further motivated by a conjecture of Hopf on the Euler characteristic of closed Riemannian manifolds of non-positive sectional curvature. In §4.6 we confirm Nevo and Petersen’s conjecture for all flag unimodular triangulations of
$\unicode[STIX]{x2202}P_{K_{a+1,b+1}}$
by giving an explicit construction of a corresponding simplicial complex.
The Real Roots Conjecture by Januszkiewicz states that the
$h$
-polynomial of a flag simplicial generalized homology sphere has only real roots (see [Reference Davis, Dymara, Januszkiewicz and Okun10, p. 116]). The conjecture was disproved in general by Gal [Reference Gal16, Reference Gal17]. Our next result shows that flag triangulations of
$\unicode[STIX]{x2202}P_{K_{a+1,b+1}}$
are positive examples of the Real Roots Conjecture. Using
$\unicode[STIX]{x1D6FE}$
-positivity and a classical result of Polyá and Schur [Reference Polya and Schur31] we prove our second main theorem;
$h_{a,b}^{\ast }(t)$
has only real roots and, moreover, the following interlacing property.
Theorem. For all
$a,b\geqslant 0$
the polynomial
$h_{a,b}^{\ast }(t)$
has only real roots and
$$\begin{eqnarray}h_{a,b-1}^{\ast }(t)\preccurlyeq h_{a,b}^{\ast }(t).\end{eqnarray}$$
That is, the polynomial
$h_{a,b-1}^{\ast }(t)$
interlaces
$h_{a,b}^{\ast }(t)$
.
The outline of the paper is as follows. In §2 we provide preliminaries and notation of our main objects. In Theorem 3.1 we give a combinatorial description of all facet-defining hyperplanes of
$P_{G}$
. From that we derive a simple counting formula for the number of facets in case of bipartite (Proposition 3.4) and, more generally, multipartite graphs (Proposition 3.5) which is exponential in the number of vertices. In §3.2 we give a combinatorial description of a Gröbner basis of
$P_{G}$
. Section 4 is devoted to complete bipartite graphs collecting all ingredients of the proofs of our two main theorems. In §4.1 we provide an alternative, combinatorial formula of
$h_{a,b}^{\ast }(t)$
by careful double counting. In §4.3 we construct a half-open triangulation and obtain a graph theoretical description of
$h_{a,b}^{\ast }(t)$
. Section 4.4 is devoted to proving the first main theorem (Theorem 4.1). In §4.5 we study the roots of
$h_{a,b}^{\ast }(t)$
and prove the second main theorem (Theorem 4.8). In §4.6 we prove Conjecture 4.11 for triangulations of
$\unicode[STIX]{x2202}P_{K_{a,b}}$
. We conclude with a general recursive formula for
$h_{a,b}^{\ast }(t)$
in §4.7.
2 Preliminaries
In this section we collect preliminaries necessary for the following sections. We assume basic knowledge of polyhedral geometry and commutative algebra. For further reading we recommend [Reference Beck and Robins3, Reference Brändén5, Reference Michałek and Hibi27, Reference Sturmfels39, Reference Ziegler41].
2.1 Lattice polytopes
A lattice polytope is the convex hull of finitely many elements in a lattice contained in
$\mathbb{R}^{d}$
, typically
$\mathbb{Z}^{d}$
. A lattice polytope
$P$
is called reflexive if
$$\begin{eqnarray}P^{\vee }:=\{\mathbf{u}\in \mathbb{R}^{d}:\langle \mathbf{u},\mathbf{v}\rangle \geqslant -1\text{ for any }\mathbf{v}\in P\}\end{eqnarray}$$
is also a lattice polytope, where
$\langle \cdot ,\cdot \rangle$
denotes the usual inner product of
$\mathbb{R}^{d}$
. It is called terminal if all lattice points on the boundary of
$P$
are vertices. In particular, the only lattice points that are contained in a terminal reflexive lattice polytope are its vertices and the origin.
By a theorem of Ehrhart [Reference Ehrhart13],
$|nP\cap \mathbb{Z}^{d}|$
is given by a polynomial
$E_{P}(n)$
of degree
$\dim P$
in
$n$
for all integers
$n\geqslant 0$
, the Ehrhart polynomial. The
$h^{\ast }$
-polynomial
$h_{P}^{\ast }(t)=h_{0}^{\ast }+h_{1}^{\ast }t+\cdots +h_{d}t^{d}$
of a
$d$
-dimensional lattice polytope
$P$
encodes the Ehrhart polynomial in a particular basis consisting of binomial coefficients:
$$\begin{eqnarray}E_{P}(n)=h_{0}^{\ast }\binom{n+d}{d}+h_{1}^{\ast }\binom{n+d-1}{d}+\cdots +h_{d}^{\ast }\binom{n}{d}.\end{eqnarray}$$
A fundamental theorem of Stanley [Reference Stanley36, Theorem 2.1] states that the coefficients of the
$h^{\ast }$
-polynomial are always non-negative integers. It was proved by Hibi [Reference Hibi18, Theorem 2.1] that a
$d$
-dimensional lattice polytope
$P$
is reflexive if and only if its
$h^{\ast }$
-polynomial is palindromic, that is,
$h_{P}^{\ast }(t)=t^{d}h_{P}^{\ast }(1/t)$
.
2.2 Triangulations and Gröbner bases
A triangulation
${\mathcal{T}}$
of dimension
$d$
is a subdivision into simplices of dimension at most
$d$
. The triangulation
${\mathcal{T}}$
is flag if every minimal non-face of
${\mathcal{T}}$
is one-dimensional. If
${\mathcal{T}}$
has vertex set
$V$
, then
${\mathcal{T}}$
is balanced if there is a proper coloring of its vertices
$c:V\rightarrow [d+1]$
, i.e., for every face
$F\in {\mathcal{T}}$
, the restriction of
$c$
into
$F$
is injective. The
$f$
-polynomial
$f(t)=f_{-1}+f_{0}t+\cdots +f_{d}t^{d+1}$
encodes the numbers of faces in all dimensions:
$f_{i}=|\{\unicode[STIX]{x1D6E5}\in {\mathcal{T}}:\dim \unicode[STIX]{x1D6E5}=i\}|$
, where we let
$f_{-1}:=1$
. The
$h$
-polynomial
$h(t)=\sum _{i=0}^{d+1}h_{i}t^{i}$
is given via the following relation:
$$\begin{eqnarray}f(t)=\mathop{\sum }_{i=0}^{d+1}h_{i}t^{i}(1+t)^{d+1-i}.\end{eqnarray}$$
Note that
$h_{d+1}=0$
if the geometric realization of
${\mathcal{T}}$
is homeomorphic to the
$d$
-dimensional ball, so in our case we always have
$h_{d+1}=0$
. A
$d$
-dimensional lattice simplex is called unimodular if its vertices affinely span the integer lattice
$\mathbb{Z}^{d}$
. A triangulation of a lattice polytope into unimodular simplices is called a unimodular triangulation. If
${\mathcal{T}}$
is a unimodular triangulation of a lattice polytope
$P$
then its
$h$
-polynomial equals the
$h^{\ast }$
-polynomial
$h_{P}^{\ast }(t)$
of
$P$
, and, moreover, if
$P$
is reflexive, then it is equal to the
$h$
-polynomial of the induced unimodular triangulation of the boundary.
An important tool to calculate triangulations are Gröbner bases. Let
$K$
be a field and let
$K[t_{1}^{\pm },\ldots ,t_{d}^{\pm },s]$
denote the ring of Laurent polynomials in
$(d+1)$
variables. Let
$P$
be a fixed lattice polytope in
$\mathbb{R}^{d}$
. For any lattice point
$\unicode[STIX]{x1D6FC}=(\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{d})\in P\cap \mathbb{Z}^{d}$
, let
$u_{\unicode[STIX]{x1D6FC}}$
be the Laurent monomial
$t_{1}^{\unicode[STIX]{x1D6FC}_{1}}\cdots t_{d}^{\unicode[STIX]{x1D6FC}_{d}}\in K[t_{1}^{\pm },\ldots ,t_{d}^{\pm },s]$
. The toric ring
$K[P]$
of
$P$
is the subring of
$K[t_{1}^{\pm },\ldots ,t_{d}^{\pm },s]$
generated by those monomials
$u_{\unicode[STIX]{x1D6FC}}s$
with
$\unicode[STIX]{x1D6FC}\in P\cap \mathbb{Z}^{d}$
. Let
$S=K[x_{\unicode[STIX]{x1D6FC}}:\unicode[STIX]{x1D6FC}\in P\cap \mathbb{Z}^{d}]$
be the polynomial ring with
$|P\cap \mathbb{Z}^{d}|$
variables and
$\deg (x_{\unicode[STIX]{x1D6FC}})=1$
. Then
$\unicode[STIX]{x1D70B}:S\rightarrow K[P],\unicode[STIX]{x1D70B}(x_{\unicode[STIX]{x1D6FC}})=u_{\unicode[STIX]{x1D6FC}}s$
defines a surjective ring homomorphism. The kernel of
$\unicode[STIX]{x1D70B}$
is called the toric ideal of
$P$
and is denoted by
$I_{P}$
.
A total order
${<}$
on the monomials of a polynomial ring is called a monomial order if for all monomials
$a,b,c$
one has
$ac<bc$
whenever
$a<b$
and
$1<a$
for all non-constant monomials. An important example is the degree reverse lexicographic order
${<}_{\text{rev}}$
(degrevlex). Here, for two monomials
$\prod x_{i}^{a_{i}}$
and
$\prod x_{i}^{b_{i}}$
,
$\prod x_{i}^{a_{i}}{<}_{\text{rev}}\prod x_{i}^{b_{i}}$
holds with respect to the degree reverse lexicographic order
${<}_{\text{rev}}$
induced by the ordering
$x_{1}{<}_{\text{rev}}x_{2}{<}_{\text{rev}}\cdots \,$
of variables if and only if
$\sum a_{i}<\sum b_{i}$
, or
$\sum a_{i}=\sum b_{i}$
and
$a_{j}>b_{j}$
for
$j=\min \{i:a_{i}\neq b_{i}\}$
. The initial term of a polynomial
$f$
is the largest monomial that appears in
$f$
and is denoted by
$\operatorname{in}_{{<}}(f)$
. The ideal generated by all initial terms of an ideal
$I$
is called the initial ideal of
$I$
and denoted by
$\operatorname{in}_{{<}}(I)$
. A system of generators
$g_{1},\ldots ,g_{m}$
of an ideal is called a Gröbner basis if the initial terms of the generators already generate the initial ideal of
$I$
, that is, if
$\operatorname{in}_{{<}}(I)=\langle \operatorname{in}_{{<}}(g_{1}),\ldots ,\operatorname{in}_{{<}}(g_{m})\rangle$
.
Consider any set of polynomials
$F=\{f_{1},\ldots ,f_{k}\}$
with leading monomials
$m_{1},\ldots ,m_{k}$
. Suppose the coefficient of
$m_{i}$
in
$f_{i}$
equals one. We say that a polynomial
$P$
may be reduced using
$F$
, if some monomial
$m$
in the support of
$P$
is divisible by one of the
$m_{i}$
, say
$m=m_{i}\cdot m^{\prime }$
. A reduction of
$P$
is a polynomial
$P^{\prime }$
with
$m$
replaced by
$m^{\prime }(m_{i}-f_{i})$
. As every monomial order is a well-ordering, every reduction process must terminate, possibly with zero. A set of polynomials of an ideal
$I$
is a Gröbner basis if and only if any polynomial
$P\in I$
may be reduced to
$0$
, or, equivalently, if
$P\neq 0$
, then
$P$
may be reduced.
For a toric ideal
$I_{P}$
of a lattice polytope
$P$
, let
$\unicode[STIX]{x1D6E5}_{P}$
be the collection of subsets
$S\subset P\cap \mathbb{Z}^{d}$
such that
$\text{conv}(S)$
is a simplex and
$\prod _{\unicode[STIX]{x1D6FC}\in S}x_{\unicode[STIX]{x1D6FC}}\not \in \sqrt{\operatorname{in}_{{<}}(I_{P})}$
. Then
$\unicode[STIX]{x1D6E5}_{P}$
defines a regular triangulation of
$P$
with the vertex set
$P\cap \mathbb{Z}^{d}$
. Moreover, the triangulation
$\unicode[STIX]{x1D6E5}_{P}$
is unimodular if and only if
$\operatorname{in}_{{<}}(I)=\sqrt{\operatorname{in}_{{<}}(I)}$
(see, e.g., [Reference Sturmfels39, Corollary 8.9]). In other words,
$P$
has a regular unimodular triangulation if and only if
$I_{P}$
has a squarefree Gröbner basis, where a Gröbner basis
$g_{1},\ldots ,g_{m}$
is said to be squarefree if all its initial terms
$\operatorname{in}_{{<}}(g_{1}),\ldots ,\operatorname{in}_{{<}}(g_{m})$
are squarefree.
2.3 Half-open decompositions
Let
$P$
be a full-dimensional polytope with facets
$F_{1},\ldots ,F_{m}$
and let
$q$
be in general position, that is,
$q$
is not contained in any facet-defining hyperplane for all
$i$
. A facet
$F_{i}$
of
$P$
is visible from
$q$
if for every
$p\in F_{i}$
we have
$(p,q]\cap P=\emptyset$
. Let
$I_{q}(P)=\{i\in [m]:F_{i}~\text{visible from }q\}$
be the index set of visible facets. A half-open polytope is a polytope without its visible facets:
$$\begin{eqnarray}H_{q}P=P\Big\backslash\mathop{\bigcup }_{i\in I_{q}(P)}F_{i}.\end{eqnarray}$$
If
$P=P_{1}\cup \cdots \cup P_{k}$
defines a polyhedral subdivision with maximal cells
$P_{1},\ldots ,P_{k}$
and
$q$
is in general position with respect to all
$P_{i}$
, then
$$\begin{eqnarray}H_{q}P=H_{q}P_{1}\sqcup \cdots \sqcup H_{q}P_{k}\end{eqnarray}$$
defines a partition [Reference Köppe and Verdoolaege23, Theorem 3]. If
$P_{1},\ldots ,P_{k}$
are simplices, that is, they are the maximal cells of a triangulation
${\mathcal{T}}$
of
$P$
, then the
$h$
-polynomial of the triangulation can be read off from the half-open decomposition.
Proposition 2.1. Let
$P=P_{1}\cup \cdots \cup P_{k}$
be a triangulation
${\mathcal{T}}$
and
$q\in P$
general with respect to
$P_{i}$
for all
$i$
. Let
$h(t)=h_{0}+h_{1}t+\cdots +h_{d}t^{d}$
be the
$h$
-polynomial of
${\mathcal{T}}$
. Then
$$\begin{eqnarray}h_{i}=|\{j\in [k]:|I_{q}(P_{j})|=i\}|.\end{eqnarray}$$
In particular, if
$P$
is a lattice polytope and
$P=P_{1}\cup \cdots \cup P_{k}$
defines a unimodular triangulation, then also
$h_{i}^{\ast }(P)=|\{j\in [k]:|I_{q}(P_{j})|=i\}|$
for all
$i$
.
2.4 Real-rooted polynomials
A polynomial
$f=\sum _{i=0}^{d}a_{i}t^{i}$
of degree
$d$
with real coefficients is said to be real-rooted, if all its roots are real. If all coefficients of a real-rooted polynomial are non-negative, or equivalently, all roots are non-positive, then
$a_{i}^{2}\geqslant a_{i-1}a_{i+1}$
for all
$i$
(see, e.g., [Reference Stanley37, Theorem 2]). A sequence
$a_{i}$
of coefficients satisfying this system of inequalities is called log-concave. An immediate consequence is that the non-negative, log-concave sequence is unimodal, that is,
$a_{0}\leqslant a_{1}\leqslant \cdots \leqslant a_{k}\geqslant \cdots \geqslant a_{d}$
for some
$k$
.
The polynomial
$f$
is said to be palindromic if
$f(t)=t^{d}f(1/t)$
. It is
$\unicode[STIX]{x1D6FE}$
-positive if there are
$\unicode[STIX]{x1D6FE}_{0},\unicode[STIX]{x1D6FE}_{1},\ldots ,\unicode[STIX]{x1D6FE}_{\lfloor d/2\rfloor }\geqslant 0$
such that
$f(t)=\sum _{i\geqslant 0}\unicode[STIX]{x1D6FE}_{i}t^{i}(1+t)^{d-2i}$
. The polynomial
$\sum \unicode[STIX]{x1D6FE}_{i}t^{i}$
is called the
$\unicode[STIX]{x1D6FE}$
-polynomial of
$f$
. It can be seen that a
$\unicode[STIX]{x1D6FE}$
-positive polynomial is real-rooted if and only if its
$\unicode[STIX]{x1D6FE}$
-polynomial has only real roots.
Let
$f$
and
$g$
be real-rooted polynomials with roots
$a_{1}\geqslant a_{2}\geqslant \cdots \,$
, respectively,
$b_{1}\geqslant b_{2}\geqslant \cdots \,$
. Then
$g$
is said to interlace
$f$
if
$$\begin{eqnarray}a_{1}\geqslant b_{1}\geqslant a_{2}\geqslant b_{2}\geqslant \cdots \,.\end{eqnarray}$$
In this case we write
$g\preccurlyeq f$
. In particular,
$\deg g\leqslant \deg f\leqslant \deg g+1$
. If
$f\preccurlyeq g$
or
$g\preccurlyeq f$
we say that
$f$
and
$g$
interlace. The following result by Obreschkoff [Reference Obreschkoff29] characterizes the interlacing property.
Theorem 2.2 [Reference Obreschkoff29, Satz 5.2].
Let
$f,g\in \mathbb{R}[t]\setminus \{0\}$
. Then
$f$
and
$g$
interlace if and only if
$cf+dg$
has only real roots for all
$c,d\in \mathbb{R}$
.
A linear operator
$T:\mathbb{R}[t]\rightarrow \mathbb{R}[t]$
preserves real-rootedness if
$T(f)$
has only real roots for any real-rooted polynomial
$f\in \mathbb{R}[t]$
. An operator is said to preserve the interlacing property if
$T(f)$
and
$T(g)$
are interlacing whenever
$f$
and
$g$
are. A consequence of Obreschkoff’s theorem is the following.
Corollary 2.3 [Reference Fisk14, Theorem 1.43].
Let
$T:\mathbb{R}[t]\rightarrow \mathbb{R}[t]$
be a linear operator. Then
$T$
preserves real-rootedness if and only if it preserves the interlacing property.
An operator
$T$
acts diagonally if there is a sequence
$\{{\unicode[STIX]{x1D706}_{i}\}}_{i}\geqslant 0$
such that
$T(t^{i})=\unicode[STIX]{x1D706}_{i}t^{i}$
for all
$i\geqslant 0$
. If
$T$
preserves real-rootedness, then
$\{{\unicode[STIX]{x1D706}_{i}\}}_{i}\geqslant 0$
is called a multiplier sequence. The following famous theorem by Polyá and Schur [Reference Polya and Schur31] characterizes multiplier sequences.
Theorem 2.4 [Reference Polya and Schur31, Satz I].
Let
$\unicode[STIX]{x1D6EC}=\{{\unicode[STIX]{x1D706}_{i}\}}_{i}\geqslant 0$
be a sequence and
$$\begin{eqnarray}G_{\unicode[STIX]{x1D6EC}}(x):=\mathop{\sum }_{i\geqslant 0}\unicode[STIX]{x1D706}_{i}\frac{x^{i}}{i!}.\end{eqnarray}$$
The following are equivalent.
(i) The sequence
$\unicode[STIX]{x1D6EC}$
is a multiplier sequence.(ii) The power series
$G_{\unicode[STIX]{x1D6EC}}(x)$
is an entire function that is the limit of real-rooted polynomials whose zeros all have the same sign that converge uniformly on compact subsets of
$\mathbb{C}$
.
3 Facets and triangulations
Let
$G=(V,E)$
be an arbitrary finite simple graph with vertex set
$V$
and edge set
$E$
. We recall that the symmetric edge polytope is defined as
$$\begin{eqnarray}P_{G}:=\text{conv}(e_{v}-e_{w},e_{w}-e_{v}:vw\in E)\subset \mathbb{R}^{V},\end{eqnarray}$$
where
$e_{v}\in \mathbb{R}^{V}$
is the unit vector indexed by the vertex
$v$
of
$G$
. Let
$G_{1},\ldots ,G_{l}$
be the connected components of
$G$
. Then
$P_{G}$
is a free sum of the polytopes
$P_{G_{1}},\ldots ,P_{G_{l}}$
. In the following we thus restrict to the case when
$G$
is connected.
3.1 Facets
In this section we provide a combinatorial description of the facets of the symmetric edge polytope
$P_{G}$
of an arbitrary finite simple graph
$G=(V,E)$
with vertex set
$V$
and edge set
$E$
. From the definition it follows that the vertices of
$P_{G}$
are contained in the lattice
$M=\{x\in \mathbb{Z}^{V}:\sum _{v\in V}x_{v}=0\}$
. The dual lattice
$N=\mathbb{Z}^{V}/(1_{v})_{v\in V}\mathbb{Z}$
consists of functions
$f:V\rightarrow \mathbb{Z}$
, where two functions are identified if they differ by a common constant. Every such function can be identified with associations of integers to vertices of the graph
$G$
, up to addition of a (common) constant. Since
$P_{G}$
is reflexive, every facet-defining hyperplane is of the form
$\{x\in M:\sum _{v\in V}f(v)x_{v}=1\}$
for some
$f\in N$
.
Theorem 3.1. Let
$G=(V,E)$
be a finite simple connected graph. Then
$f:V\rightarrow \mathbb{Z}$
is facet-defining if and only if both of the following hold.
(i) For any edge
$e=uv$
we have
$|f(u)-f(v)|\leqslant 1$
.(ii) The subset of edges
$E_{f}=\{e=uv\in E:|f(u)-f(v)|=1\}$
forms a spanning connected subgraph of
$G$
.
Proof. First we show that for any function
$f:V\rightarrow \mathbb{Z}$
that satisfies the conditions (i) and (ii) the hyperplane
$\{x\in M:\sum _{v\in V}f(v)x_{v}=1\}$
defines a facet. By condition (ii) the set
$X_{f}=\{e_{u}-e_{v}:f(u)-f(v)=1\}$
of vertices of
$P_{G}$
that lie on the hyperplane defined by
$f$
span
$\{x\in \mathbb{Z}^{V}:\sum _{v\in V}x_{v}=0\}$
. Moreover, by condition (i),
$f$
is maximized on
$X_{f}$
. Therefore,
$X_{f}$
is a facet and thus
$f$
is facet-defining.
For the other direction, let
$F=\{x\in P_{G}:\sum _{v\in V}f(v)x_{v}=1\}$
be a facet of
$P_{G}$
defined by some
$f:V\rightarrow \mathbb{Z}$
. Then
$e_{u}-e_{v}\in F$
if and only if
$f(u)-f(v)=1$
. Since
$F$
is a facet, there are
$|V|-1$
linearly independent vertices in
$F$
, say
$e_{u_{1}}-e_{v_{1}},\ldots ,e_{u_{|V|-1}}-e_{v_{|V|-1}}$
. Because of linear independence
$\{u_{1}v_{1},\ldots ,u_{|V|-1}v_{|V|-1}\}\subset E_{f}$
is a spanning tree, and therefore also
$E_{f}$
is spanning and condition (ii) is satisfied. Since
$P_{G}$
is symmetric,
$-F=\{x\in P_{G}:\sum _{v\in V}f(v)x_{v}=-1\}$
is also a facet, and therefore
$f(x)\in [-1,1]$
for all
$x\in P_{G}$
. In particular, evaluating
$f$
at vertices of
$P_{G}$
shows that condition (i) is satisfied.◻
From the proof of Theorem 3.1 we see the following.
Corollary 3.2. The unimodular simplices contained in a facet of
$P_{G}$
represented by a function
$f$
correspond exactly to spanning trees consisting of all edges
$vw$
such that
$|f(v)-f(w)|=1$
.
In the case of complete graphs, complete bipartite graphs and, more generally, complete multipartite graphs, Theorem 3.1 leads to a simple description of the facets of the symmetric edge polytope that moreover allows for an easy counting formula. For complete graphs the following is immediate.
Corollary 3.3. Let
$K_{n}$
be a complete graph with vertex set
$V$
. Then a function
$f:V\rightarrow \mathbb{Z}$
is facet-defining if and only if, up to a constant,
$f(V)=\{0,1\}$
.
Proposition 3.4. Let
$K_{a,b}$
be a complete bipartite graph with vertex set
$v_{1},\ldots ,v_{a},w_{1},\ldots ,w_{b}$
and edge set
$\{\{v_{i},w_{j}\}:1\leqslant i\leqslant a,\;1\leqslant j\leqslant b\}$
. Then
$f:V\rightarrow \mathbb{Z}$
defines a facet if and only if
$f$
, up to a constant, satisfies one of the following conditions:
(i)
$f(v_{i})=0$
for all
$i$
and
$f(w_{j})\in \{-1,1\}$
for all
$j$
; or(ii)
$f(w_{j})=0$
for all
$j$
and
$f(v_{i})\in \{-1,1\}$
for all
$i$
.
In particular, the polytope
$P_{K_{a,b}}$
has
$2^{a}+2^{b}-2$
facets.
Proof. By Theorem 3.1, every function
$f$
that satisfies condition (i) or (ii) defines a facet. It thus remains to prove that every
$f$
such that
$F=\{x\in P_{G}:\sum _{v\in V}f(v)x_{v}=1\}$
is a facet satisfies, up to a constant, one of the conditions (i) or (ii). First, we assume that
$f$
is constant on one part of the graph; without loss of generality
$f(v_{i})=0$
for all
$1\leqslant i\leqslant a$
. By condition (i) in Theorem 3.1,
$f(w_{j})\in \{-1,0,1\}$
for all
$1\leqslant j\leqslant b$
. However, if there was a
$j$
with
$f(w_{j})=0$
, then the graph given in (ii) of Theorem 3.1 would not be connected. Hence we must have
$f(w_{j})\in \{-1,1\}$
for all
$1\leqslant j\leqslant b$
.
We are left with excluding the possibility that
$f$
is non-constant on both parts of the graph. We give a proof by contradiction and assume that there is such a facet-defining function
$f$
. Without loss of generality we may assume that
$f(v_{1})=0$
,
$f(v_{i})\geqslant 0$
for all
$2\leqslant i\leqslant a$
and there exists a
$2\leqslant k\leqslant a$
with
$f(v_{k})>0$
. If
$f(v_{k})>1$
, then
$f(w_{j})=1$
must hold for all
$j$
in order to be able to satisfy condition (i) of Theorem 3.1. This, however, is a contradiction to the assumption that
$f$
is non-constant on both parts. Thus,
$f(v_{i})\in \{0,1\}$
for all
$2\leqslant i\leqslant a$
and hence
$f(w_{j})\in \{0,1\}$
for all
$j$
. However, then the graph given in (ii) of Theorem 3.1 is not connected, again a contradiction.◻
Proposition 3.5. Let
$k\geqslant 3$
and
$G=K_{a_{1},\ldots ,a_{k}}$
be a complete
$k$
-partite graph with vertex set
$V=\bigcup _{i=1}^{k}A_{i}$
and edge set
$\{uv:u\in A_{i},v\in A_{j},i\neq j\}$
. Then
$f:V\rightarrow \mathbb{Z}$
is facet-defining if and only if
$f$
, up to a constant, satisfies one of the following conditions:
(i)
$f(A_{i})=\{-1,1\}$
for some
$1\leqslant i\leqslant k$
and
$f_{|A_{j}}=0$
for all
$i\neq j$
; or(ii)
$f(V)=\{0,1\}$
and:(a)
$f$
is constant on
$A_{i}$
for all
$1\leqslant i\leqslant k$
; or(b) there exists a part
$A_{i}$
such that
$f$
both restricted to
$A_{i}$
and to its complement is surjective onto
$\{0,1\}$
.
In particular, the polytope
$P_{G}$
has
$2^{\sum _{i=1}^{k}a_{i}}-\sum _{i=1}^{k}(2^{a_{i}}-2)-2$
facets where
$a_{i}:=|A_{i}|$
.
Proof. It is easy to check that any function satisfying the above conditions also satisfies the conditions given in Theorem 3.1 and is thus facet-defining.
For the other direction, let
$f:V\rightarrow \mathbb{Z}$
be a facet-defining function. Without loss of generality we may assume that
$f(v)=0$
for some vertex
$v$
in
$A_{1}$
. Then by condition (i) of Theorem 3.1
$f(u)\in [-1,1]$
for all
$u\in V\setminus A_{1}$
.
First suppose that there exists an
$i>1$
with
$\{-1,1\}\subseteq f(A_{i})$
. Then, by condition (i) of Theorem 3.1,
$f_{|A_{j}}=0$
for all
$j\neq i$
, and then, by condition (ii) of Theorem 3.1,
$f(A_{i})=\{-1,1\}$
, and thus condition (i) above is satisfied.
Otherwise, without loss of generality we may assume
$f$
takes only values
$0$
and
$1$
, as it is not possible that
$f$
takes the value
$-1$
on one part and
$1$
on another by condition (i) of Theorem 3.1. If there exists an
$i$
such that both
$f_{|A_{i}}$
and
$f_{|V\setminus A_{i}}$
are surjective onto
$\{0,1\}$
, then condition (ii)(b) above is satisfied. In the other case, under the assumption that condition (ii)(b) above is not satisfied, there is no
$i$
with
$f(A_{i})=\{0,1\}$
since otherwise
$f(V\setminus A_{i})=\{0\}$
or
$\{1\}$
, which contradicts to condition (ii) of Theorem 3.1. Hence, in this case
$f$
must be constant on each part
$A_{i}$
, proving the claim.
In order to determine the number of facets we observe that there are
$\sum _{i=1}^{k}(2^{a_{i}}-2)$
facets of type (i). Furthermore, there are
$2\sum _{i=1}^{k}(2^{a_{i}}-2)$
functions
$f:V\rightarrow \{0,1\}$
that are non-constant on one part
$A_{i}$
and constant and equal on all other parts. Thus, there are
$2^{\sum _{i=1}^{k}a_{i}}-2(\sum _{i=1}^{k}(2^{a_{i}}-2))-2$
functions of type (ii)(a) or (b), where we subtracted
$-2$
to account for the constant functions which are never facet-defining.◻
Example 3.6. From Proposition 3.5 the facets of
$P_{K_{a,b}}$
can be easily geometrically described. If
$f:V\rightarrow \mathbb{Z}$
is a facet-defining hyperplane with
$f(v_{i})=0$
for all
$i$
and
$f(w_{j})=1$
for all
$1\leqslant j\leqslant b_{1}$
and
$f(w_{j})=-1$
for all
$b_{1}<j\leqslant b$
, then the corresponding facet is
$$\begin{eqnarray}\operatorname{conv}(\{e_{w_{j}}-e_{v_{i}}:j\leqslant b_{1}\}\cup \{e_{v_{i}}-e_{w_{j}}:j>b_{1}\})\end{eqnarray}$$
which is isomorphic to the convex hull of
$\unicode[STIX]{x1D6E5}_{a}\times \unicode[STIX]{x1D6E5}_{b_{1}}\times \{0\}$
and
$-\unicode[STIX]{x1D6E5}_{a}\times \{0\}\times -\unicode[STIX]{x1D6E5}_{b_{2}}$
under the isomorphism defined by
$e_{v_{i}}\mapsto -e_{v_{i}}$
and
$e_{w_{j}}\mapsto e_{w_{j}}$
for all
$i,j$
. Here,
$b_{1}+b_{2}=b$
and
$\unicode[STIX]{x1D6E5}_{a}$
denotes the standard simplex on
$a$
vertices. In particular, if
$b=b_{1}$
, then the facet is isomorphic to a product of two standard simplices.
Remark 3.7. Interestingly, for complete bipartite graph only facets of type (i) from Proposition 3.5 appear, while for complete graph only facets of type (ii)(a).
3.2 Gröbner basis
In this section we provide a Gröbner basis for the toric ideal associated to
$P_{G}$
and study the associated induced triangulation. For each edge
$e$
of a simple graph
$G$
we consider both oriented versions
$e^{+}$
and
$e^{-}$
and associate two variables
$x_{e},y_{e}$
, one for each possible orientation. Since
$P_{G}$
is reflexive and terminal, we can naturally identify
$K[\{x_{\unicode[STIX]{x1D6FC}}:\unicode[STIX]{x1D6FC}\in P_{G}\cap \mathbb{Z}^{V}\}]$
with
$K[\{x_{e},{y_{e}\}}_{e\in E}\cup \{z\}]$
, where
$z$
is associated to the origin.
In order to simplify notation, in the following, for any oriented edge
$e$
, we denote by
$p_{e}$
the corresponding variable, i.e.
$p_{e}=x_{e}$
or
$p_{e}=y_{e}$
depending on the orientation. We also set
$q_{e}$
to be equal to the variable with the opposite orientation, i.e.
$\{p_{e},q_{e}\}=\{x_{e},y_{e}\}$
.
Proposition 3.8. Let
$z<x_{e_{1}}<y_{e_{1}}<\cdots <x_{e_{k}}<y_{e_{k}}$
be an order on the edges. Then the following collection of three types of binomials forms a Gröbner basis of the toric ideal of
$P_{G}$
with respect to the degrevlex order.
(1) For every
$2k$
-cycle
$C$
, with fixed orientation, and any
$k$
-element subset
$I$
of edges of
$C$
not containing the smallest edge $$\begin{eqnarray}\mathop{\prod }_{e\in I}p_{e}-\mathop{\prod }_{e\in C\setminus I}q_{e}.\end{eqnarray}$$
(2) For every
$(2k+1)$
-cycle
$C$
, with fixed orientation, and any
$(k+1)$
-element subset
$I$
of edges of
$C$
$$\begin{eqnarray}\mathop{\prod }_{e\in I}p_{e}-z\mathop{\prod }_{e\in C\setminus I}q_{e}.\end{eqnarray}$$
(3) For any edge
$e$
$$\begin{eqnarray}x_{e}y_{e}-z^{2}.\end{eqnarray}$$
The leading monomial is always chosen to have positive sign.
Proof. It is enough to prove that for any binomial
$m_{1}-m_{2}$
in the toric ideal of
$P_{G}$
one of the monomials
$m_{1}$
or
$m_{2}$
is divisible by the leading monomial of one of the binomials present above (see, e.g., [Reference Sturmfels39]). Both monomials can be represented by directed subgraphs
$G_{1}$
and
$G_{2}$
of
$G$
in a canonical way, namely
$e^{+}$
and
$e^{-}$
are edges in the graph if and only if
$x_{e}$
or, respectively,
$y_{e}$
are present in the monomial. We may assume that neither
$G_{1}$
nor
$G_{2}$
has a directed cycle of length two since otherwise this monomial is divisible by
$x_{e}y_{e}$
for some edge
$e$
. Since
$m_{1}-m_{2}$
is contained in the toric ideal of
$P_{G}$
the graphs
$G_{1}$
and
$G_{2}$
have the same difference of in and out degrees at every vertex. Let
$G_{2}^{\prime }$
be the graph obtained from
$G_{2}$
by inverting all edge orientations. Since in
$G_{1}\cup G_{2}^{\prime }$
the in degree equals the out degree at every vertex, we can find an Euler path, that is, a directed closed path using every edge exactly once. In particular, we find a cycle
$C$
in
$G_{1}\cup G_{2}^{\prime }$
. Let
$a$
be the number of edges of
$C\cap G_{1}$
and
$b$
be the number of edges of
$C\cap G_{2}^{\prime }$
. Without loss of generality
$a\geqslant b$
.
First, suppose that
$a+b=2k$
,
$k>1$
. If
$a>b$
consider the set consisting of the
$k$
largest edges of
$C\cap G_{1}$
. Then the leading term of the corresponding binomial in (1) divides
$m_{1}$
. If
$a=b$
we may assume without loss of generality that the smallest edge of
$C$
belongs to
$G_{2}$
and proceed as before. If
$a+b=2k+1$
, then since
$a>b$
, the leading term of the binomial in (2) corresponding to
$(k+1)$
directed edges in
$G_{1}$
divides
$m_{1}$
.◻
While the Gröbner basis obtained in Proposition 3.8 is in general not reduced, an explicit construction of a reduced Gröbner basis for
$K_{a,b}$
was obtained in [Reference Higashitani, Kummer and Michałek21]. For edge polytopes a set of generators was obtained by Ohsugi and Hibi [Reference Ohsugi and Hibi30].
Theorem 3.9 [Reference Higashitani, Kummer and Michałek21, Lemma 4.1].
Let
$K_{a,b}$
be a complete bipartite graph with vertex set
$\{v_{1},\ldots ,v_{a},w_{1},\ldots ,w_{b}\}$
and edge set
$\{v_{i}w_{j}:1\leqslant i\leqslant a,1\leqslant j\leqslant b\}$
. Let
$e_{ij}$
be a variable associated to the oriented edge
$(v_{i},w_{j})$
and
$f_{ij}$
be the variable associated to
$(w_{j},v_{i})$
. Let
$e_{ij}<e_{i^{\prime }j^{\prime }}$
and
$f_{ij}<f_{i^{\prime }j^{\prime }}$
whenever
$i<i^{\prime }$
, or
$i=i^{\prime }$
and
$j<j^{\prime }$
and
$e_{ij}<f_{i^{\prime }j^{\prime }}$
for any choice of
$i,j,i^{\prime },j^{\prime }$
. Then the following are the initial terms of a reduced Gröbner basis of the toric ideal associated to
$P_{K_{a,b}}$
with respect to the degrevlex order:
$$\begin{eqnarray}\displaystyle e_{ij}f_{ij} & & \displaystyle \quad \text{for all }i,j\text{;}\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle e_{ij}e_{i^{\prime }j^{\prime }}\text{and }f_{ij}f_{i^{\prime }j^{\prime }} & & \displaystyle \quad \text{whenever }i<i^{\prime }\text{and }j>j^{\prime }\text{;}\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle e_{ij}f_{i^{\prime }j}\text{ and }f_{ji}e_{ji^{\prime }} & & \displaystyle \quad \text{for all }j\neq 1.\end{eqnarray}$$
In particular, since all initial terms are quadratic and square free the induced triangulation of
$\unicode[STIX]{x2202}P_{K_{a,b}}$
is unimodular and flag.
4 Complete bipartite graphs
This section is primarily dedicated to the case of complete bipartite graphs; however, a few statements generalize to arbitrary graphs. Let
$h_{a,b}^{\ast }(t)$
denote the
$h^{\ast }$
-polynomial of
$P_{K_{a+1,b+1}}$
. The goal of this section is to study arithmetic properties of
$h_{a,b}^{\ast }(t)$
. The first main result is the following simple expression for
$h_{a,b}^{\ast }(t)$
.
Theorem 4.1. For all
$a,b\geqslant 0$
,
$$\begin{eqnarray}h_{a,b}^{\ast }(t)=\mathop{\sum }_{i=0}^{\min (a,b)}\binom{2i}{i}\binom{a}{i}\binom{b}{i}t^{i}(1+t)^{a+b+1-2i}.\end{eqnarray}$$
In particular,
$h_{a,b}^{\ast }(t)$
is
$\unicode[STIX]{x1D6FE}$
-positive.
In §§4.1, 4.2 and 4.3, we employ methods from geometric, enumerative and bijective combinatorics to describe
$h_{a,b}^{\ast }(t)$
. These are essential in the proof of Theorem 4.1 in §4.4. In §§4.5, 4.6 and 4.7 we study arithmetic properties of
$h_{a,b}^{\ast }(t)$
.
4.1 Colorings
In this section we give a combinatorial interpretation for the right-hand side of (4.1). At the same time we give an alternative expression which serves as a first step towards a proof of Theorem 4.1.
We consider disjoint sets
$A$
and
$B$
with
$|A|=a$
and
$|B|=b$
, and colorings of
$A\sqcup B$
, that is, maps
$c:A\sqcup B\rightarrow \{R,G,W,B\}$
, where
$R,G,W$
and
$B$
stand for red, green, white and black, respectively. Let
$g(c):=|c^{-1}(G)|$
denote the number of green elements colored by
$c$
, and let
$r(c),w(c)$
and
$b(c)$
be defined analogously. A coloring is called good if the number of red elements in
$A$
equals the number of green elements in
$B$
, and at the same time, the number of green elements in
$A$
equals the number of red elements in
$B$
. In particular,
$g(c)=r(c)$
for every good coloring
$c$
.
Proposition 4.2.
$$\begin{eqnarray}\displaystyle (1+t)\!\!\mathop{\sum }_{\text{good}~c}\!\!t^{g(c)+w(c)} & = & \displaystyle \mathop{\sum }_{i=0}^{\min (a,b)}\!\!\binom{2i}{i}\binom{a}{i}\binom{b}{i}t^{i}(1+t)^{a+b+1-2i}\nonumber\\ \displaystyle & = & \displaystyle (1+t)\!\mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\!\binom{a}{i}\binom{b}{j}\binom{a-i+j}{j}\binom{b+i-j}{i}t^{i+j},\nonumber\\ \displaystyle & & \displaystyle\end{eqnarray}$$
where the first sum is taken over all good colorings of
$A\sqcup B$
.
Proof. We prove that both expressions on the right-hand side equal to the one on the left-hand side.
First expression. Let
$i$
be the number of elements in
$A$
that are either red or green. There are
$(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)$
possibilities of choosing the subset of elements in
$A$
that are either green or red. Since we only consider good colorings, there are
$\binom{b}{i}$
possibilities for choosing the subset of all green or red elements in
$B$
. Among these
$2i$
chosen red or green elements in
$A\sqcup B$
we have
$(\!\begin{smallmatrix}2i\\ i\end{smallmatrix}\!)$
possibilities to choose the red elements. It remains to choose
$w$
white elements which accounts for
$(\!\begin{smallmatrix}a+b-2i\\ w\end{smallmatrix}\!)$
possibilities. As
$(1+t)^{a+b-2i}=\sum _{w}(\!\begin{smallmatrix}a+b-2i\\ w\end{smallmatrix}\!)t^{w}$
we see that indeed the left-hand side equals the first expression on the right-hand side.
Second expression. Let
$X$
be the subset of elements that are either green or white in
$A$
and let
$Y$
be the subset of green or white elements in
$B$
. Let
$|X|=i$
and
$|Y|=j$
. Then there are
$(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}b\\ j\end{smallmatrix}\!)$
possibilities to choose
$X$
and
$Y$
. To determine the red elements in
$A$
and the white elements in
$B$
we choose a subset
$S$
of
$(A\setminus X)\cup Y$
of cardinality
$j$
. We define
$S\cap A$
to be the subset of red elements in
$A$
and
$S\cap B$
to be the subset of white elements in
$B$
. There are
$(\!\begin{smallmatrix}a-i+j\\ j\end{smallmatrix}\!)$
possibilities to choose
$S$
and by construction, the number of red elements in
$A$
equals the number of green elements in
$B$
. It remains to choose the red elements in
$B$
and, simultaneously, the white elements in
$A$
in an analogous way, which accounts for another
$(\!\begin{smallmatrix}b-j+i\\ i\end{smallmatrix}\!)$
possibilities.◻
4.2 Triangulation
Let
$\unicode[STIX]{x1D6E5}$
be the unimodular triangulation defined by the Gröbner basis given in Theorem 3.9. Every maximal face
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}$
in the triangulation corresponds to a directed spanning tree
$T(\unicode[STIX]{x1D70E})$
of the graph in the following way. If
$e_{v}-e_{w}$
is a vertex of the maximal cell, then the directed edge
$(w,v)$
is present in
$T(\unicode[STIX]{x1D70E})$
. Since the non-zero vertices form a maximally linearly independent set,
$T(\unicode[STIX]{x1D70E})$
is a directed spanning tree. In the following, we think of
$K_{a+1,b+1}$
as drawn in the plane in such a way that the vertices lie on two parallel lines and the edges are represented by straight segments connecting its vertices. The vertices on the upper line are labeled by
$v_{0},v_{1},\ldots v_{a}$
, from left to right and the vertices on the lower line are labeled by
$w_{0},w_{1},\ldots ,w_{b}$
from left to right. A spanning tree is called planar if no two of its edges drawn as segments in that way intersect in their interior. Let
$T^{\uparrow }(\unicode[STIX]{x1D70E})$
denote the edge induced subtree of
$T(\unicode[STIX]{x1D70E})$
consisting of all edges that are directed from the lower towards the upper level of vertices, and, correspondingly, let
$T^{\downarrow }(\unicode[STIX]{x1D70E})$
denote the edge induced subgraph of downward oriented edges. If there are no upward oriented edges, then
$T^{\uparrow }(\unicode[STIX]{x1D70E}):=\{w_{0}\}$
and, respectively,
$T^{\downarrow }(\unicode[STIX]{x1D70E}):=\{v_{0}\}$
if there are no downward oriented edges. Let
${\mathcal{T}}=\{T(\unicode[STIX]{x1D70E})=(T^{\uparrow }(\unicode[STIX]{x1D70E}),T^{\downarrow }(\unicode[STIX]{x1D70E})):\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}\}$
be the set of all directed spanning trees corresponding to maximal cells in
$\unicode[STIX]{x1D6E5}$
.
The minimal non-faces given by the leading coefficients of the Gröbner basis description in Theorem 3.9 correspond to the subgraphs given in Figure 1. A directed spanning tree of
$K_{a+1,b+1}$
is therefore contained in
${\mathcal{T}}$
if and only if it does not contain any of these subgraphs. The following result characterizes the elements in
${\mathcal{T}}$
.
Proposition 4.3. Let
$T=(T^{\uparrow },T^{\downarrow })$
be a directed spanning tree of
$K_{a+1,b+1}$
. Then
$T\in {\mathcal{T}}$
if and only if:
(i) either
$(v_{0},w_{0})\in T$
or
$(w_{0},v_{0})\in T$
; and(ii)
$T^{\uparrow }$
and
$T^{\downarrow }$
are planar subtrees; and(iii)
$T^{\uparrow }\cap T^{\downarrow }=\{v_{0}\}$
or
$T^{\uparrow }\cap T^{\downarrow }=\{w_{0}\}$
.
Proof. Let
$T$
be a directed spanning tree that satisfies (i),(ii) and (iii), then it is easily seen that it does not contain any forbidden subgraph given in Figure 1.
For the other direction we assume that
$T=T(\unicode[STIX]{x1D70E})$
for some
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}$
.
(i) Suppose there is no edge between
$v_{0}$
and
$w_{0}$
in
$T(\unicode[STIX]{x1D70E})$
. Since
$T(\unicode[STIX]{x1D70E})$
is a spanning tree there is a unique path
$v_{0}=p_{0}p_{1}\ldots p_{m}=w_{0}$
and, since
$K_{a+1,b+1}$
is bipartite, its length
$m$
is odd. By (3.3), every edge
$p_{i}p_{i+1}$
for all even
$i$
has the same orientation. In particular,
$p_{0}p_{1}$
and
$p_{m-1}p_{m}$
have the same orientation. However, since these two edges have to cross, this contradicts condition (3.2).
(ii) Planarity of
$T^{\uparrow }(\unicode[STIX]{x1D70E})$
and
$T^{\downarrow }(\unicode[STIX]{x1D70E})$
follows directly from condition (3.2).
(iii) Either
$T^{\uparrow }(\unicode[STIX]{x1D70E})$
and
$T^{\downarrow }(\unicode[STIX]{x1D70E})$
intersect in a vertex since
$T(\unicode[STIX]{x1D70E})$
is spanning. By condition (3.3) the only vertices that can possibly be contained in
$T^{\uparrow }(\unicode[STIX]{x1D70E})\cap T^{\downarrow }(\unicode[STIX]{x1D70E})$
are
$v_{0}$
or
$w_{0}$
, but not both by condition (3.1).◻
Forbidden configurations.
The triangulation
$\unicode[STIX]{x1D6E5}$
canonically induces a unimodular triangulation of every face of
$P_{K_{a+1,b+1}}$
. If
$F$
is a facet with facet-defining linear function
$f:V\rightarrow \mathbb{Z}$
, then a directed tree
$T\in {\mathcal{T}}$
corresponds to a maximal simplex in the triangulation of
$F$
if and only if
$f(q)-f(p)=1$
for every directed edge
$(p,q)\in T$
. In Example 3.6 we saw that the facet defined by
$f(v_{i})=0$
and
$f(w_{j})=1$
for all
$i,j$
is a product of simplices for which the normalized volume can easily be calculated to be
$(\!\begin{smallmatrix}a+b\\ a\end{smallmatrix}\!)$
. Together with Proposition 4.3 this yields the following well-known result.
Corollary 4.4. The number of (undirected) planar spanning trees of
$K_{a+1,b+1}$
is
$(\!\begin{smallmatrix}a+b\\ b\end{smallmatrix}\!)$
.
On the other hand, more generally, Proposition 4.3 allows us to determine the volume of arbitrary facets of
$P_{K_{a+1,b+1}}$
by counting spanning trees.
Proposition 4.5. Let
$F$
be a facet of
$P_{K_{a+1,b+1}}$
with facet-defining function
$f:V\rightarrow \mathbb{Z}$
where
$f(v_{i})=0$
and
$f(w_{j})=1$
for
$0\leqslant j\leqslant b_{1}$
and
$f(w_{j})=-1$
for
$b_{1}<j\leqslant b$
. Let
$b_{2}=b-b_{1}$
. Then
$F$
has normalized volume
$$\begin{eqnarray}\mathop{\sum }_{i=0}^{a}\binom{b_{1}+i}{b_{1}}\binom{b_{2}+a-i-1}{b_{2}-1}\binom{a}{i}.\end{eqnarray}$$
Proof. Let
$B_{1}=\{w_{j}:j\leqslant b_{1}\}$
and
$B_{2}=\{w_{j}:j>b_{1}\}$
. Let
$\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}$
be a maximal simplex in the triangulation given by the Gröbner basis. Then
$\unicode[STIX]{x1D70E}$
is contained in
$F$
if and only if all edges of
$T^{\uparrow }(\unicode[STIX]{x1D70E})$
start in
$B_{2}$
and all edges of
$T^{\downarrow }(\unicode[STIX]{x1D70E})$
end in
$B_{1}$
. By condition (iii) of Proposition 4.3,
$T^{\uparrow }(\unicode[STIX]{x1D70E})\cap T^{\downarrow }(\unicode[STIX]{x1D70E})=\{v_{0}\}$
. By choosing the vertices of
$\{v_{1},\ldots ,v_{a}\}$
contained in
$T^{\downarrow }(\unicode[STIX]{x1D70E})$
and counting the number of possible planar spanning trees
$T^{\uparrow }(\unicode[STIX]{x1D70E})$
and
$T^{\downarrow }(\unicode[STIX]{x1D70E})$
we obtain the claimed formula as the number of directed spanning trees corresponding to maximal simplices contained in
$F$
which equals the normalized volume of
$F$
.◻
4.3 Half-open triangulation
In this section we will give a combinatorial description of
$h_{a,b}^{\ast }(t)$
by decomposing
$P_{K_{a+1,b+1}}$
into half-open unimodular simplices of
$\unicode[STIX]{x1D6E5}$
.
For every
$T\in {\mathcal{T}}$
and every directed edge
$\vec{e}$
of
$T$
,
$T\setminus \{\vec{e}\}$
decomposes into two trees (possibly without edges) corresponding to a face of codimension one of
$\unicode[STIX]{x1D6E5}$
containing the origin. Let
$U_{1}$
be the component containing
$w_{0}$
and let
$U_{2}$
denote the other component. By construction,
$\vec{e}$
connects
$U_{1}$
and
$U_{2}$
. We call
$\vec{e}$
ingoing (into
$U_{1}$
) if its orientation goes from a vertex in
$U_{2}$
into a vertex in
$U_{1}$
.
Proposition 4.6. Let
$h_{a,b}^{\ast }(t)=\sum _{i=0}^{d}h_{i}^{\ast }t^{i}$
. Then
$$\begin{eqnarray}\displaystyle h_{i}^{\ast }=\sharp \{T\in {\mathcal{T}}:T\text{ has exactly }i\text{ ingoing edges}\}. & & \displaystyle \nonumber\end{eqnarray}$$
Proof. For every
$T\in {\mathcal{T}}$
and every directed edge
$\vec{e}$
of
$T$
, the facet-defining hyperplane of the facet corresponding to
$T\setminus \{\vec{e}\}$
is given by the linear function
$f:\mathbb{R}^{V}\rightarrow \mathbb{R}$
defined by
$$\begin{eqnarray}\displaystyle f(v)=\left\{\begin{array}{@{}ll@{}}d+1-|U_{1}|\quad & \text{for every }v\text{ contained in }U_{1},\\ -|U_{1}|\quad & \text{otherwise},\end{array}\right. & & \displaystyle \nonumber\end{eqnarray}$$
where
$|U_{1}|$
denotes the number of vertices in
$U_{1}$
. This is easily seen as
$f(v)-f(w)=0$
for all edges
$(w,v)\in T\setminus \{\vec{e}\}$
. Let
$t\gg 0$
large and let
$q\in \mathbb{R}^{V}$
be the point defined by
$q_{v_{i}}=-t^{a+1-i}$
and
$q_{w_{i}}=-t^{a+b+2-i}$
. Since
$t\gg 0$
, then
$q_{v}\gg q_{w_{0}}$
for all vertices
$v$
in
$K_{a+1,b+1}$
and therefore
$f(q)<0$
. Let
$\tilde{q}=q-\unicode[STIX]{x1D706}(1,\ldots ,1)\in \mathbb{R}^{|V|}$
, be such that the sum of coordinates of
$\tilde{q}$
equals
$0$
. In other words
$\tilde{q}$
belongs to the linear span of
$P_{K_{a+1,b+1}}$
. We have
$f(\tilde{q})=f(q)$
, as
$\sum _{v}f(v)=0$
.
If
$\vec{e}=(v,w)$
is oriented into
$U_{1}$
, then
$f(w)-f(v)=d+1>0$
; otherwise
$f(w)-f(v)=-d-1<0$
. That is, in the former case,
$\tilde{q}$
is beyond the facet-defining hyperplane. The claim follows now with Proposition 2.1.◻
4.4 Proof of Theorem 4.1
This section is devoted to the proof of Theorem 4.1.
For any
$T\in {\mathcal{T}}$
let
$A^{\uparrow }$
denote the vertices in the upper level and
$B^{\uparrow }$
the vertices in the lower level contained in
$T^{\uparrow }$
. Accordingly,
$A^{\downarrow }$
denotes the vertices in the upper level and
$B^{\downarrow }$
the vertices in the lower level contained in
$T^{\downarrow }$
.
Lemma 4.7. Let
$T\in {\mathcal{T}}$
. Then the number of ingoing edges in
$T$
equals:
(i)
$|A^{\downarrow }|+|B^{\uparrow }|-2$
, if
$T^{\uparrow }\cap T^{\downarrow }=\{v_{0}\}$
and
$w_{0}\in T^{\uparrow }$
;(ii)
$|A^{\downarrow }|+|B^{\uparrow }|$
, if
$T^{\uparrow }\cap T^{\downarrow }=\{v_{0}\}$
and
$w_{0}\in T^{\downarrow }$
;(iii)
$|A^{\downarrow }|+|B^{\uparrow }|-1$
, if
$T^{\uparrow }\cap T^{\downarrow }=\{w_{0}\}$
.
In particular, the number of ingoing edges of
$T$
only depends on
$|A^{\downarrow }|$
and
$|B^{\uparrow }|$
.
Proof. (i) In every vertex of
$A^{\downarrow }\setminus \{v_{0}\}$
ends exactly one ingoing edge of
$T^{\downarrow }$
and every vertex of
$B^{\uparrow }\setminus \{w_{0}\}$
is incident to exactly one ingoing edge of
$T^{\uparrow }$
.
(ii) Every vertex in
$A^{\downarrow }$
is an endpoint of exactly one ingoing edge of
$T^{\downarrow }$
and in every vertex of
$B^{\uparrow }$
ends exactly one ingoing edge of
$T^{\uparrow }$
.
(iii) Every vertex in
$A^{\downarrow }$
is incident to exactly one ingoing edge of
$T^{\downarrow }$
and every vertex of
$B^{\uparrow }\setminus \{w_{0}\}$
is an endpoint of exactly one ingoing edge of
$T^{\uparrow }$
.◻
Proof of Theorem 4.1.
By Proposition 4.6, the
$h^{\ast }$
-polynomial of
$P_{K_{a+1,b+1}}$
corresponds to the sum of the numbers of all ingoing edges of all
$T\in {\mathcal{T}}$
. To determine this number we partition the elements of
${\mathcal{T}}$
according to the cases (i), (ii) and (iii) in Lemma 4.7. Let
${\mathcal{T}}^{\prime }$
,
${\mathcal{T}}^{\prime \prime }$
and
${\mathcal{T}}^{\prime \prime \prime }$
denote the subset of
${\mathcal{T}}$
satisfying condition (i), (ii) or (iii), respectively, and for all
$T\in {\mathcal{T}}$
let
$\unicode[STIX]{x1D6FC}(T)$
denote the number of ingoing edges. Since by Lemma 4.7, the number of ingoing edges only depends on
$|B^{\uparrow }|$
and
$|A^{\downarrow }|$
, it suffices to consider all possible choices of
$B^{\uparrow }$
and
$A^{\downarrow }$
(equivalently,
$B^{\downarrow }$
and
$A^{\uparrow }$
) and weighting with the corresponding number of pairs of spanning trees on
$A^{\uparrow }\sqcup B^{\uparrow }$
and
$A^{\downarrow }\sqcup B^{\downarrow }$
. We will use Corollary 4.4 for counting the possible spanning trees
$A^{\uparrow }\sqcup B^{\uparrow }$
and
$A^{\downarrow }\sqcup B^{\downarrow }$
.
Type (i). Let
$j+1:=|B^{\uparrow }|$
and
$i+1:=|A^{\uparrow }|$
, and, equivalently,
$b-j=|B^{\downarrow }|$
and
$a+1-i=|A^{\downarrow }|$
. By Lemma 4.7 we obtain
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{T\in {\mathcal{T}}^{\prime }}t^{\unicode[STIX]{x1D6FC}(T)} & = & \displaystyle \mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{i+j}{j}\binom{a+b-i-j-1}{b-j-1}t^{j+a-i}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{a-i+j}{j}\binom{b+i-j-1}{i}t^{i+j},\end{eqnarray}$$
where the last equation follows from a change of variables
$i\mapsto a-i$
.
Type (ii). Let
$j:=|B^{\uparrow }|$
and
$i+1:=|A^{\uparrow }|$
, and, equivalently,
$b-j+1=|B^{\downarrow }|$
and
$a+1-i=|A^{\downarrow }|$
. By Lemma 4.7 we obtain
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{T\in {\mathcal{T}}^{\prime \prime }}t^{\unicode[STIX]{x1D6FC}(T)} & = & \displaystyle \mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{i+j-1}{j-1}\binom{a+b-i-j}{b-j}t^{j+a-i+1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{a-i+j-1}{j-1}\binom{b+i-j}{i}t^{i+j+1}\end{eqnarray}$$
with the convention that
$(\!\begin{smallmatrix}k\\ -1\end{smallmatrix}\!)=1$
if
$k=-1$
and is equal to zero otherwise.
Type (iii). Let
$j+1:=|B^{\uparrow }|$
and
$i:=|A^{\uparrow }|$
, and, equivalently,
$b-j+1=|B^{\downarrow }|$
and
$a+1-i=|A^{\downarrow }|$
. By Lemma 4.7 we obtain
$$\begin{eqnarray}\displaystyle \mathop{\sum }_{T\in {\mathcal{T}}^{\prime \prime \prime }}t^{\unicode[STIX]{x1D6FC}(T)} & = & \displaystyle \mathop{\sum }_{i=1}^{a+1}\mathop{\sum }_{j=0}^{b}\binom{a+1}{i}\binom{b}{j}\binom{i+j-1}{i-1}\binom{a+b-i-j}{a-i}t^{j+a-i+1}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a+1}{i}\binom{b}{j}\binom{a-i+j}{j}\binom{b+i-j-1}{i-1}t^{i+j}\nonumber\\ \displaystyle & = & \displaystyle \mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{a-i+j}{j}\binom{b+i-j-1}{i-1}t^{i+j}\end{eqnarray}$$
$$\begin{eqnarray}\displaystyle & & \displaystyle +\,\mathop{\sum }_{i=0}^{a-1}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{a-i+j-1}{j}\binom{b+i-j}{i}t^{i+j+1}\end{eqnarray}$$
again with the convention that
$(\!\begin{smallmatrix}k\\ -1\end{smallmatrix}\!)=1$
if
$k=-1$
and is equal to zero otherwise.
Summing up (4.3), (4.5), (4.4) and (4.6) we obtain
$$\begin{eqnarray}\mathop{\sum }_{T\in {\mathcal{T}}}t^{\unicode[STIX]{x1D6FC}}(T)=\mathop{\sum }_{i=0}^{a}\mathop{\sum }_{j=0}^{b}\binom{a}{i}\binom{b}{j}\binom{a-i+j}{j}\binom{b+i-j}{i}(t^{i+j}+t^{i+j+1}),\end{eqnarray}$$
and therefore the proof follows with Proposition 4.2.◻
4.5 Roots
In this section we study the roots of the polynomial
$h_{a,b}^{\ast }(t)$
. By employing techniques of interlacing polynomials we prove that all roots are real. The following is our main result.
Theorem 4.8. For all
$a,b\geqslant 0$
the polynomial
$h_{a,b}^{\ast }(t)$
has only real roots and
$$\begin{eqnarray}h_{a,b-1}^{\ast }(t)\preccurlyeq h_{a,b}^{\ast }(t).\end{eqnarray}$$
We are going to prove Theorem 4.8 by investigating the roots of the
$\unicode[STIX]{x1D6FE}$
-polynomial of
$h_{a,b}^{\ast }(t)$
which equals
$\unicode[STIX]{x1D6FE}_{a,b}(t):=\sum _{i\geqslant 0}(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}b\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}2i\\ i\end{smallmatrix}\!)t^{i}$
by Theorem 4.1.
Proposition 4.9. For all
$a,b\geqslant 1$
$$\begin{eqnarray}\unicode[STIX]{x1D6FE}_{a,b-1}(t)\preccurlyeq \unicode[STIX]{x1D6FE}_{a,b}(t).\end{eqnarray}$$
Proof. By Theorem 2.4,
$\big\{(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)i!\big\}_{i\geqslant 0}$
is a multiplier sequence, since
$\sum _{i\geqslant 0}(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)i!(x^{i}/i!)=(x+1)^{a}$
is real-rooted. Furthermore, by [Reference Craven and Csordas8, Theorem 3.14], we have also that
$\big\{(\!\begin{smallmatrix}2i\\ i\end{smallmatrix}\!)(1/i!)\big\}_{i\geqslant 0}$
is a multiplier sequence. Multiplication yields that
$\big\{(\!\begin{smallmatrix}2i\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)\big\}_{i\geqslant 0}$
is a multiplier sequence. Since
$(t+1)^{b-1}$
interlaces
$(t+1)^{b}$
we obtain the result by applying the multiplier sequence
$\big\{(\!\begin{smallmatrix}2i\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)\big\}_{i\geqslant 0}$
to these two polynomials by Corollary 2.3.◻
In certain cases, interlacing of the
$\unicode[STIX]{x1D6FE}$
-polynomials of two palindromic polynomials implies interlacing of the polynomials themselves.
Lemma 4.10. Let
$f_{1}(t)$
and
$f_{2}(t)$
be
$\unicode[STIX]{x1D6FE}$
-positive polynomials with
$\deg f_{2}(t)=\deg f_{1}(t)+1$
and
$f_{1}(0),f_{2}(0)\neq 0$
. Let
$\unicode[STIX]{x1D6FE}_{1}(t)$
and
$\unicode[STIX]{x1D6FE}_{2}(t)$
be the
$\unicode[STIX]{x1D6FE}$
-polynomials of
$f_{1}(t)$
and
$f_{2}(t)$
, respectively. If
$\unicode[STIX]{x1D6FE}_{1}(t)\preccurlyeq \unicode[STIX]{x1D6FE}_{2}(t)$
, then
$f_{1}(t)\preccurlyeq f_{2}(t)$
.
Proof. Let
$\unicode[STIX]{x1D6FE}_{i}(t)=c_{i}\prod _{j}(t+a_{i,j})$
for
$i=1,2$
. Since
$f_{i}$
has only non-negative coefficients and
$f_{i}(0)\neq 0$
it follows that
$a_{i,j}>0$
for all
$j$
. By [Reference Gal17, Proposition 2.1.1]
$\unicode[STIX]{x1D6FE}_{i}(t)$
is the unique polynomial such that
$$\begin{eqnarray}f_{i}=(1+t)^{\deg f_{i}}c_{i}\unicode[STIX]{x1D6FE}_{i}\biggl(\frac{t}{(1+t)^{2}}\biggr)=(1+t)^{\deg f_{i}-2\deg \unicode[STIX]{x1D6FE}_{i}}c_{i}\mathop{\prod }_{j}(t+a_{i,j}(1+t)^{2}).\end{eqnarray}$$
Since
$a_{i,j}>0$
, every factor of the form
$(t+a_{i,j}(1+t)^{2})$
contributes to two distinct negative real roots of
$f_{i}$
, say
$b_{i,j,+}>-1>b_{i,j,-}$
, which are reciprocals of each other. Calculating these roots explicitly shows that the larger root
$b_{i,j,+}$
is monotonically increasing with
$a_{i,j}$
and, accordingly, the smaller root
$b_{i,j,-}$
is monotonically decreasing. Let
$d=\deg \unicode[STIX]{x1D6FE}_{2}$
. Then, if
$\deg \unicode[STIX]{x1D6FE}_{1}=\deg \unicode[STIX]{x1D6FE}_{2}-1$
we obtain
$$\begin{eqnarray}\displaystyle b_{2,1,-} & & \displaystyle <b_{1,1,-}<\cdots <b_{1,d-1,-}<b_{2,d,-}<-1\nonumber\\ \displaystyle & & \displaystyle <b_{2,d,+}<b_{1,d-1,+}<\cdots <b_{1,1,+}<b_{2,1,+}.\end{eqnarray}$$
Since
$\deg f_{2}-2\deg \unicode[STIX]{x1D6FE}_{2}=\deg f_{1}-2\deg \unicode[STIX]{x1D6FE}_{1}-1$
, the multiplicity of the zero
$-1$
in
$f_{2}$
is smaller by one than the multiplicity in
$f_{1}$
and thus
$f_{1}\preccurlyeq f_{2}$
follows with (4.7). In the other case, if
$d=\deg \unicode[STIX]{x1D6FE}_{1}=\deg \unicode[STIX]{x1D6FE}_{2}$
we have
$$\begin{eqnarray}\displaystyle b_{2,1,-} & & \displaystyle <b_{1,1,-}<\cdots <b_{2,d,-}<b_{1,d,-}<-1\nonumber\\ \displaystyle & & \displaystyle <b_{1,d,+}<b_{2,d,+}<\cdots <b_{1,1,+}<b_{2,1,+}.\end{eqnarray}$$
In this case,
$\deg f_{2}-2\deg \unicode[STIX]{x1D6FE}_{2}=\deg f_{1}-2\deg \unicode[STIX]{x1D6FE}_{1}+1$
, that is, the multiplicity of the zero
$-1$
in
$f_{2}$
is greater by one than the multiplicity in
$f_{1}$
, and thus
$f_{1}\preccurlyeq f_{2}$
follows with (4.8).◻
4.6 Flag simplicial complexes and
$\unicode[STIX]{x1D6FE}$
-polynomials
In [Reference Nevo and Petersen28], Nevo and Petersen conjecture the following.
Conjecture 4.11 [Reference Nevo and Petersen28, Conjecture 6.3].
The
$\unicode[STIX]{x1D6FE}$
-polynomial of any flag triangulation of a simplicial sphere is the
$f$
-polynomial of a balanced simplicial complex.
Equivalently, the coefficients of the
$\unicode[STIX]{x1D6FE}$
-polynomial satisfies the so-called Frankl–Füredi–Kalai inequalities [Reference Frankl, Füredi and Kalai15]. Towards that conjecture we prove the following.
Theorem 4.12. The
$\unicode[STIX]{x1D6FE}$
-polynomial of any flag unimodular triangulation of
$\unicode[STIX]{x2202}P_{K_{a+1,b+1}}$
is the
$f$
-polynomial of a flag balanced simplicial complex.
Proof. By Theorem 4.1 the
$h^{\ast }$
-polynomial of
$P_{K_{a+1,b+1}}$
is
$\unicode[STIX]{x1D6FE}$
-positive with
$\unicode[STIX]{x1D6FE}$
-polynomial
$\unicode[STIX]{x1D6FE}_{a,b}(t)=\sum _{i\geqslant 0}(\!\begin{smallmatrix}2i\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}a\\ i\end{smallmatrix}\!)(\!\begin{smallmatrix}b\\ i\end{smallmatrix}\!)t^{i}$
. Since the
$h^{\ast }$
-polynomial equals the
$h$
-polynomial of any unimodular triangulation of the boundary of
$P_{K_{a+1,b+1}}$
, the proof follows from Proposition 4.13 below.◻
Proposition 4.13. For all
$a,b\geqslant 1$
the polynomial
$$\begin{eqnarray}\mathop{\sum }_{i\geqslant 0}\binom{2i}{i}\binom{a}{i}\binom{b}{i}t^{i}\end{eqnarray}$$
is the
$f$
-polynomial of a flag balanced simplicial complex.
Proof. Without loss of generality we may assume that
$a\leqslant b$
. Let
$X=\{x_{i,j}:1\leqslant i\leqslant a,1\leqslant j\leqslant b\}$
,
$Y=\{y_{i,j}:1\leqslant i\leqslant a,1\leqslant j\leqslant b\}$
and let
$V=X\cup Y$
be the set of vertices of the simplicial complex
$\unicode[STIX]{x1D6E5}$
that we define by the following set of minimal non-faces:
∙
$\{x_{i,j},x_{i^{\prime },j^{\prime }}\}$
for
$i\leqslant i^{\prime }$
and
$j\geqslant j^{\prime }$
;∙
$\{y_{i,j},y_{i^{\prime },j^{\prime }}\}$
for
$i\leqslant i^{\prime }$
and
$j\geqslant j^{\prime }$
; and∙
$\{x_{i,j},y_{i^{\prime },j}\}$
and
$\{x_{i,j},y_{i,j^{\prime }}\}$
for any
$i,j,i^{\prime },j^{\prime }$
.
By definition,
$\unicode[STIX]{x1D6E5}$
is a flag simplicial complex, and of dimension
$(a-1)$
since
$\{x_{1,1},\ldots ,x_{a,a}\}$
defines a simplex. Assigning to all
$x_{i,j}$
and
$y_{i,j}$
the color
$i$
moreover shows that
$\unicode[STIX]{x1D6E5}$
is a balanced simplicial complex.
It remains to prove that the
$f$
-vector of
$\unicode[STIX]{x1D6E5}$
is as predicted in the proposition. To see that let
$A=\{1,\ldots ,a\}$
and
$B=\{1,\ldots ,b\}$
. Reminiscent of the proof of Proposition 4.2 we define a partial coloring with colors red and green of the set
$A\sqcup B$
to be good if there are as many green elements in
$A$
as there are red elements in
$B$
and at the same time there are as many green elements in
$B$
as there are red elements in
$A$
. Just as in Proposition 4.2 we see that the polynomial we are interested in is of the form
$$\begin{eqnarray}\mathop{\sum }_{\text{good }c}t^{g(c)}=\mathop{\sum }_{i\geqslant 0}\binom{2i}{i}\binom{a}{i}\binom{b}{i}t^{i},\end{eqnarray}$$
where the sum is over all good colorings
$c$
and
$g(c)$
is the number of green elements. To finish the proof we establish a bijection between simplices in
$\unicode[STIX]{x1D6E5}$
with
$k$
vertices and good colorings of
$A\sqcup B$
with
$k$
green elements.
For the first direction, for every simplex
$\unicode[STIX]{x1D70E}$
of
$\unicode[STIX]{x1D6E5}$
let
$$\begin{eqnarray}\displaystyle & X_{A}(\unicode[STIX]{x1D70E})=\{i:x_{i,j}\in \unicode[STIX]{x1D70E}\},\qquad X_{B}(\unicode[STIX]{x1D70E})=\{j:x_{i,j}\in \unicode[STIX]{x1D70E}\}, & \displaystyle \nonumber\\ \displaystyle & Y_{A}(\unicode[STIX]{x1D70E})=\{i:y_{i,j}\in \unicode[STIX]{x1D70E}\},\qquad Y_{B}(\unicode[STIX]{x1D70E})=\{j:y_{i,j}\in \unicode[STIX]{x1D70E}\}. & \displaystyle \nonumber\end{eqnarray}$$
Then, by definition of
$\unicode[STIX]{x1D6E5}$
,
$$\begin{eqnarray}X_{A}(\unicode[STIX]{x1D70E})\cap Y_{A}(\unicode[STIX]{x1D70E})=\emptyset \quad \text{and}\quad X_{B}(\unicode[STIX]{x1D70E})\cap Y_{B}(\unicode[STIX]{x1D70E})=\emptyset .\end{eqnarray}$$
We define a coloring of
$A\sqcup B$
by setting
$X_{A}\subseteq A$
to be the green elements and
$Y_{A}\subseteq A$
to red elements in
$A$
, and
$X_{B}\subseteq B$
the red elements and
$Y_{B}\subseteq B$
the green elements in
$B$
. Since every
$x_{i,j}$
and
$y_{i^{\prime },j^{\prime }}$
in
$\unicode[STIX]{x1D70E}$
contributes to precisely one green element and one red element, this defines a good coloring and
$|\unicode[STIX]{x1D70E}|$
equals the total number of green elements in
$A\sqcup B$
.
For the inverse map, consider a good coloring of
$A\sqcup B$
with
$k$
green elements and let:
∙
$i_{1}<i_{2}<\cdots <i_{s}$
be the green elements of
$A$
;∙
$j_{1}<j_{2}<\cdots <j_{t}$
be the red elements of
$B$
;∙
$i_{1}^{\prime }<\cdots <i_{k-s}^{\prime }$
be the red elements of
$A$
;∙
$j_{1}^{\prime }<\cdots <j_{k-t}^{\prime }$
be the green elements of
$B$
.
Since the coloring is good, we have
$s=t$
and we may associate a simplex with vertices
$x_{i_{1},j_{1}},x_{i_{2},j_{2}},\ldots ,x_{i_{s},j_{s}}$
and
$y_{i_{1}^{\prime },j_{1}^{\prime }},\ldots ,y_{i_{k-s}^{\prime },j_{k-s}^{\prime }}$
. By definition, this simplex belongs to
$\unicode[STIX]{x1D6E5}$
, has
$k$
vertices and both maps are easily seen to be inverses of each other, which finishes the proof.◻
4.7 A recursive formula
In [Reference Higashitani, Kummer and Michałek21, Proposition 4.5] recursive formulas for
$h_{a,b}^{\ast }$
were given for any fixed
$a\leqslant 2$
. These formulas played a fundamental role in the study of the roots of the Ehrhart polynomial of
$P_{K_{a+1,b+1}}$
. Here we present a general formula for arbitrary
$a$
and
$b$
.
Proposition 4.14. For all
$a,b\geqslant 1$
$$\begin{eqnarray}(b-a)h_{a,b}^{\ast }=(1+t)(bh_{a,b-1}^{\ast }-ah_{a-1,b}^{\ast }).\end{eqnarray}$$
Proof. By Theorem 4.1,
$$\begin{eqnarray}b(h_{a,b}^{\ast }-(1+t)h_{a,b-1}^{\ast })=\mathop{\sum }_{i\geqslant 0}\binom{2i}{i}\binom{a}{i}t^{i}(1+t)^{a+b+1-2i}b\left(\binom{b}{i}-\binom{b-1}{i}\right).\end{eqnarray}$$
As
$b((\!\begin{smallmatrix}b\\ i\end{smallmatrix}\!)-(\!\begin{smallmatrix}b-1\\ i\end{smallmatrix}\!))=i(\!\begin{smallmatrix}b\\ i\end{smallmatrix}\!)$
the above polynomial equals
$$\begin{eqnarray}\mathop{\sum }_{i\geqslant 0}i\binom{2i}{i}\binom{a}{i}\binom{b}{i}t^{i}(1+t)^{a+b+1-2i}.\end{eqnarray}$$
However, by the same argument, this is also equal to
$$\begin{eqnarray}a(h_{a,b}^{\ast }-(1+t)h_{a-1,b}^{\ast }),\end{eqnarray}$$
which proves the proposition.◻
Acknowledgements
The authors would like to thank the Mathematisches Forschungsinstitut Oberwolfach for hosting the mini-workshop “Lattice polytopes: methods, advances and applications” in fall 2017 during which this project evolved. They also would like to thank Petter Bränden, Christian Haase, Eran Nevo and the anonymous referee for helpful comments. Akihiro Higashitani was partially supported by JSPS Grant-in-Aid for Young Scientists (B)
$\sharp$
17K14177. Katharina Jochemko was supported by the Knut and Alice Wallenberg foundation. Mateusz Michaek was supported by the Polish National Science Centre grant no. 2015/19/D/ST1/01180.
