The h^{∗}-Polynomial of the Cut Polytope of K_{2,m} in the Lattice Spanned by its Vertices

Ryuichi Sakamoto Department of Mathematical Sciences Graduate School of Science and Technology Kwansei Gakuin University Sanda, Hyogo 669-1337 Japan

                dpm86391@kwansei.ac.jp

Abstract

The cut polytope of a graph is an important object in several fields, such as functional analysis, combinatorial optimization, and probability. For example, Sturmfels and Sullivant showed that the toric ideals of cut polytopes are useful in algebraic statistics. In the theory of lattice polytopes, the h^{∗}-polynomial is an important invariant. However, except for trees, there are no classes of graphs for which the h^{∗}-polynomial of their cut polytope is explicitly specified. In the present paper, we determine the h^{∗}- polynomial of the cut polytope of the complete bipartite graph K_{2,m} using the theory of Gröbner bases of toric ideals.

1 Introduction

Given integer vectors v_{1}, …, v_{l} ∈ ℤ^{d}, let

conv(v_{1}, …, v_{l}) = {∑_{i=1}^{l} r_{i}v_{i} | 0 ≤ r_{i} ∈ ℝ, ∑_{i=1}^{l} r_{i} = 1} .

A set P ⊂ ℝ^{d} is called a lattice polytope if there exist v_{1}, …, v_{l} ∈ ℤ^{d} such that P = conv(v_{1}, …, v_{l}). Let P ⊂ ℝ^{d} be a lattice polytope of dimension d, where P ∩ ℤ^{d} = {a_{1}, …, a_{n}}. Let A_{P} be the integer matrix

A_{P} = (\begin{matrix}a_{1} & ⋯ & a_{n} \\ 1 & ⋯ & 1 \end{matrix}) .

The normalized Ehrhart polynomial i(P, m) is given by the following equation:

i(P, m) = |mP′ ∩ ℤA_{P}|,

where m ∈ ℕ, P′ = conv(\binom{a_{1}}{1}, …, \binom{a_{n}}{1}), mP′ = \{ma | a ∈ P′\}, and

ℤA_{P} = ℤ (\begin{matrix}a_{1} \\ 1 \end{matrix}) + ⋯ + ℤ (\begin{matrix}a_{n} \\ 1 \end{matrix}) .

In general, i(P, m) satisfies the following fundamental properties [4]:

• i(P, m) is a polynomial of degree d in m;

• i(P, 0) = 1.

The h^{∗}-polynomial h^{∗}(P, x) of P in the lattice ℤA_{P} is defined by

1 + ∑_{m=1}^{∞} i(P, m)x^{m} = \frac{h^{∗}(P, x)}{(1 − x)^{d+1}} .

In general, h^{∗}(P, x) satisfies the following properties:

• h^{∗}(P, x) = ∑_{i=0}^{d} h_{i}^{∗}x^{i}, where each h_{i}^{∗} is a nonnegative integer [18];

• i(P, m) = ∑_{i=0}^{d} h_{i}^{∗}\binom{m+d−i}{d};

• If h_{d}^{∗} > 0, then we have h_{i}^{∗} ≥ h_{1}^{∗} (1 ≤ i ≤ d − 1) [8, Theorem 1.1].

The third property is Hibi’s lower bound theorem. Since the h^{∗}-polynomial is defined in the lattice ℤA_{P}, P is a spanning lattice polytope [10], and a generalization of Hibi’s lower bound theorem is known:

• h_{i}^{∗} ≥ h_{1}^{∗} (1 ≤ i ≤ deg(h^{∗}(P, x)) − 1) [9, Corollary 1.6].

A polynomial f(x) of degree s is said to be palindromic if f(x) = x^{s}f(x^{−1}). Let K[A_{P}] be the toric ring of P. (The toric ring will be defined in Section 1.) If K[A_{P}] is normal (i.e., ℤ_{≥0}A_{P} = ℤA_{P} ∩ ℚ_{≥0}A_{P}, see [21, Proposition 13.5]) and Gorenstein, then it is known by [7, Lemma 4.22 (b)] and [3, P.235] that the h^{∗}-polynomial of P is palindromic. In the theory of lattice polytopes, h^{∗}-polynomials are important objects to study. For example, the h^{∗}-polynomials of stable set polytopes of graphs, order polytopes, and chain polytopes of posets were studied in [1, 19]. Let G be a finite connected simple graph with vertex set V (G) = {1, 2, …, m} and edge set E(G) = {e_{1}, e_{2}, …, e_{r}}. For two subsets A and B of V (G) such that A∩B = ∅, A∪B = V (G), we define a vector δ_{A|B} = (d_{1}, d_{2}, …, d_{r}) ∈ {0, 1}^{r} by

d_{i} = \begin{cases}1, & |A ∩ e_{i}| = 1; \\ 0, & otherwise. \end{cases}

Note that δ_{A|B} = δ_{B|A}. The cut polytope of G is the 0/1 polytope

Cut(G) = conv(δ_{A|B} |A, B ⊂ V (G), A ∩ B = ∅, A ∪ B = V (G)).

Example 1. Let G be a cycle of length 4, where V (G) = {1, 2, 3, 4} and E(G) = {e_{1} = {1, 2}, e_{2} = {2, 3}, e_{3} = {3, 4}, e_{4} = {1, 4}}. For subset A = {1, 2} ⊂ V (G), we compute δ_{A|B} = (d_{1}, d_{2}, d_{3}, d_{4}), where B = {3, 4}. Since |A ∩ e_{1}| = 2, we have d_{1} = 0. Similarly, we obtain d_{2} = 1, d_{3} = 0, and d_{4} = 1. Hence, δ_{A|B} = (0, 1, 0, 1). By computing δ_{A|B} for all subsets A ⊂ V (G), we obtain the cut polytope

Cut(G) = conv((0, 0, 0, 0), (1, 1, 0, 0), (1, 0, 1, 0), (1, 0, 0, 1), (0, 1, 1, 0), (0, 1, 0, 1), (0, 0, 1, 1), (1, 1, 1, 1)).

We define the graph theoretical terminology used in the present paper. A bridge of a graph G is an edge of G whose deletion increases the number of connected components, and a graph G is said to be bridgeless if G has no bridges. An induced cycle of G is a cycle of G that is an induced subgraph of G. A graph G is said to be chordal if G has no induced cycles of length ≥ 4. A graph H is called a minor of a graph G if H is obtained from G by a sequence of contractions and deletions of edges. On the other hand, if we cannot obtain H as a minor of G, then G is said to be H-minor free. A complete graph with n vertices is denoted by K_{n}, a complete bipartite graph with m + n vertices is denoted by K_{m,n}, and a cycle of length n is denoted by C_{n}. There is only one class of cut polytopes for which the h^{∗}-polynomial is explicitly known. Nagel and Petrović [12] showed that, if G is a tree with n ≥ 1 edges, then the h^{∗}-polynomial of the cut polytope in the lattice ℤA_{Cut(G)} is the Eulerian polynomial

A_{n}(x) := ∑_{w∈𝔖_{n}} x^{des(w)}

of degree n − 1. Here, 𝔖_{n} is a symmetric group and des(w) = |{i | w_{i} > w_{i+1}}| for w = w_{1}w_{2} ⋯ w_{n} ∈ 𝔖_{n}. It is known that A_{n}(x) is palindromic and unimodal. Ohsugi [14] showed that the toric ring of the cut polytope Cut(G) of a graph G is normal and Gorenstein if and only if G is K_{5}-minor free and satisfies one of the following:

1. G is a bipartite graph with no induced cycle of length ≥ 6.

2. G is a bridgeless chordal graph.

Thus, if G satisfies one of the above conditions, then the h^{∗}-polynomial of the cut polytope of G is palindromic, since the toric ring is normal and Gorenstein.

In the present paper, we determine the h^{∗}-polynomial of the cut polytope of a complete bipartite graph K_{2,n−2} and show that the h^{∗}-polynomial is (x+1)(A_{n−2}(x))^{2} using the theory of Gröbner bases of toric ideals. See [7, 21] for the details of Gröbner bases and toric ideals. Remark 2. We discuss the normalized Ehrhart polynomial

i(P, m) = |mP′ ∩ ℤA_{P}|

instead of the ordinary Ehrhart polynomial

|mP ∩ ℤ^{d}|

because the lattice spanned by the δ_{A|B} is important in the study of the cut polytopes. In fact, the characterization of the graph G satisfying ℤ_{≥0}B_{G} = ℤB_{G} ∩ ℚ_{≥0}B_{G}, where B_{G} = Cut(G) ∩ ℤ^{d}, is an important open problem. See [6] and the references therein. In addition, it has been conjectured that ℤ_{≥0}A_{Cut(G)} = ℤA_{Cut(G)} ∩ ℚ_{≥0}A_{Cut(G)} if and only if G is K_{5}-minor free [22]. See [13, 22].

2 Standard monomials of cut ideals of K_{2,n−2}

Let K[x] = K[x_{1}, …, x_{n}] be a polynomial ring in n variables over a field K. Let M_{n} be the set of all monomials of K[x]. A total order < on M_{n} is called a monomial order if < satisfies the following properties:

• For all 1 ≠ u ∈ M_{n}, 1 < u.

• If u < v (u, v ∈ M_{n}), then w · u < w · v for all w ∈ M_{n}.

We fix a monomial order <. For a nonzero polynomial f which belongs to K[x], the initial monomial in_{<}(f) of f is the greatest monomial in f with respect to <. The initial ideal of an ideal I ⊂ K[x] with respect to < is defined by in_{<}(I) = ⟨ in_{<}(f) | 0 ≠ f ∈ I⟩. A finite subset G = {g_{1}, …, g_{s}} ⊂ I is called a Gröbner basis of I with respect to < when in_{<}(I) = ⟨in_{<}(g_{1}), …,in_{<}(g_{s})⟩. See [7, Chapter 1] for the basic theory of Gröbner bases.

A d×n integer matrix A = (a_{1}, a_{2}, …, a_{n}) is called a configuration if there exists a vector c ∈ ℝ^{d} such that for all 1 ≤ i ≤ n, the inner product a_{i}·c is equal to 1. Let K[t_{1}^{±1}, t_{2}^{±1}, …, t_{d}^{±1}] be a Laurent polynomial ring over K. For an integer vector b = (b_{1}, b_{2}, …, b_{d}) ∈ ℤ^{d}, we define the Laurent monomial t^{b} = t_{1}^{b_{1}}t_{2}^{b_{2}} ⋯ t_{d}^{b_{d}} ∈ K[t_{1}^{±1}, t_{2}^{±1}, …, t_{d}^{±1}] and the toric ring K[A] = K[t^{a_{1}}, t^{a_{2}}, …, t^{a_{n}}]. Let π be a homomorphism π : K[x] → K[A], where π(x_{i}) = t^{a_{i}}. The kernel of π is called the toric ideal of A and denoted by I_{A}. We often regard A = (a_{1}, …, a_{n}) as a set A = {a_{1}, …, a_{n}}. Suppose that a set Δ consists of simplices and that each vertex of σ ∈ Δ belongs to A. Then Δ is called a covering of conv(A) if

conv(A) = ⋃_{F ∈Δ} F .

We say that a covering Δ is a triangulation of conv(A) if Δ is a simplicial complex. A triangulation Δ of a polytope conv(A) is unimodular if the normalized volume of any maximal simplex is equal to 1. For a configuration A, the initial complex with respect to < is defined by

Δ(in_{<}(I_{A})) := \{conv(B) | B ⊂ \{a_{1}, …, a_{n}\}, ∏_{a_{i}∈B}x_{i} ∉ \sqrt{in_{<}(I_{A})}\} .

It is known that Δ(in_{<}(I_{A})) is a triangulation of conv(A). Moreover, Δ(in_{<}(I_{A})) is unimodular if and only if in_{<}(I_{A}) is generated by squarefree monomials.

Example 3. Let A be a configuration

A = (a_{1}, a_{2}, a_{3}, a_{4}, a_{5}) = (\begin{matrix}0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \end{matrix}) .

The toric ideal of A is given by I_{A} = ⟨x_{1}x_{5}^{2} − x_{2}x_{3}x_{4}⟩. Let < be the lexicographic order on K[x_{1}, x_{2}, x_{3}, x_{4}, x_{5}] induced by the ordering x_{1} > x_{2} > x_{3} > x_{4} > x_{5}. Then

in_{<}(x_{1}x_{5}^{2} − x_{2}x_{3}x_{4}) = x_{1}x_{5}^{2}
in_{<}(I_{A}) = ⟨x_{1}x_{5}^{2}⟩
\sqrt{in_{<}(I_{A})} = ⟨x_{1}x_{5}⟩.

Thus, the maximal simplices of Δ(in_{<}(I_{A})) are

σ_{1} = conv(a_{1}, a_{2}, a_{3}, a_{4}) and σ_{2} = conv(a_{2}, a_{3}, a_{4}, a_{5}).

The triangulation Δ(in_{<}(I_{A})) is not unimodular, since the normalized volume of σ_{1} is 2.

A monomial is said to be a standard monomial of a toric ideal I_{A} with respect to a monomial order < if the monomial does not belong to in_{<}(I_{A}). If Δ(in_{<}(I_{A})) is unimodular, then the number of squarefree standard monomials of degree i corresponds to the number of (i − 1)-dimensional faces of Δ(in_{<}(I_{A})). See [7, 21] for details.

Let G be a graph with m vertices. We consider the configuration

A_{Cut(G)} = (\begin{matrix}δ_{A_{1}|B_{1}} & δ_{A_{2}|B_{2}} & ⋯ & δ_{A_{N} |B_{N}} \\ 1 & 1 & ⋯ & 1 \end{matrix} ) ,

where A_{i} ∩ B_{i} = ∅, A_{i} ∪ B_{i} = V (G) for 1 ≤ i ≤ N, and N = 2^{m−1}. The toric ideal of A_{Cut(G)} is called the cut ideal of G and is denoted by I_{G}. The notion of cut ideals was introduced in [22]. The toric ring and ideal of A_{Cut(G)} were investigated in, e.g., [5, 12, 11, 13, 16, 17]. The cut ideal I_{G} of a graph G is generated by quadratic binomials if and only if G is K_{4}-minor free [5]. The cut ideal I_{G} of a graph G has a quadratic Gröbner basis if G satisfies one of the following:

• G is (K_{4}, C_{5})-minor free, where K_{4} is a complete graph with 4 vertices, and C_{5} is a cycle of length 5 [17, Corollary 2.4];

• G is a cycle of length ≤ 7 [16, Theorem 2.3].

An unordered partition A|B of the vertex set V (G) consists of subsets A, B ⊂ V (G) such that A ∩ B = ∅, A ∪ B = V (G). Given an unordered partition A|B, we associate a variable q_{A|B}. In particular, q_{A|B} = q_{B|A}. Let K[q] be the polynomial ring in N = 2^{m−1} variables over a field K defined by

K[q] = K[q_{A_{1}|B_{1}}, …, q_{A_{N} |B_{N}}],

where {A_{1}|B_{1}, …, A_{N}|B_{N}} is the set of all unordered partitions of V (G). Let < be a reverse lexicographic order [7, Example 1.8 (b)] on K[q] that satisfies q_{A|B} < q_{C|D} with min{|A|, |B|} < min{|C|, |D|}. A quadratic Gröbner basis of the cut ideal of K_{2,n−2} with respect to < is given by the following proposition.

Proposition 4 ([17, Theorem 2.3]). Let K_{2,n−2} be the complete bipartite graph on the vertex set {1, 2} ∪ {3, …, n} for n ≥ 4. Then a Gröbner basis of I_{K_{2,n−2}} with respect to < consists of

1. q_{{1}∪A|{2}∪B}q_{{1}∪B|{2}∪A} − q_{∅|[n]}q_{{1,2}|{3,...,n}},

2. q_{A|B}q_{C|D} − q_{A∩C|B∪D}q_{A∪C|B∩D} (1 ∈ A ∩ C, 2 ∈ B ∩ D, A ⊄ C, C ⊄ A),

3. q_{A|B}q_{C|D} − q_{A∩C|B∪D}q_{A∪C|B∩D} (1, 2 ∈ A ∩ C, A ⊄ C, C ⊄ A).

The initial monomial of each binomial is the first monomial.

Example 5. Let K_{2,3} be the complete bipartite graph on the vertex set {1, 2} ∪ {3, 4, 5}. Then the configuration A_{Cut(K_{2,3})} is

A_{Cut(K_{2,3})} = (\begin{matrix}0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}) ,

and a Gröbner basis of I_{K_{2,3}} with respect to the monomial order < consists of the following binomials:

q_{{1}|{2,3,4,5}}q_{{2}|{1,3,4,5}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},
q_{{1,3}|{2,4,5}}q_{{2,3}|{1,4,5}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},
q_{{1,4}|{2,3,5}}q_{{2,4}|{1,3,5}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},
q_{{1,5}|{2,3,4}}q_{{2,5}|{1,3,4}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},

q_{{3}|{1,2,4,5}}q_{{4,5}|{1,2,3}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},
q_{{5}|{1,2,3,4}}q_{{3,4}|{1,2,5}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},
q_{{4}|{1,2,3,5}}q_{{3,5}|{1,2,4}} − q_{∅|{1,2,3,4,5}}q_{{1,2}|{3,4,5}},
q_{{4}|{1,2,3,5}}q_{{5}|{1,2,3,4}} − q_{∅|{1,2,3,4,5}}q_{{4,5}|{1,2,3}},
q_{{3}|{1,2,4,5}}q_{{5}|{1,2,3,4}} − q_{∅|{1,2,3,4,5}}q_{{3,5}|{1,2,4}},
q_{{3}|{1,2,4,5}}q_{{4}|{1,2,3,5}} − q_{∅|{1,2,3,4,5}}q_{{3,4}|{1,2,5}},
q_{{3,5}|{1,2,4}}q_{{4,5}|{1,2,3}} − q_{{5}|{1,2,3,4}}q_{{1,2}|{3,4,5}},
q_{{3,4}|{1,2,5}}q_{{3,5}|{1,2,4}} − q_{{3}|{1,2,4,5}}q_{{1,2}|{3,4,5}},
q_{{3,4}|{1,2,5}}q_{{4,5}|{1,2,3}} − q_{{4}|{1,2,3,5}}q_{{1,2}|{3,4,5}}
q_{{1,4}|{2,3,5}}q_{{1,5}|{2,3,4}} − q_{{1}|{2,3,4,5}}q_{{2,3}|{1,4,5}},
q_{{1,3}|{2,4,5}}q_{{1,5}|{2,3,4}} − q_{{1}|{2,3,4,5}}q_{{2,4}|{1,3,5}},
q_{{2,3}|{1,4,5}}q_{{2,4}|{1,3,5}} − q_{{2}|{1,3,4,5}}q_{{1,5}|{2,3,4}},
q_{{1,3}|{2,4,5}}q_{{1,4}|{2,3,5}} − q_{{1}|{2,3,4,5}}q_{{2,5}|{1,3,4}},
q_{{2,3}|{1,4,5}}q_{{2,5}|{1,3,4}} − q_{{2}|{1,3,4,5}}q_{{1,4}|{2,3,5}},
q_{{2,4}|{1,3,5}}q_{{2,5}|{1,3,4}} − q_{{2}|{1,3,4,5}}q_{{1,3}|{2,4,5}}.

The h^{∗}-polynomial h^{∗}(Cut(K_{2,3}), x) is

h^{∗}(Cut(K_{2,3}), x) = x^{5} + 9x^{4} + 26x^{3} + 26x^{2} + 9x + 1 = (x + 1)(x^{2} + 4x + 1)^{2}. Since the dimension of the cut polytopes of K_{2,n−2} is 2n − 4, the maximum degree of

squarefree standard monomials is 2n − 3. Note that the initial monomial q_{A|B}q_{C|D} of the binomials in the Gröbner basis in Proposition 4 satisfies one of the following conditions:

• 1 ∈ A ∩ C and 2 ∈ B ∩ D,

• 1, 2 ∈ A ∩ C. Hence, a squarefree monomial

q_{A_{1}|{1,2}∪B_{1}} … q_{A_{k}|{1,2}∪B_{k}} q_{{1}∪A′_{1}|{2}∪B′_{1}} … q_{{1}∪A′_{l}|{2}∪B′_{l}} ∈ K[q]

is standard if and only if both q_{A_{1}|{1,2}∪B_{1}} … q_{A_{k}|{1,2}∪B_{k}} and q_{{1}∪A′_{1}|{2}∪B′_{1}} … q_{{1}∪A′_{l}|{2}∪B′_{l}} are standard. Proposition 6. Each of the squarefree monomials

(1) q_{A_{1}|{1,2}∪B_{1}} … q_{A_{k}|{1,2}∪B_{k}}

(2) q_{{1}∪A′_{1}|{2}∪B′_{1}} … q_{{1}∪A′_{k}|{2}∪B′_{k}}, of degree k ≤ 2n − 3 is not divisible by the initial monomials if and only if, by changing indices if necessary,

(1) A_{1} ⊊ A_{2} ⊊ ⋯ ⊊ A_{k}, (2) A′_{1} ⊊ A′_{2} ⊊ ⋯ ⊊ A′_{k} and (A′_{1}, A′_{k}) ≠ (∅, {3, …, n}),

respectively. Moreover, the numbers of squarefree standard monomials of types (1) and (2) above are

(k − 1)!\left\{{n − 2 \atop k − 1}\right\} + 2k!\left\{{n − 2 \atop k}\right\} + (k + 1)!\left\{{n − 2 \atop k + 1}\right\},

2k!\left\{{n − 2 \atop k}\right\} + (k + 1)!\left\{{n − 2 \atop k + 1}\right\},

respectively, where \left\{{n \atop k}\right\} is the Stirling number of the second kind.

Proof. Let m_{1} = q_{A_{1}|{1,2}∪B_{1}} … q_{A_{k}|{1,2}∪B_{k}} and m_{2} = q_{{1}∪A′_{1}|{2}∪B′_{1}} … q_{{1}∪A′_{k}|{2}∪B′_{k}} be squarefree monomials.

First, suppose that m_{1} and m_{2} are standard. Since m_{1} is squarefree and is not divisible by the initial monomials q_{A|B}q_{C|D} (1, 2 ∈ A ∩ C, A ⊄ C, C ⊄ A), we can obtain B_{1} ⊋ ⋯ ⊋ B_{k−1} ⊋ B_{k} by changing indices if necessary. Then A_{1} ⊊ ⋯ ⊊ A_{k−1} ⊊ A_{k}. Similarly, since m_{2} is squarefree and is not divisible by the initial monomials q_{A|B}q_{C|D} (1 ∈ A ∩ C, 2 ∈ B ∩ D, A ⊄ C, C ⊄ A), we can obtain A′_{1} ⊊ ⋯ ⊊ A′_{k−1} ⊊ A′_{k} by changing indices if necessary. Moreover, since m_{2} is not divisible by the initial monomial q_{{1}|{2,3,...,n}}q_{{1,3,...,n}|{2}} of the binomial q_{{1}|{2,3,...,n}}q_{{1,3,...,n}|{2}} − q_{∅|[n]}q_{{1,2}|{3,...,n}}, we have (A′_{1}, A′_{k}) ≠ (∅, {3, …, n}).

Contrarily, suppose that m_{1} and m_{2} satisfy A_{1} ⊊ A_{2} ⊊ ⋯ ⊊ A_{k}, A′_{1} ⊊ A′_{2} ⊊ ⋯ ⊊ A′_{k} and (A′_{1}, A′_{k}) ≠ (∅, {3, …, n}). Then m_{1} and m_{2} are not divisible by the initial monomials q_{A|B}q_{C|D} (1, 2 ∈ A ∩ C, A ⊄ C, C ⊄ A) and q_{A|B}q_{C|D} (1 ∈ A ∩ C, 2 ∈ B ∩ D, A ⊄ C, C ⊄ A). Hence, m_{1} is standard. Suppose that m_{2} is not standard. Then m_{2} is divisible by the initial monomial q_{{1}∪A|{2}∪B}q_{{1}∪B|{2}∪A}. Since A′_{1} ⊊ A′_{2} ⊊ ⋯ ⊊ A′_{k}. Thus, we may assume that A ⊊ B. Since {1} ∪ A|{2} ∪ B is a partition, A ∪ B = {3, …, n}. Therefore, (A, B) = (∅, {3, …, n}). This contradicts the hypothesis (A′_{1}, A′_{k}) ≠ (∅, {3, …, n}). Hence, m_{2} is standard.

The Stirling number of the second kind \left\{{a \atop b}\right\} represents the number of ways to partition a set of a objects into b nonempty subsets. We obtain Table 2 by considering four cases for the number of squarefree standard monomials of type (1). There is a restriction that

A_{1} = ∅  A_{1} ≠ ∅
A_{k} = \{3, …, n\} (k − 1)!\left\{{n − 2 \atop k − 1}\right\}  k!\left\{{n − 2 \atop k}\right\}
A_{k} ≠ \{3, …, n\}  k!\left\{{n − 2 \atop k}\right\}  (k + 1)!\left\{{n − 2 \atop k + 1}\right\}

Table 1: Number of squarefree standard monomials

(A′_{1}, A′_{k}) ≠ (∅, {3, …, n}) for type (2). Therefore, we obtain the desired number of squarefree standard monomials in each condition.

3 h^{∗}-polynomial of the cut polytope of K_{2,n−2}

Let Δ be a triangulation of a lattice polytope P. The f-polynomial f_{Δ}(x) = ∑_{i=0}^{d+1} f_{i−1}x^{i} of Δ encodes the number f_{i} of i-faces for i = 0, 1 …, d and f_{−1} = 1. The h-polynomial h_{Δ}(x) = ∑_{i=0}^{d+1} h_{i}x^{i} is given by the following relation [2, P.185]:

h_{Δ}(x) = ∑_{i=0}^{d+1} f_{i−1}x^{i}(1 − x)^{d+1−i}.

The following is known for h^{∗}-polynomials and h-polynomials [2, Theorem 10.3].

Proposition 7. If P is a d-dimensional lattice polytope that admits a unimodular triangulation Δ, then h^{∗}(P, x) = h_{Δ}(x).

We have the following theorem for the h^{∗}-polynomial of the cut polytope of K_{2,n−2}.

Theorem 8. Let P = Cut(K_{2,n−2}) be the cut polytope of K_{2,n−2}, and let Δ be the unimodular triangulation Δ(in_{<}(I_{A_{P}})) of P with respect to the monomial order < in Proposition 4. Then the h^{∗}-polynomial of P and the h-polynomial of Δ are

h^{∗}(P, x) = h_{Δ}(x) = (x + 1)(A_{n−2}(x))^{2},

where A_{n}(x) is the Eulerian polynomial of degree n−1. In particular, the normalized volume of P is h^{∗}(P, 1) = 2((n − 2)!)^{2}.

Proof. The Eulerian polynomial A_{n}(x) satisfies the following condition [15, Theorem 9.1]:

A_{n}(x) = ∑_{k=1}^{n} k!\left\{{n \atop k}\right\}(x − 1)^{n−k}.

In addition, \left\{{n \atop k}\right\} is given by the following equation [20]:

\left\{{n \atop k}\right\} = ∑_{m=1}^{k}(−1)^{k−m}m^{n}\binom{k}{m}.

The f-polynomial of Δ is given by the following equation:

f_{Δ}(x) = ∑_{k=0}^{2n−3} f_{k−1}x^{k}.

Then f_{k−1} is equal to the number of squarefree standard monomials of degree k. Recall that a squarefree monomial

q_{A_{1}|{1,2}∪B_{1}} … q_{A_{α}|{1,2}∪B_{α}} q_{{1}∪A′_{α+1}|{2}∪B′_{α+1}} … q_{{1}∪A′_{k}|{2}∪B′_{k}} ∈ K[q]

is standard if and only if q_{A_{1}|{1,2}∪B_{1}} … q_{A_{α}|{1,2}∪B_{α}} and q_{{1}∪A′_{α+1}|{2}∪B′_{α+1}} … q_{{1}∪A′_{k}|{2}∪B′_{k}} are standard. From Proposition 6, we have f_{k−1} = ∑_{α=0}^{k} B_{α}C_{k−α}, where

B_{k} = (k − 1)!\left\{{n − 2 \atop k − 1}\right\} + 2k!\left\{{n − 2 \atop k}\right\} + (k + 1)!\left\{{n − 2 \atop k + 1}\right\},
C_{k} = 2k!\left\{{n − 2 \atop k}\right\} + (k + 1)!\left\{{n − 2 \atop k + 1}\right\}.

Since B_{k} = 0 for any k ≥ n, and C_{k} = 0 for any k ≥ n − 1,

f_{Δ}(x) = ∑_{k=0}^{2n−3} ∑_{α=0}^{k} B_{α}C_{k−α}x^{k} = (∑_{k=0}^{n−1} B_{k}x^{k}) (∑_{k=0}^{n−2} C_{k}x^{k}) .

Let X = x − 1. From [14, Remark 2.4, Theorem 3.4], h_{Δ}(x) is a palindromic polynomial of degree 2n − 5. Hence,

h_{Δ}(x) = x^{2n−5}h_{Δ}(x^{−1}) = x^{2n−5} ∑_{k=0}^{2n−3} f_{k−1}x^{−k}(1 − x^{−1})^{2n−3−k} = x^{−2} ∑_{k=0}^{2n−3} f_{k−1}X^{2n−3−k} (1)
= x^{−2} (∑_{k=0}^{n−1} B_{k}X^{n−k−1}) (∑_{k=0}^{n−2} C_{k}X^{n−k−2}) .  (2)

It then follows that

∑_{k=0}^{n−1} B_{k}X^{n−k−1} = ∑_{k=1}^{n} B_{k−1}X^{(n−1)−(k−1)}

= ∑_{k=3}^{n}(k − 2)!\left\{{n − 2 \atop k − 2}\right\}X^{(n−2)−(k−2)}

+ 2X ∑_{k=2}^{n−1}(k − 1)!\left\{{n − 2 \atop k − 1}\right\}X^{(n−2)−(k−1)} + X^{2} ∑_{k=1}^{n−2} k!\left\{{n − 2 \atop k}\right\}X^{(n−2)−k}

= ∑_{k′=1}^{n−2} k′!\left\{{n − 2 \atop k′}\right\}X^{(n−2)−k′}

+ 2X ∑_{k′′=1}^{n−2} k′′!\left\{{n − 2 \atop k′′}\right\}X^{(n−2)−k′′} + X^{2} ∑_{k=1}^{n−2} k!\left\{{n − 2 \atop k}\right\}X^{(n−2)−k}

= A_{n−2}(x) + 2XA_{n−2}(x) + X^{2}A_{n−2}(x)
= x^{2}A_{n−2}(x),

and

∑_{k=0}^{n−2} C_{k}X^{n−k−2} = ∑_{k=0}^{n−2} (2k!\left\{{n − 2 \atop k}\right\}X^{n−k−2} + (k + 1)!\left\{{n − 2 \atop k + 1}\right\}X^{n−k−2})

= 2 ∑_{k=1}^{n−2} k!\left\{{n − 2 \atop k}\right\}X^{(n−2)−k} + X ∑_{k=0}^{n−3}(k + 1)!\left\{{n − 2 \atop k + 1}\right\}X^{(n−3)−k}

= 2A_{n−2}(x) + X ∑_{k′=1}^{n−2} k′!\left\{{n − 2 \atop k′}\right\}X^{(n−2)−k′}

= 2A_{n−2}(x) + XA_{n−2}(x)

= (1 + x)A_{n−2}(x).

Therefore, h^{∗}(P, x) = h_{Δ}(x) = (x + 1)(A_{n−2}(x))^{2}.

4 Acknowledgment

The author is grateful to the anonymous referees for their careful reading and useful comments.

References

[1] C. A. Athasianadis, h^{∗}-vectors, Eulerian polynomials and stable polytopes of graphs, Electron. J. Combin. 11 (2) (2004), #R6.

[2] M. Beck and S. Robins, Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra, 2nd edition, Springer, 2015.

[3] W. Bruns and J. Gubeladze, Polytopes, Rings, and K-Theory, Springer, 2009.

[4] E. Ehrhart, Polynômes Arithmétiques et Méthode des Polyédres en Combinatoire, Birkhäuser, 1977.

[5] A. Engström, Cut ideals of K_{4}-minor free graphs are generated by quadrics, Michigan Math. J. 60 (2011), 705–714.

[6] L. Goddyn, T. Huynh, and T. Deshpande, On Hilbert bases of cuts, Discrete Math. 339 (2016), 721–728.

[7] J. Herzog, T. Hibi, and H. Ohsugi, Binomial Ideals, Springer, 2018.

[8] T. Hibi, A lower bound theorem for Ehrhart polynomials of convex polytopes, Adv. Math. 105 (1994), 162–165.

[9] J. Hofscheier, L. Katthän, and B. Nill, Spanning lattice polytopes and the uniform position principle, preprint, 2017. Available at https://arxiv.org/abs/1711.09512.

[10] J. Hofscheier, L. Katthän, and B. Nill, Ehrhart theory of spanning lattice polytopes, Int. Math. Res. Not. 19 (2018), 5947–5973.

[11] D. Král’, S. Norine, and O. Pangrác, Markov bases of binary graph models of K_{4}-minor free graphs, J. Combinatorial Theory, Series A 117 (2010), 759–765.

[12] U. Nagel and S. Petrović, Properties of cut ideals associated to ring graphs, J. Commut. Algebra 1 (2009), 547–565.

[13] H. Ohsugi, Normality of cut polytopes of graphs is a minor closed property, Discrete Math. 310 (2010), 1160–1166.

[14] H. Ohsugi, Gorenstein cut polytopes, European J. Combin. 38 (2014), 122–129.

[15] T. K. Petersen, Eulerian Numbers, Birkhäuster/Springer, 2015.

[16] R. Sakamoto, Lexicographic and reverse lexicographic quadratic Gröbner bases of cut ideals, J. Symbolic Comput., to appear.

[17] K. Shibata, Strong Koszulness of the toric ring associated to a cut ideal, Comment. Math. Univ. St. Pauli 64 (2015), 71–80.

[18] R. P. Stanley, Decomposition of rational convex polytopes, Ann. Discrete Math. 6 (1980), 333–342.

[19] R. P. Stanley, Two poset polytopes, Discrete Comput. Geom. 1 (1986), 9–23.

[20] R. P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd edition, Cambridge University Press, 2012.

[21] B. Sturmfels, Gröbner Bases and Convex Polytopes, American Mathematical Society, 1996.

[22] B. Sturmfels and S. Sullivant, Toric geometry of cuts and splits, Michigan Math. J. 57 (2008), 689–709.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 13P10, 52B20. Keywords: cut polytope, complete bipartite graph, h^{∗}-polynomial, Gröbner basis.

Received June 12 2019; revised versions received July 5 2019; September 26 2019; September 28 2019; April 9 2020. Published in Journal of Integer Sequences, June 27 2020.

Return to Journal of Integer Sequences home page.