Facets of Symmetric Edge Polytopes for Graphs with Few Edges

Benjamin Braun and Kaitlin Bruegge Department of Mathematics University of Kentucky Lexington, KY 40506-0027 USA

                          benjamin.braun@uky.edu
                          kaitlin bruegge@uky.edu

Abstract

Symmetric edge polytopes, also called adjacency polytopes, are lattice polytopes determined by simple undirected graphs. We introduce the integer array giving the maximum number of facets of a symmetric edge polytope for a connected graph having a fixed number of vertices and edges and the corresponding array of minimal values. We establish formulas for the number of facets obtained in several classes of sparse graphs, and provide partial progress toward conjectures that identify facet-maximizing graphs in these classes. These formulas are combinatorial in nature, and lead to independently interesting observations and conjectures regarding integer sequences defined by sums of products of binomial coefficients.

1 Introduction

Given a finite graph G, there are many ways to construct a lattice polytope using G as input: graphical zonotopes, edge polytopes, matching polytopes, stable set polytopes, Laplacian simplices, flow polytopes, and others. Of recent interest is the symmetric edge polytope P_{G}, introduced by Matsui, Higashitani, Nagazawa, Ohsugi, and Hibi [12]. These are known as adjacency polytopes in some applied settings [2]. Symmetric edge polytopes are of interest in several areas, including the study of Ehrhart theory and applications to algebraic Kuramoto equations. These polytopes have been the subject of intense recent study [1, 2, 3, 4, 5, 10, 11, 12, 15, 17].

n  m − n + 1 0 1 2 3 4 5 6 7 8 9 10 11 12
2  2
3  4 6
4  8 12 12 14
5  16 30 36 28 28 28 30
6  32 60 72 72 84 68 68 60 60 60 62
7  64 140 180 216 168 168 196 180 148 148 132 132 124

Table 1: maxf(n, m).

In this paper, we study the number of facets of P_{G} for connected graphs, with an emphasis on those graphs having few edges. Our study is motivated by the following question: for a fixed number of vertices and edges, what properties of connected graphs lead to symmetric edge polytopes with either a large or small number of facets? This leads us to the following definition.

Definition 1. For n ≥ 2 and m ≥ n − 1, define maxf(n, m) to be the maximum number of facets of a symmetric edge polytope for a connected graph having n vertices and m edges, and similarly define minf(n, m) to be the minimum number of facets. For n ≥ 2, we define Maxf(n) to be the maximum number of facets of a symmetric edge polytope for a connected graph having n vertices, and similarly define Minf(n) to be the minimum number.

The first few values of maxf(n, m) \underline{A360408} are given in Table 1. The first few values of minf(n, m) \underline{A360409} are given in Table 2. The sequence Maxf(n) is given by

2, 6, 14, 36, 84, 216, 504, 1296, …

while the sequence Minf(n) is given by

2, 4, 6, 10, 14, 22, 30, 46, …

Note that the conjectured sequence \underline{A027383} for Minf(n) has been previously studied. The problem of determining maxf(n, m) and minf(n, m) is challenging, in part due to the complicated combinatorial structures that describe the facets of P_{G}. Our experimental data suggest that facet-maximizing graphs can be obtained as wedges of odd cycles; how broadly this holds for general n and m beyond relatively sparse graphs is not clear. Based on computational evidence obtained with SageMath [19], we offer the following conjecture regarding terms of the sequences Maxf(n) and Minf(n) in general (all undefined terms below are defined in subsequent sections).

Conjecture 2. Let n ≥ 3.

1. For n = 2k + 1, we have Maxf(n) = 6^{k}, which is attained by a wedge of k cycles of length three.

n  m − n + 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13
2  2
3  4 6
4  8 6 12 14
5  16 12 10 22 26 28 30
6  32 20 18 16 14 42 54 56 58 60 62
7  64 40 32 28 26 24 22 78 102 106 116 118 120 122

Table 2: minf(n, m).

2. For n = 2k, we have Maxf(n) = 14 · 6^{k−2}, which is attained by a wedge of K_{4} with k − 2 cycles of length three.

3. For n = 2k + 1, we have Minf(n) = 3 · 2^{k} − 2, which is attained by K_{k,k+1}.

4. For n = 2k, we have Minf(n) = 2^{k+1} − 2, which is attained by K_{k,k}.

The fact that the conjectured max and min values in Cases 1 and 2 of Conjecture 2 are attained by a wedge follows from Proposition 9 below, while the analogous values for bipartite graphs in Cases 3 and 4 were established by Higashitani, Jochemko, and Michałek [10].

It is known that the symmetric edge polytope for every tree on n vertices is combinatorially a cross polytope and thus has 2^{n−1} facets, hence maxf(n, n − 1) = 2^{n−1}. More generally, the number of facets for symmetric edge polytopes can be derived using combinatorial tools. Specifically, a combinatorial description of the facet-defining hyperplanes of P_{G} was given by Higashitani, Jochemko, and Michałek [10]. Further, Chen, Davis, and Korchevskaia [1] give a combinatorial description of the faces of P_{G} that utilizes special subgraphs of G.

It follows from Definition 3 below that symmetric edge polytopes are centrally symmetric lattice polytopes. Symmetric edges polytopes have also been shown to be reflexive and terminal [9]. Further, Higashitani [9, Theorem 3.3] proved that centrally symmetric simplicial reflexive polytopes are precisely the symmetric edge polytopes of graphs without even cycles. In Case 1 of Conjecture 2, the symmetric edge polytopes arising from wedges of cycles of length three fall within this family. This is related to a result due to Nill [13, Corollary 4.4] stating that the maximum number of facets for every pseudo-symmetric reflexive simplicial d-polytope P is 6^{d/2} and that the maximum is attained if and only if P is a free sum of d/2 copies of P_{K_{3}}. Thus, Conjecture 2 aligns with existing results regarding these polytopes.

In this work, we investigate the sequences maxf(n, n) and maxf(n, n + 1). We provide an exact result for maxf(n, n) and provide partial progress toward a conjectured value of maxf(n, n + 1). The use of combinatorial tools for this analysis produces independently interesting integer sequences defined by sums of products of binomial coefficients.

This paper is structured as follows. In Section 2, we provide necessary definitions and background. In Section 3, we give formulas for the number of facets and discuss facetmaximizers among some sparse connected graphs, namely graphs on n vertices with n or n+1 edges where every pair of cycles present is edge-disjoint. In these cases, Theorems 11 and 14 respectively describe facet-maximizing graphs. In Section 4, we discuss facet counts for graphs constructed from internally disjoint paths connected at their endpoints and give formulas in Propositions 22 and 24. As a special case of this, we get results about the number of facets arising from graphs with n vertices and n + 1 edges where the cycles share at least one edge, and we make progress toward generalizing Theorem 14 to this class of graphs. In Section 5, we give several conjectures regarding facet-maximizing graphs in certain families. We also discuss computational evidence supporting these conjectures.

2 Background

Definition 3. Let G be a graph on the vertex set [n] = {1, …, n} and edge set E = E(G). Let e_{i} denote the i-th standard basis vector in ℝ^{n} and let conv{X} denote the convex hull of a subset X ⊂ ℝ^{n}. The symmetric edge polytope for G is

P_{G} := conv{±(e_{i} − e_{j}) : {i, j} ∈ E(G)} .

We denote by N(P) the number of facets of a polytope P. We denote by both N(P_{G}) and N(G) the number of facets of P_{G}.

Example 4. Let G be the path with vertices {1, 2, 3} and edges {12, 23}. Then

P_{G} = conv{±(e_{1} − e_{2}), ±(e_{2} − e_{3})} ⊂ ℝ^{3}

is a 4-gon contained in the orthogonal complement of the vector ⟨1, 1, 1⟩. This polygon has four 1-dimensional faces. Thus, we have N(P_{G}) = 4.

In general, the machinery used to count the facets of P_{G} are functions f : V → ℤ on the set V of vertices in G satisfying certain properties. It is known [10, Theorem 3.1] that the facets of P_{G} are in bijection with these functions.

Theorem 5 (Higashitani, Jochemko, Michałek [10]). Let G = (V, E) be a finite simple connected graph. Then f : V → ℤ is facet-defining if and only if both of the following hold.

(i) For every edge e = uv we have |f(u) − f(v)| ≤ 1.

(ii) The subset of edges E_{f} = {e = uv ∈ E : |f(u)−f(v)| = 1} forms a spanning connected subgraph of G.

As symmetric edge polytopes are contained in the hyperplane orthogonal to the span of the vector where every entry is one, two facet-defining functions are identified if they differ by a common constant. The spanning connected subgraphs with edge sets E_{f} arising in Theorem 5, called facet subgraphs, have further structure.

Lemma 6 (Chen, Davis, Korchevskaia [1]). Let G be a connected graph. A subgraph H of G is a facet subgraph of G if and only if it is a maximal connected spanning bipartite subgraph of G.

Lemma 6 provides a strategy for identifying the facets of P_{G} combinatorially: first identify the maximal connected spanning bipartite subgraphs of G, then determine the valid integer labelings of the vertices. Facet counts for symmetric edge polytopes are known for certain classes of graphs. A class of particular interest to us is cycles. Let C_{n} denote the cycle with n edges and let Q_{n} denote the path with n edges.

Lemma 7. For every m,

N(P_{C_{m}}) = \begin{cases}\binom{m}{m/2}, & if m is even; \\ m\binom{m−1}{(m−1)/2}, & if m is odd. \end{cases}

Proof. For even m, the facets of P_{C_{m}} are identified and counted in [2, Proposition 12], and for odd m in [13, Remark 4.3].

Though the two-cycle is a multigraph (and thus its symmetric edge polytope is not defined), its facet-defining functions would be exactly the facet-defining functions of a graph on two vertices with a single edge. This is consistent with the formula in Lemma 7.

For a graph G that is constructed by identifying two graphs at a single vertex, there is a relationship between the facets of P_{G} and the facets of the subgraphs.

Definition 8. For graphs G and H, let G ∨ H denote a graph obtained by identifying a vertex in G with a vertex in H. We call G ∨ H a wedge or join.

Note that we do not specify a choice of identification points when defining G ∨ H, as by the following proposition every such choice yields a symmetric edge polytope with the same number of facets.

Proposition 9. For connected graphs G and H,

N(P_{G∨H}) = N(P_{G}) · N(P_{H}).

Proof. This follows from the fact that P_{G∨H} is the free sum P_{G} ⊕ P_{H} [16, Proposition 4.2] (also called the direct sum) and the number of facets is multiplicative for free sums [8].

3 Graphs with few edges and disjoint cycles

We consider the symmetric edge polytopes for classes of connected graphs where the number of edges is small relative to the number of vertices. For every tree T on n vertices, we obtain N(T) = 2^{n−1} using Proposition 9 since T can be constructed as a wedge of n−1 single edges

Figure 1: C(7, 5).

with an appropriate choice of identification points. Thus, it follows that maxf(n, n − 1) = 2^{n−1}.

Considering next the sequence maxf(n, n), every connected graph with an equal number of vertices and edges has a unique cycle and hence can be constructed as a wedge of that cycle with trees. Therefore, we can count the facets of P_{G} for every such graph G and determine the maximum possible facet number arising from a graph with n vertices and n edges.

Definition 10. Let C(n, m) denote a graph on n vertices obtained by joining an m-cycle with a path graph on n − m edges.

Theorem 11. For every connected graph H with n vertices and n edges, the number of facets of P_{H} is less than or equal to the number of facets of P_{G} for G = C(n, n) when n is odd and G = C(n, n − 1) when n is even. Thus, for odd n we have

maxf(n, n) = n\binom{n − 1}{(n − 1)/2}

and for even n we have

maxf(n, n) = 2(n − 1)\binom{n − 2}{(n − 2)/2} .

Proof. A connected graph on n vertices and n edges has a unique cycle of length m for some 3 ≤ m ≤ n. Thus, the graph G is the join of an m-cycle and n − m edges. By Proposition 9, we have N(G) = N(C(n, m)). For k ≥ 2, we claim

N(C(n, 2k)) < N(C(n, 2k − 1)) < N(C(n, 2k + 1)) .  (1)

In other words, if m is even, then N(C(n, m − 1)) is greater than N(C(n, m)). Also, if m is odd and m ≤ n − 2, the graph C(n, m + 2) exists, and N(C(n, m + 2)) is greater than N(C(n, m)). With these two statements, we see that N(G) is maximized when G contains the largest odd cycle possible in a graph with n vertices.

To prove the inequality in (1), let

M = \frac{2^{n−(2k+1)}(2k − 1)!}{(k!)^{2}}.

Figure 2: A graph with N(G) = M(7).

Then, by Lemma 7 and Proposition 9,

N(C(n, 2k)) = N(C_{2k}) · 2^{n−2k} = \binom{2k}{k} · 2^{n−2k} = 4kM,

N(C(n, 2k − 1)) = N(C_{2k−1}) · 2^{n−(2k−1)} = (2k − 1)\binom{2k − 2}{k − 1} · 2^{n−(2k−1)} = 4k^{2}M,

N(C(n, 2k + 1)) = N(C_{2k+1}) · 2^{n−(2k+1)} = (2k + 1)\binom{2k}{k} · 2^{n−(2k+1)} = (4k^{2} + 2k)M,

and the claim holds.

We next consider the sequence maxf(n, n + 1), which is substantially more challenging than the previous cases. Every connected, simple graph with n vertices and n + 1 edges can be constructed from a tree on n vertices by adding two edges. Each of these additions induces a cycle in the graph. For such graphs, we make the following definition and conjecture.

Definition 12. For n ≥ 3, let M(n) be the number of facets of P_{G} where

G := \begin{cases}C_{k+1} ∨ C_{k−1}, & if n = 2k − 1 and k even; \\ C_{k} ∨ C_{k}, & if n = 2k − 1 and k odd; \\ C_{k+1} ∨ C_{k−1} ∨ e, & if n = 2k and k even; \\ C_{k} ∨ C_{k} ∨ e, & if n = 2k and k odd. \end{cases}

Conjecture 13. For all n ≥ 3, we have maxf(n, n + 1) = M(n).

Graphs with n vertices and n + 1 edges fall into two categories: graphs with exactly 2 edge-disjoint cycles, such as those defined in Definition 15 below, and graphs where the cycles share one or more edges, such as those defined in Definition 20 below. In this section, we show that Conjecture 13 is true for the first category.

Theorem 14. For every connected graph H with n vertices and n+1 edges where H contains two edge-disjoint cycles, we have N(H) ≤ M(n).

Note that Theorem 14 states that, among connected graphs with n vertices and n + 1 edges containing disjoint cycles, a facet-maximizing family arises by creating a graph that as closely as possible resembles the wedge of two equal-length odd cycles. The proof relies on the following definition and lemmas.

Definition 15. Let G(n, i, j) denote the graph C_{i} ∨ C_{j} ∨ Q_{n+1−(i+j)}. Note that G(n, i, j) has n vertices and n + 1 edges.

Lemma 16. If i is even, then

N(G(n, i, j)) < N(G(n, i − 1, j)).

Proof. Note that N(G(n, i, j)) = N(C(n + 1 − j, i) ∨ C_{j}). Because i is even, applying (1) and Proposition 9 yields

N(C(n + 1 − j, i) ∨ C_{j}) < N(C(n + 1 − j, i − 1) ∨ C_{j}) = N(G(n, i − 1, j)) ,

which completes the proof.

Lemma 17. For i, j, m, ℓ odd with m < i ≤ j < l and i + j = m + ℓ, we have

N(C_{m} ∨ C_{ℓ}) < N(C_{i} ∨ C_{j}).

Proof. We show this holds for m = i − 2 and ℓ = j + 2, then the argument follows by induction. Using Lemma 7 and Proposition 9, we obtain

N(C_{i} ∨ C_{j}) = ij\binom{i − 1}{\frac{i−1}{2}}\binom{j − 1}{\frac{j−1}{2}}

and

N(C_{i−2} ∨ C_{j+2}) = (i − 2)(j + 2)\binom{i − 3}{\frac{i−3}{2}}\binom{j + 1}{\frac{j+1}{2}}.

Letting M = (i − 2)j\binom{i − 3}{\frac{i−3}{2}}\binom{j − 1}{\frac{j−1}{2}}, we obtain

N(C_{i−2} ∨ C_{j+2}) = 4M · \frac{j + 2}{j + 1} < 4M · \frac{i}{i − 1} = N(C_{i} ∨ C_{j}).

We also make use of the following theorem.

Theorem 18. For all n, we have 2M(n) ≤ M(n + 1).

Proof. Lemma 7 and Proposition 9 imply that

M(n) = \begin{cases}(k + 1)(k − 1)\binom{k}{\frac{k}{2}}\binom{k−2}{\frac{k−2}{2}}, & if n = 2k − 1 and k even; \\ k^{2}\binom{k−1}{\frac{k−1}{2}}^{2}, & if n = 2k − 1 and k odd; \\ 2 · M(n − 1), & if n = 2k. \end{cases}

When n is odd, we have 2 · M(n) = M(n + 1) and we are done. When n is even, we consider two cases. Case 1: If n = 2k with k even, then n + 1 = 2(k + 1) − 1 with k + 1 odd. Therefore, letting

K = (k + 1)\binom{k}{\frac{k}{2}}, we have

M(n) = 2 · M(2k − 1) = 2(k + 1)(k − 1)\binom{k}{\frac{k}{2}}\binom{k − 2}{\frac{k−2}{2}} = 2(k − 1)\binom{k − 2}{\frac{k−2}{2}} · K

and

M(n + 1) = (k + 1)^{2}\binom{k}{\frac{k}{2}}^{2} = K^{2} .

Since

\begin{aligned}K & = (k + 1)\binom{k}{\frac{k}{2}} = \frac{(k + 1)k}{(\frac{k}{2})2} · (k − 1) · \binom{k − 2}{\frac{k−2}{2}} \\ & = \frac{4(k + 1)}{k} · (k − 1) · \binom{k − 2}{\frac{k−2}{2}} ≥ 4 · (k − 1) · \binom{k − 2}{\frac{k−2}{2}} , \end{aligned}

we see

2 · M(n) = 4(k − 1)\binom{k − 2}{\frac{k−2}{2}} · K ≤ K^{2} = M(n + 1) .

Case 2: If n = 2k with k odd, then n + 1 = 2(k + 1) − 1 with k + 1 even. Therefore, letting K = k\binom{k−1}{\frac{k−1}{2}}, we have

M(n) = 2 · M(2k − 1) = 2k^{2}\binom{k − 1}{\frac{k−1}{2}}^{2} = 2K^{2}

and

M(n + 1) = (k + 2)k\binom{k + 1}{\frac{k+1}{2}}\binom{k − 1}{\frac{k−1}{2}} = (k + 2)\binom{k + 1}{\frac{k+1}{2}} · K .

Since

(k + 2)\binom{k + 1}{\frac{k+1}{2}} = \frac{(k + 2)(k + 1)}{(\frac{k+1}{2})2} · k · \binom{k − 1}{\frac{k−1}{2}} = \frac{4(k + 2)}{(k + 1)} · K ≥ 4K ,

we see

2 · M(n) = 4K^{2} ≤ (k + 2)\binom{k + 1}{\frac{k+1}{2}} · K = M(n + 1) .

With these in place, we can prove Theorem 14.

Proof of Theorem 14. By Proposition 9, every such graph H containing exactly two edgedisjoint cycles of length i and j satisfies N(H) = N(G(n, i, j)). Thus, it is sufficient to restrict our attention to G(n, i, j). By Lemmas 16 and 17, we can consider only G(n, i, j) for i, j odd and as close to \frac{i+j}{2} as possible. Without loss of generality, suppose i ≤ j. Case 1: n = 2k − 1 and k even. Note that, since i and j are both odd, we have i ≤ k − 1 and j ≤ k + 1. Also, using Lemma 7 and Proposition 9, we obtain

N(G(n, i, j)) = 2^{n−(i+j)+1}ij\binom{i − 1}{\frac{i−1}{2}}\binom{j − 1}{\frac{j−1}{2}} = 2^{2k−(i+j)} · \frac{i!j!}{(\frac{i−1}{2}!)^{2} (\frac{j−1}{2}!)^{2}} .

Similarly,

M(n) = (k + 1)(k − 1)\binom{k}{\frac{k}{2}}\binom{k − 2}{\frac{k−2}{2}}

= \frac{(k + 1)!}{(\frac{k}{2}!)^{2}} · \frac{(k − 1)!}{(\frac{k−2}{2}!)^{2}}

= \frac{j!}{(\frac{j−1}{2}!)^{2}} · ( ∏_{\begin{matrix}ℓ=j+1 \\ ℓ even \end{matrix}}^{k} \frac{(ℓ + 1)ℓ}{(\frac{ℓ}{2})2} ) · \frac{i!}{(\frac{i−1}{2}!)^{2}} · ( ∏_{\begin{matrix}m=i+1 \\ m even \end{matrix}}^{k−2} \frac{(m + 1)m}{(\frac{m}{2})2} )

= 2^{2k−(i+j)} · \frac{i!j!}{(\frac{i−1}{2}!)^{2} (\frac{j−1}{2}!)^{2}} · ( ∏_{\begin{matrix}ℓ=j+1 \\ ℓ even \end{matrix}}^{k} \frac{ℓ + 1}{ℓ}) · ( ∏_{\begin{matrix}m=i+1 \\ m even \end{matrix}}^{k−2} \frac{m + 1}{m})

≥ N(G(n, i, j)).

Case 2: n = 2k − 1 and k odd. Note that, by assumption, we have i ≤ k and j ≤ k. Also, using Lemma 7 and Proposition 9, we obtain

N(G(n, i, j)) = 2^{n−(i+j)+1}ij\binom{i − 1}{\frac{i−1}{2}}\binom{j − 1}{\frac{j−1}{2}} = 2^{2k−(i+j)} · \frac{i!j!}{(\frac{i−1}{2}!)^{2} (\frac{j−1}{2}!)^{2}} .

Similarly,

M(n) = k^{2}\binom{k − 1}{\frac{k−1}{2}}^{2}

= \frac{j!}{(\frac{j−1}{2}!)^{2}} · ( ∏_{\begin{matrix}ℓ=j+1 \\ ℓ even \end{matrix}}^{k−1} \frac{(ℓ + 1)ℓ}{(\frac{ℓ}{2})2} ) · \frac{i!}{(\frac{i−1}{2}!)^{2}} · ( ∏_{\begin{matrix}m=i+1 \\ m even \end{matrix}}^{k−1} \frac{(m + 1)m}{(\frac{m}{2})2} )

= 2^{2k−(i+j)} · \frac{i!j!}{(\frac{i−1}{2}!)^{2} (\frac{j−1}{2}!)^{2}} ( ∏_{\begin{matrix}ℓ=j+1 \\ ℓ even \end{matrix}}^{k−1} \frac{ℓ + 1}{ℓ}) · ( ∏_{\begin{matrix}m=i+1 \\ m even \end{matrix}}^{k−1} \frac{m + 1}{m})

≥ N(G(n, i, j)).

Case 3: n = 2k. Using Lemma 7 and Proposition 9, we obtain

N(G(n, i, j)) = 2^{n−(i+j)+1}ij\binom{i − 1}{\frac{i−1}{2}}\binom{j − 1}{\frac{j−1}{2}} = 2 · N(G(n − 1, i, j)) .

Also, using Theorem 18 and the previous cases, we obtain

M(n) ≥ 2 · M(n − 1)
≥ 2 · N(G(n − 1, i, j))
= N(G(n, i, j)).

Thus, in every case, we have N(G(n, i, j)) ≤ M(n).

4 Graphs with few edges and overlapping cycles

We next consider the family of graphs on n vertices and n + 1 edges that have two cycles intersecting in at least one edge. Note that the case where two cycles intersect in exactly one edge was previously studied [1, Section 5]. Theorem 18 allows us to reduce Conjecture 13 to the case where G has no vertices of degree one, as follows.

Corollary 19. If Conjecture 13 is true for graphs on n vertices, then it is true for graphs on n + 1 vertices that have at least one leaf.

Proof. Let G be a graph on n + 1 vertices and n + 2 edges that has a leaf e. Then G \ {e} is a graph with n vertices and n + 1 edges, and by assumption N(G \ {e}) ≤ M(n). By Proposition 9 and Theorem 18, we get

N(G) = 2 · N(G \ {e}) ≤ 2 · M(n) ≤ M(n + 1).

Corollary 19 allows us to restrict our attention to graphs with no leaves. Every graph on n vertices and n + 1 edges with no leaves that contains cycles sharing one or more edges can be interpreted as three internally disjoint paths connected at their endpoints. We consider these as a special case of a more general construction.

Definition 20. For a vector m ∈ ℕ^{t}, let CB(m) denote the graph made of t internally disjoint paths of lengths m_{1}, m_{2}, …, m_{t} connecting two endpoints.

Note that when t = 3, we obtain the leafless connected graphs with n vertices and n + 1 edges.

Remark 21. The graphs CB(m) for which all entries of m are the same m ∈ ℕ are sometimes called theta graphs, denoted by θ_{m,t} [6].

Proposition 22. For m ∈ ℕ^{t}, we may permute the entries so that without loss of generality we have m_{1} ≥ m_{2} ≥ ⋯ ≥ m_{t}. If all the m_{i}’s have the same parity, then N(CB(m)) is given by

F (m) = ∑_{j=0}^{m_{t}} \binom{m_{t}}{j} [∏_{k=1}^{t−1} \binom{m_{k}}{\frac{1}{2}(m_{k} − m_{t}) + j}] .

Proof. Consider CB(m) as consisting of paths Q_{1}, Q_{2}, …, Q_{t} having m_{1} ≥ ⋯ ≥ m_{t} edges respectively, as shown in Figure 3. Since all m_{i} are the same parity, it follows that CB(m) is bipartite. For every facet-defining function f : V → ℤ, we have |f(u) − f(v)| = 1 for every edge uv in CB(m) [5, Lem. 4.5]. If we consider the paths as oriented away from the top vertex toward the bottom vertex, we can view each edge u → v as ascending (f(v) − f(u) = 1) and label it 1, or as descending (f(v) − f(u) = −1) and label it −1.

We count facets by finding valid labelings of the edges of CB(m) with ±1, that is labelings such that the sum of the labels on every path is the same. For a labeling of a shortest path with length m_{t} using j (−1)s and m_{t} − j 1s, the sum of the edge labels is m_{t} − 2j. There are \binom{m_{t}}{j} labelings of this path with this sum.

To produce a valid labeling of the entire graph with each path sum equal to m_{t} − 2j, the number of (−1)s, call this number y, on a path of length m_{k} must satisfy the following equation:

\begin{aligned}(+1)(m_{k} − y) + (−1)y & = m_{t} − 2j \\ y & = \frac{1}{2}(m_{k} − m_{t}) + j. \end{aligned}

Thus, there are \binom{m_{k}}{\frac{1}{2}(m_{k} − m_{t}) + j} labelings of a path of length m_{k} with label sum m_{t} − 2j.

Applying this argument to m_{k} for k = 1, …, t − 1 gives

\binom{m_{t}}{j} ∏_{k=1}^{t−1} \binom{m_{k}}{\frac{1}{2}(m_{k} − m_{t}) + j}

\begin{matrix}Q_{1} \\ Q_{2} \\ Q_{t} \\ ⋯ \end{matrix}

Figure 3: The graph CB(m) for m = (m_{1}, …, m_{t}).

valid labelings of CB(m) with j (−1)s on the shortest path. The result follows by taking the sum over all j = 0, …, m_{t}.

Note that there is a combinatorial interpretation for F, where we consider the arithmetical triangle of binomial coefficients vertically centered at the central terms. What F does is select the m_{t} row of the arithmetical triangle, multiply each entry by the vertically-aligned entries in rows m_{1} through m_{t−1}, and sum the resulting products.

For CB(m) = θ_{m,t} where all the paths are the same length, this formula simplifies.

Corollary 23. For t ∈ ℕ, we have

N(θ_{m,t}) = ∑_{j=0}^{m} \binom{m}{j}^{t}.

If the vector m has both even and odd entries, counting the facets of CB(m) becomes more complicated, but still involves F.

Proposition 24. For m ∈ ℕ^{t}, permute the entries so that m = (e_{1}, …, e_{k}, o_{1}, …, o_{ℓ}) with e_{1} ≥ e_{2} ≥ ⋯ ≥ e_{k} even and o_{1} ≥ o_{2} ≥ ⋯ ≥ o_{ℓ} odd and k, ℓ ≥ 1 with k + ℓ = t. Also, let m_{e} be the vector obtained by subtracting 1 from every even entry of m, and m_{o} the vector obtained by subtracting 1 from every odd entry of m.

(i) If all entries of m are at least 2, then

N(CB(m)) = (∏_{j=1}^{k} e_{j}) F (m_{e}) + (∏_{j=1}^{ℓ} o_{j}) F (m_{o}).

(ii) If o_{p+1} = ⋯ = o_{ℓ} = 1 (and o_{p} > 1), then

N(CB(m)) = (∏_{j=1}^{k} e_{j}) F (m_{e}) + (∏_{j=1}^{ℓ} o_{j}) N ((⋁_{j=1}^{k} C_{e_{j}}) ∨ (⋁_{j=1}^{p} C_{o_{j}−1})) .

Proof. Consider CB(m) as in Figure 3. As in the proof of Proposition 22, we will count facets of P_{CB(m)} by counting valid labelings of the facets subgraphs of CB(m). These subgraphs are those in which either one edge of every even length path has been removed or one edge of every odd length path has been removed. We can view these as labelings of CB(m) where the sum of labels on each Q_{i} is equal, and all edges must be labeled with ±1 except either

A. one edge on each even path is labeled 0, or

B. one edge on each odd path is labeled 0.

In Case A, there are ∏_{j=1}^{k} e_{j} ways to choose the edges to label 0. Having the edge uv labeled 0

indicates that f(u) = f(v) in the corresponding facet-defining function f : V → ℤ. Thus, we can view this edge as having been contracted since its endpoints have the same value. The reduced graph with these edges contracted is CB(m_{e}), constructed of paths that all have odd length. So, by Proposition 22, the number of valid labelings of CB(m) where each even path has a 0 edge is

(∏_{j=1}^{k} e_{j}) F (m_{e}).

In Case B, there are ∏_{j=1}^{ℓ} o_{j} ways to choose the edges to label 0. If every entry of m is at

least 2, the graph produced by contracting these 0 edges is CB(m_{o}), constructed of paths that all have even length. As above, the number of valid labelings of CB(m) of this type is

(∏_{j=1}^{ℓ} o_{j}) F (m_{o}).

Thus, in Case (i) of the Proposition statement, we have

N(CB(m)) = (∏_{j=1}^{k} e_{j}) F (m_{e}) + (∏_{j=1}^{ℓ} o_{j}) F (m_{o}).

To complete Case (ii) of the Proposition, note that if we contract an edge on a path of length 1, the endpoints of the remaining paths are identified, and the reduced graph is a wedge of cycles. In particular, if o_{p+1} = ⋯ = o_{ℓ} = 1 and o_{p} > 1, the reduced graph is

(⋁_{j=1}^{k} C_{e_{j}}) ∨ (⋁_{j=1}^{p} C_{o_{j}−1}). Thus, the number of valid labelings of CB(m) of this type is

N ((⋁_{j=1}^{k} C_{e_{j}}) ∨ (⋁_{j=1}^{p} C_{o_{j}−1})) .

Therefore, in Case (ii) of the Proposition, we have

N(CB(m)) = (∏_{j=1}^{k} e_{j}) F (m_{e}) + (∏_{j=1}^{ℓ} o_{j}) N ((⋁_{j=1}^{k} C_{e_{j}}) ∨ (⋁_{j=1}^{p} C_{o_{j}−1})) .

Returning to the special case of leafless connected graphs on n vertices with n + 1 edges, specializing to t = 3 provides facet counts for our graphs of interest.

Corollary 25. The number of facets of the symmetric edge polytope for CB(x_{1}, x_{2}, x_{3}) is computed as follows.

(i) For x_{1}, x_{2}, x_{3} either all even or all odd, we have

N(CB(x_{1}, x_{2}, x_{3})) = F (x_{1}, x_{2}, x_{3}) .

(ii) For o_{1}, o_{2} odd and e_{1} even, and all at least 2, we have

N(CB(o_{1}, o_{2}, e_{1})) = e_{1}F (o_{1}, o_{2}, e_{1} − 1) + o_{1}o_{2}F (o_{1} − 1, o_{2} − 1, e_{1}) .

For e_{1}, e_{2} even and o_{1} odd, and all at least 2, we have

N(CB(e_{1}, e_{2}, o_{1})) = o_{1}F (e_{1}, e_{2}, o_{1} − 1) + e_{1}e_{2}F (e_{1} − 1, e_{2} − 1, o_{1}) .

(iii) For e_{1}, e_{2} even and o_{1} = 1, we have

N(CB(e_{1}, e_{2}, 1)) = e_{1}e_{2}F (e_{1} − 1, e_{2} − 1, 1) + N(C_{e_{1}} ∨ C_{e_{2}}) .

(iv) For e_{1} even and o_{1} ≥ 3 odd, we have

N(CB(e_{1}, o_{1}, 1)) = e_{1}F (e_{1} − 1, o_{1}, 1) + o_{1}N(C_{o_{1}−1} ∨ C_{e_{1}}) .

(v) For e_{1} even, we have

N(CB(e_{1}, 1, 1)) = e_{1}F (e_{1} − 1, 1, 1) + N(C_{e_{1}}) .

0121231+ + + + + + + − 0121 2 11+ + + + + + − +

Figure 4: Some of the facet-defining functions of CB(4, 2, 2) when j = 0.

0101211+ + + − + − 0−1 01211+ + + − + 0101 0 −1 1− + + + − + − 0−1 010−1 1− + + + − +

Figure 5: Some of the facet-defining functions of CB(4, 2, 2) when j = 1.

\begin{matrix}0 \\ −1 \\ −2 \\ −1 \\ −2 \\ −3 \\ −1 \\ − \\ − \\ − \\ − \\ − \\ − \\ − \\ + \\ 0 \\ −1 \\ −2 \\ −1 \\ −2 \\ −1 \\ −1 \\ − \\ − \\ − \\ − \\ − \\ − \\ + \\ − \end{matrix}

Figure 6: Some of the facet-defining functions of CB(4, 2, 2) when j = 2.

Example 26. Figures 4, 5, and 6 illustrate some of the facet-defining functions for the symmetric edge polytope of CB(4, 2, 2). The vertices are labeled with their function values, and the edges are labeled “ + ” if they are ascending and “ − ” if they are descending.

Using these results, we can make partial progress toward Conjecture 13 in two special cases, given below in Theorem 27 and Proposition 30.

Theorem 27. For all n ≥ 4, if x_{1} ≥ x_{2} ≥ x_{3} ≥ 1, all x_{i}’s have the same parity, and x_{1} + x_{2} + x_{3} = n + 1, then

F (x_{1}, x_{2}, x_{3}) ≤ M(n).

Thus, if x_{1}, x_{2}, x_{3} are all of the same parity, then Conjecture 13 is true.

Remark 28. The proof of Theorem 27 makes use of the Stirling bounds on n! [18]:

\sqrt{2π} n^{n+ \frac{1}{2}} e^{−n}e^{\frac{1}{12n+1}} ≤ n! ≤ \sqrt{2π} n^{n+ \frac{1}{2}} e^{−n}e^{\frac{1}{12n}}

Proof of Theorem 27. In each of the following cases, we show that the desired inequality holds for large enough n. For all smaller values of n we have verified that the theorem holds

using SageMath [19]. Throughout the proof, we use the notation ≤^{!} to indicate an unproven inequality we wish to show. Case 1: Assume n = 2k − 1. In this case, we have x_{1} + x_{2} + x_{3} = 2k and all x_{i}’s are even by assumption. Thus, we have

\begin{aligned}F (x_{1}, x_{2}, x_{3}) & = ∑_{j=0}^{x_{3}} \binom{x_{3}}{j}\binom{x_{2}}{\frac{1}{2} (x_{2} − x_{3}) + j}\binom{x_{1}}{\frac{1}{2} (x_{1} − x_{3}) + j} \\ & ≤ (x_{3} + 1)\binom{x_{3}}{\frac{x_{3}}{2}}\binom{x_{2}}{\frac{x_{2}}{2}}\binom{x_{1}}{\frac{x_{1}}{2}}. \end{aligned}

Subcase 1(a): If k is even, then

M(n) = M(2k − 1) = (k + 1)(k − 1)\binom{k}{\frac{k}{2}}\binom{k − 2}{\frac{k−2}{2}}.

To show F (x_{1}, x_{2}, x_{3}) ≤ M(n), it suffices to show

(x_{3} + 1) x_{3}!x_{2}!x_{1}! (\frac{k}{2}!)^{2} (\frac{k − 2}{2}!)^{2} ≤^{!} (k + 1)(k − 1)k!(k − 2)! (\frac{x_{3}}{2} !)^{2} (\frac{x_{2}}{2} !)^{2} (\frac{x_{1}}{2} !)^{2} . (2)

By the Stirling bounds on n!, it suffices to show that

(\begin{matrix}(x_{3} + 1)x_{3}^{x_{3}+ \frac{1}{2}} x_{2}^{x_{2}+ \frac{1}{2}} x_{1}^{x_{1}+ \frac{1}{2}} \\ · (\frac{k}{2})^{k+1} (\frac{k−2}{2})^{k−1} \\ ·e^{−(x_{1}+x_{2}+x_{3}+2k)+2} \\ ·e^{\frac{1}{12x_{3}} + \frac{1}{12x_{2}} + \frac{1}{12x_{1}} + \frac{1}{3k} + \frac{1}{3(k−2)}} \end{matrix} ) ≤^{!} ( \begin{matrix}\sqrt{2π} & (\frac{x_{3}}{2} ) & x_{3}+1 & (\frac{x_{2}}{2} ) & x_{2}+1 & (\frac{x_{1}}{2} ) & x_{1}+1 \\ ·(k + 1)(k − 1)k^{k+ \frac{1}{2}} (k − 2)^{k− \frac{3}{2}} \\ ·e^{−(x_{1}+x_{2}+x_{3}+2k)+2} \\ ·e^{\frac{1}{12k+1} + \frac{1}{12k−23} + \frac{2}{6x_{3}+1} + \frac{2}{6x_{2}+1} + \frac{2}{6x_{1}+1}} \end{matrix})

or, equivalently, to show that

(\begin{matrix}(x_{3} + 1) \\ ·k^{k+1}(k − 2)^{k−1} \\ ·e^{\frac{1}{12x_{3}} + \frac{1}{12x_{2}} + \frac{1}{12x_{1}} + \frac{1}{3k} + \frac{1}{3(k−2)}} \end{matrix} ) ≤^{!} ( \begin{matrix}\frac{\sqrt{2π}}{8} & \sqrt{x_{1}x_{2}x_{3}} \\ ·(k + 1)(k − 1)k^{k+ \frac{1}{2}} (k − 2)^{k− \frac{3}{2}} \\ ·e^{\frac{1}{12k+1} + \frac{1}{12k−23} + \frac{2}{6x_{3}+1} + \frac{2}{6x_{2}+1} + \frac{2}{6x_{1}+1}} \end{matrix} ) .

Since \frac{1}{12k+1} + \frac{1}{12k−23} > 0 for k ≥ 2, we have

e^{\frac{1}{12k+1} + \frac{1}{12k−23}} > 1.

Also, since

−1 ≤ \frac{1}{12x} − \frac{2}{6x + 1} ≤ 0

for all x ≥ 1, we have

0 ≤ e^{\frac{1}{12x_{3}} − \frac{2}{6x_{3}+1} + \frac{1}{12x_{2}} − \frac{2}{6x_{2}+1} + \frac{1}{12x_{1}} − \frac{2}{6x_{1}+1}} ≤ 1

for all x_{1}, x_{2}, x_{3}. Therefore, to show inequality (2), it suffices to show

(x_{3} + 1)k^{k+1}(k − 2)^{k−1}e^{\frac{1}{3k} + \frac{1}{3(k−2)}} ≤^{!} \frac{\sqrt{2π}}{8} (k + 1)(k − 1)k^{k+ \frac{1}{2}} (k − 2)^{k− \frac{3}{2}} \sqrt{x_{1}x_{2}x_{3}}

or, rather, to show

(x_{3} + 1)\sqrt{k(k − 2)}e^{\frac{1}{3k} + \frac{1}{3(k−2)}} ≤^{!} \frac{\sqrt{2π}}{8} (k + 1)(k − 1)\sqrt{x_{1}x_{2}x_{3}}.

Finally, we note the following:

• By assumption, we have x_{3} + 1 ≤ \frac{2k}{3} + 1 ≤ k + 1, and thus \frac{x_{3} + 1}{k + 1} ≤ 1.

• We have \frac{\sqrt{k(k − 2)}}{k − 1} ≤ 1.

• We have 0 < e^{\frac{1}{3k} + \frac{1}{3(k−2)}} < e for k ≥ 3.

• By assumption, we have x_{1} ≥ \frac{2k}{3} , and x_{2}, x_{3} ≥ 2, implying that x_{1}x_{2}x_{3} ≥ \frac{8k}{3} . With this, it suffices to show that

e ≤^{!} \frac{\sqrt{2π}}{8} \sqrt{\frac{8k}{3}}

or, equivalently, that

k ≥^{!} \frac{12e^{2}}{π} ≈ 28.224.

This inequality and the desired inequality hold for all even k ≥ 30.

Subcase 1(b): If k is odd, then

M(n) = M(2k − 1) = k^{2}\binom{k − 1}{\frac{k−1}{2}}.

To show F (x_{1}, x_{2}, x_{3}) ≤ M(n), it suffices to show

(x_{3} + 1) x_{3}!x_{2}!x_{1}! (\frac{k − 1}{2}!)^{4} ≤^{!} (k!)^{2} (\frac{x_{3}}{2} !)^{2} (\frac{x_{2}}{2} !)^{2} (\frac{x_{1}}{2} !)^{2} .  (3)

By the Stirling bounds on n!, it suffices to show

(\begin{matrix}(x_{3} + 1)x_{3}^{x_{3}+ \frac{1}{2}} x_{2}^{x_{2}+ \frac{1}{2}} x_{1}^{x_{1}+ \frac{1}{2}} \\ · (\frac{k−1}{2})^{2k} \\ ·e^{−(x_{1}+x_{2}+x_{3}+2k)+2} \\ ·e^{\frac{1}{12x_{3}} + \frac{1}{12x_{2}} + \frac{1}{12x_{1}} + \frac{2}{3(k−1)}} \end{matrix} ) ≤^{!} ( \begin{matrix}\sqrt{2π} & (\frac{x_{3}}{2} ) & x_{3}+1 & (\frac{x_{2}}{2} ) & x_{2}+1 & (\frac{x_{1}}{2} ) & x_{1}+1 \\ ·k^{2k+1} \\ ·e^{−(x_{1}+x_{2}+x_{3}+2k)} \\ ·e^{\frac{2}{12k+1} + \frac{2}{6x_{3}+1} + \frac{2}{6x_{2}+1} + \frac{2}{6x_{1}+1}} \end{matrix}) .

Using the same kinds of computations as the previous case, we see it suffices to show

e^{2}(x_{3} + 1)(k − 1)^{2k}e^{\frac{2}{3(k−1)}} ≤^{!} \frac{\sqrt{2π}}{8} k^{2k+1}\sqrt{x_{1}x_{2}x_{3}}.

Now note the following:

• We have x_{3} + 1 ≤ \frac{2k}{3} + 1 ≤ k for k ≥ 3 and thus \frac{x_{3}+1}{k} ≤ 1.

• We have e^{2} (\frac{k − 1}{k})^{2k} ≤ 1 for k ≥ 3.

• We have 1 ≤ e^{\frac{2}{3(k−1)}} ≤ e for k ≥ 2.

So, it suffices to show that

e ≤^{!} \frac{\sqrt{2π}}{8} \sqrt{x_{1}x_{2}x_{3}},

which, as before, holds for

k ≥ \frac{12e^{2}}{π} ≈ 28.224

or all odd k ≥ 29. Case 2: Assume n = 2k. In this case, we have x_{1} + x_{2} + x_{3} = 2k + 1 and all x_{i}’s are odd by assumption. Thus, we have

\begin{aligned}F (x_{1}, x_{2}, x_{3}) & = ∑_{j=0}^{x_{3}} \binom{x_{3}}{j}\binom{x_{2}}{\frac{1}{2} (x_{2} − x_{3}) + j}\binom{x_{1}}{\frac{1}{2} (x_{1} − x_{3}) + j} \\ & ≤ (x_{3} + 1)\binom{x_{3}}{\frac{x_{3}−1}{2}}\binom{x_{2}}{\frac{x_{2}−1}{2}}\binom{x_{1}}{\frac{x_{1}−1}{2}}. \end{aligned}

Subcase 2(a): If k is even, then

M(n) = M(2k) = 2(k + 1)(k − 1)\binom{k}{\frac{k}{2}}\binom{k − 2}{\frac{k−2}{2}}.

To show F (x_{1}, x_{2}, x_{3}) ≤ M(n), it suffices to show

\begin{matrix}(x_{3} + 1) x_{3}!x_{2}!x_{1}! (\frac{k}{2}!)^{2} (\frac{k − 2}{2}!)^{2} \\ ≤^{!} 2(k + 1)(k − 1)k!(k − 2)! ∏_{k=1}^{3} [(\frac{x_{i} + 1}{2}!) (\frac{x_{i} − 1}{2}!)] . \end{matrix}  (4)

Equivalently, we want

\begin{matrix}(x_{3} + 1) x_{3}!x_{2}!x_{1}! (\frac{k}{2}!)^{2} (\frac{k − 2}{2}!)^{2} \\ ≤^{!} 2(k + 1)(k − 1)k!(k − 2)! ∏_{i=1}^{3} (\frac{x_{i} + 1}{2}!)^{2} (\frac{8}{(x_{3} + 1)(x_{2} + 1)(x_{1} + 1)}) , \end{matrix}

or, equivalently, we want

\begin{matrix}(x_{3} + 1) (x_{3} + 1)!(x_{2} + 1)!(x_{1} + 1)! (\frac{k}{2}!)^{2} (\frac{k − 2}{2}!)^{2} \\ ≤^{!} 16(k + 1)(k − 1)k!(k − 2)! (\frac{x_{3} + 1}{2}!)^{2} (\frac{x_{2} + 1}{2}!)^{2} (\frac{x_{1} + 1}{2}!)^{2} . \end{matrix}

By the Stirling bounds, it suffices to show

(\begin{matrix}(x_{3} + 1)(x_{3} + 1)^{x_{3}+ \frac{3}{2}} (x_{2} + 1)^{x_{2}+ \frac{3}{2}} (x_{1} + 1)^{x_{1}+ \frac{3}{2}} (\frac{k}{2})^{k+1} (\frac{k−2}{2})^{k−1} \\ · e^{−(x_{3}+x_{2}+x_{1}+2k+1)}e^{\frac{1}{12(x_{3}+1)} + \frac{1}{12(x_{2}+1)} + \frac{1}{12(x_{1}+1)} + \frac{1}{3k} + \frac{1}{3(k−2)}} \end{matrix} )

≤^{!} ( \begin{matrix}16\sqrt{2π} (\frac{x_{3}+1}{2})^{x_{3}+2} (\frac{x_{2}+1}{2})^{x_{2}+2} (\frac{x_{1}+1}{2})^{x_{1}+2} (k + 1)(k − 1)k^{k+ \frac{1}{2}} (k − 1)^{k− \frac{3}{2}} \\ · e^{−(x_{3}+x_{2}+x_{1}+2k+1)}e^{\frac{1}{12k+1} + \frac{1}{12(k−2)+1} + \frac{2}{6(x_{3}+1)+1} + \frac{2}{6(x_{2}+1)+1} + \frac{2}{6(x_{1}+1)+1}} \end{matrix} ) .

After computations similar to those in Case 1, we see it suffices to show

(x_{3} + 1)\sqrt{k(k − 2)}e ≤^{!} \frac{\sqrt{2π}}{8} (k + 1)(k − 1)\sqrt{(x_{1} + 1)(x_{2} + 1)(x_{3} + 1)}

where x_{1} + 1 ≥ \frac{2k+4}{3} and x_{2} + 1 ≥ 2 and x_{3} + 1 ≥ 2. It therefore suffices to show

e ≤^{!} \frac{\sqrt{2π}}{8} \sqrt{4 (\frac{2k + 4}{3})}

or, equivalently, to have

k ≥ \frac{12e^{2}}{π} − 2 ≈ 26.224.

Thus, the desired inequality holds for even k ≥ 28.

Subcase 2(b): If k is odd, then

M(n) = M(2k) = 2k^{2}\binom{k − 1}{\frac{k−1}{2}}^{2}.

To show F (x_{1}, x_{2}, x_{3}) ≤ M(n), it suffices to show

\begin{matrix}(x_{3} + 1)x_{3}!x_{2}!x_{1}! (\frac{k − 1}{2}!)^{4} \\ ≤^{!} 2(k!)^{2} (\frac{x_{3} − 1}{2}!) (\frac{x_{3} + 1}{2}!) (\frac{x_{2} − 1}{2}!) (\frac{x_{2} + 1}{2}!) (\frac{x_{1} − 1}{2}!) (\frac{x_{1} + 1}{2}!) . \end{matrix} (5)

Equivalently, we want

\begin{matrix}(x_{3} + 1) x_{3}!x_{2}!x_{1}! (\frac{k − 1}{2}!)^{4} \\ ≤^{!} 2(k!)^{2} (\frac{x_{3} + 1}{2}!)^{2} (\frac{x_{2} + 1}{2}!)^{2} (\frac{x_{1} + 1}{2}!)^{2} (\frac{8}{(x_{3} + 1)(x_{2} + 1)(x_{1} + 1)}) , \end{matrix}

which is equivalent to

\begin{matrix}(x_{3} + 1)(x_{3} + 1)!(x_{2} + 1)!(x_{1} + 1)! (\frac{k − 1}{2}!)^{4} \\ ≤^{!} 16(k!)^{2} (\frac{x_{3} + 1}{2}!)^{2} (\frac{x_{2} + 1}{2}!)^{2} (\frac{x_{1} + 1}{2}!)^{2} . \end{matrix}

By the Stirling bounds, it suffices to show

(\begin{matrix}(x_{3} + 1)(x_{3} + 1)^{x_{3}+ \frac{3}{2}} (x_{2} + 1)^{x_{2}+ \frac{3}{2}} (x_{1} + 1)^{x_{1}+ \frac{3}{2}} (\frac{k−1}{2})^{2k} \\ · e^{−(x_{3}+x_{2}+x_{1}+2k+1)}e^{\frac{1}{12(x_{3}+1)} + \frac{1}{12(x_{2}+1)} + \frac{1}{12(x_{1}+1)} + \frac{2}{3(k−1)}} \end{matrix} )

≤^{!} ( \begin{matrix}16\sqrt{2π} (\frac{x_{3}+1}{2})^{x_{3}+2} (\frac{x_{2}+1}{2})^{x_{2}+2} (\frac{x_{1}+1}{2})^{x_{1}+2} k^{2k+1} \\ · e^{−(x_{3}+x_{2}+x_{1}+2k+3)}e^{\frac{2}{12k+1} + \frac{2}{6(x_{3}+1)+1} + \frac{2}{6(x_{2}+1)+1} + \frac{2}{6(x_{1}+1)+1}} \end{matrix} ) .

After computations similar to those in previous cases, we see it suffices to show

e^{2}(x_{3} + 1)(k − 1)^{2k}e^{\frac{2}{3(k−1)}} ≤^{!} \frac{\sqrt{2π}}{8} k^{2k+1}\sqrt{(x_{1} + 1)(x_{2} + 1)(x_{3} + 1)} .

Similar to Case 1, it suffices to show that

e ≤^{!} \frac{\sqrt{2π}}{8} \sqrt{(x_{1} + 1)(x_{2} + 1)(x_{3} + 1)}

with x_{1} + 1 ≥ \frac{2k+4}{3} and x_{2} + 1 ≥ 2 and x_{3} + 1 ≥ 2. Thus, the desired inequality holds for

k ≥ \frac{12e^{2}}{π} − 2 ≈ 26.224,

hence all odd k ≥ 27.

Our second special case concerns a certain family of CB graphs with an even number of vertices where the two cycles share exactly one edge. We will need the following lemma, the proof of which follows from straightforward computations after expanding the right hand sides below.

Lemma 29. If k is even, then

M(2k) = (\frac{k + 2}{2}) (\frac{k}{2}) F (k + 1, k − 1, 1).  (6)

If k is odd, then

M(2k) = (\frac{k + 1}{2})^{2} F (k, k, 1).  (7)

For even k, we have

M(2k − 2) = \frac{k}{2(k + 1)}M(2k − 1).  (8)

For odd k, we have

M(2k − 2) = \frac{k − 1}{2k}M(2k − 1).  (9)

For all k, we have

M(2k − 1) = \frac{1}{2}M(2k).  (10)

Finally, if k is even, then

N(C_{k}) = \frac{4}{k}N(C_{k−1}) .  (11)

Proposition 30. Let n = 2k ≥ 10.

(i) If k is even, then

N(CB(k, k, 1)) ≤ M(2k).

(ii) If k is odd, then

N(CB(k + 1, k − 1, 1)) ≤ M(2k).

Proof. For even k, we have

N(CB(k, k, 1)) = N(C_{k} ∨ C_{k}) + k^{2}F (k − 1, k − 1, 1)

=^{(11),(7)} \frac{16}{k^{2}}N(C_{k−1} ∨ C_{k−1}) + \frac{4k^{2}}{k^{2}} M(2k − 2)

Def 12 = \frac{16}{k^{2}}M(2k − 3) + 4M(2k − 2)

=^{(10),(8)} \frac{2}{k(k + 1)}M(2k) + \frac{k − 1}{k}M(2k)

= \frac{k^{2} + 1}{k^{2} + k}M(2k) ≤ M(2k).

For odd k, we have

N(CB(k + 1, k − 1, 1)) = N(C_{k+1} ∨ C_{k−1}) + k^{2}F (k − 1, k − 1, 1)

=^{(11), (6)} \frac{16}{(k + 1)(k − 1)}N(C_{k} ∨ C_{k−2}) + \frac{4(k + 1)(k − 1)}{(k + 1)(k − 1)}M(2k − 2)

Def 12 = \frac{16}{(k + 1)(k − 1)}M(2k − 3) + 4M(2k − 2)

=^{(10),(9)} \frac{2}{k(k + 1)}M(2k) + \frac{k}{k + 1}M(2k)

= \frac{k^{2} + 2}{k^{2} + k}M(2k) ≤ M(2k).

5 Further conjectures and open problems

Through the course of this study, we observed several patterns that remain as conjectures and open questions. First, computational evidence suggests interesting structure for the function F (x_{1}, x_{2}, x_{3}) beyond Theorem 27. We formally record our observations as the following conjecture, which has been confirmed with SageMath [19] for all n less than or equal to 399.

Conjecture 31. For n = 2k and k ≥ 2 with x_{1} + x_{2} + x_{3} = n + 1, the function F (x_{1}, x_{2}, x_{3}) is maximized at F (n − 1, 1, 1). For n = 2k − 1 and k ≥ 3 with x_{1} + x_{2} + x_{3} = n + 1, the function F (x_{1}, x_{2}, x_{3}) is maximized at F (n − 3, 2, 2). Further, for every x_{1} ≥ x_{2} ≥ x_{3} ≥ 3 all even or all odd positive integers, we have

F (x_{1}, x_{2}, x_{3}) ≤ F (x_{1} + 2, x_{2}, x_{3} − 2)

and

F (x_{1}, x_{2}, x_{3}) ≤ F (x_{1} + 2, x_{2} − 2, x_{3}) ,

when the subtraction by 2 will maintain the inequalities on the x_{i}’s.

For example, the first inequality in Conjecture 31 asserts that for x_{1} ≥ x_{2} ≥ x_{3} ≥ 5 all of the same parity,

∑_{j=0}^{x_{3}} \binom{x_{3}}{j}\binom{x_{2}}{\frac{1}{2} (x_{2} − x_{3}) + j}\binom{x_{1}}{\frac{1}{2} (x_{1} − x_{3}) + j}

≤ ∑_{j=0}^{x_{3}−2} \binom{x_{3} − 2}{j}\binom{x_{2}}{\frac{1}{2} (x_{2} − x_{3} + 2) + j}\binom{x_{1} + 2}{\frac{1}{2} (x_{1} − x_{3}) + j} .

Second, the remaining case for Conjecture 13 is the following.

Conjecture 32. If x_{1}, x_{2}, and x_{3} have different parities, then N(CB(x_{1}, x_{2}, x_{3})) ≤ M(n).

Using the recursion given by Corollary 25 and the inequality x_{i} ≤ n, it is straightforward to deduce that N(CB(x_{1}, x_{2}, x_{3})) ≤ 6n^{2}M(n). It is not clear to the authors how to obtain a stronger bound in this case. One direction toward proving Conjecture 32 is the following.

Conjecture 33. For n ≥ 10, the value N(CB(x_{1}, x_{2}, x_{3})) with x_{1} + x_{2} + x_{3} = n + 1 is maximized by

CB(k − 1, k − 1, 2), if n = 2k − 1 and k even;
CB(k, k − 2, 2),  if n = 2k − 1 and k odd;
CB(k, k, 1),  if n = 2k and k even;
CB(k + 1, k − 1, 1), if n = 2k and k odd.

\begin{matrix}WM(7, 2) \\ WM(8, 2) \end{matrix}

Figure 7: Two windmill graphs which are not full.

Using SageMath [19], we have computed N(CB(x_{1}, x_{2}, x_{3})) for all tuples with x_{1} + x_{2} + x_{3} = n + 1 ≤ 535. All of these values are less than or equal to the number of facets of our conjectured maximizer for the corresponding n, providing significant support for Conjecture 33.

Third, when n is even, Proposition 30 gives that the number of facets given by these conjectured maximizing graphs remains less than M(n). Currently, for odd n we do not know of an equality or a bound strong enough to accomplish what (6) and (7) give for even n. Therefore, a similar result for odd n remains unproven. We have verified that such a result holds for all odd n less than 100,000 via computations with SageMath [19].

Fourth and finally, throughout our investigations we sought examples of graphs having a high number of symmetric edge polytope facets. Conjecture 2 asserts that graphs appearing as global facet-maximizers for connected graphs on n vertices can be constructed from minimally intersecting odd cycles, but it is unclear how to prove this. A related problem would be to prove that the graphs appearing as global facet-maximizers in Conjecture 2 are facet-maximizers among connected graphs having a fixed number of edges. We explore this idea a bit further in the special case of the following graphs, which are the conjectured global facet-maximizers for connected graphs on an odd number of vertices.

Definition 34. Let WM(n, r) denote the windmill graph on n vertices consisting of r copies of the cycle C_{3} and n − 1 − 2r edges all wedged at a single vertex. We say a windmill is full if n is odd and r = \frac{n−1}{2}. In other words, a full windmill is a wedge of \frac{n−1}{2} triangles at a single vertex. Denote by WM(n) the full windmill on n vertices.

Proposition 35. For all odd n, we have

N(WM(n)) = 6^{\frac{n−1}{2}}

Proof. The windmill WM(n) is a join of \frac{n−1}{2} 3-cycles. By Lemma 7 and Proposition 9, we obtain

N(WM(n)) = (N(C_{3}))^{\frac{n−1}{2}} = 6^{\frac{n−1}{2}} .

Conjecture 36. For odd n, among graphs with n vertices and 3(n − 1)/2 edges, WM(n) is a facet-maximizer.

To support this conjecture, we used SageMath [19] to sample the space of connected graphs with n vertices and 3(n−1)/2 edges using a Markov Chain Monte Carlo technique [7, Section 2]. We then computed N(P_{G}) for each graph G in our sample. The transition operation we consider is an edge replacement. Starting at a graph G, we produce a new graph G′ by randomly choosing an edge e ∈ E(G) and a non-edge f ∈ E(G)^{C}. Then, if the edges (E(G) \ {e}) ∪ {f} form a connected graph, define G′ to be this graph. If the new graph is not connected, let G′ = G (in other words, sample at G again).

Using this single-edge replacement, the resulting graph of graphs G is regular [7], with each node having in-degree and out-degree both equal to

\frac{3}{2}(n − 1) (\binom{n}{2} − \frac{3}{2}(n − 1)) .

Given two graphs G_{1} and G_{2} in the space, there is a sequence of edge replacements that first transforms a spanning tree of G_{1} into a spanning tree of G_{2} and then replaces all other edges in E(G_{1}) \ E(G_{2}) with edges in E(G_{2}) \ E(G_{1}) in some order. Thus G_{2} is reachable from G_{1} and hence G_{1} is reachable from G_{2} since all edge replacements are reversible. Thus G is strongly connected. Finally, it is straightforward to see that G is aperiodic, as it contains 2-cycles and 3-cycles. Thus, we can conclude that samples from this Markov chain asymptotically obey a uniform distribution, and we can assume that this process uniformly samples the space of connected graphs with n vertices and 3(n − 1)/2 edges. We generated sample families of graphs for all odd n between 5 and 17. The results of our sampling, shown in Figures 8 and 9, support Conjecture 36 for these values of n.

The complexity of counting facets and determining which graphs are facet-maximizers in a case as small as graphs with n vertices and n + 1 edges was unexpected and indicates that there are many factors at play. Therefore, counting the facets of symmetric edge polytopes remains an interesting problem in terms of both establishing formulas and investigating new techniques.

6 Acknowledgments

Both authors were partially supported by National Science Foundation award DMS-1953785. The authors thank Rob Davis and Tianran Chen for helpful discussions. The authors thank the anonymous referees for many helpful suggestions and references. The authors made extensive use of both OEIS [14] and SageMath [19] in this work.

References

[1] T. Chen, R. Davis, and E. Korchevskaia, Facets and facet subgraphs of symmetric edge polytopes, Discrete Appl. Math. 328 (2023), 139–153.

Figure 8: For each odd n between 5 and 17, the plot shows the log of the number of facets of P_{G} for samples of graphs G with n vertices and 3(n − 1)/2 edges with a target sample size of 200 graphs for each n. The line is y = \frac{log(6)}{2}(x − 1), indicating N(WM(n)) for each n.

Figure 9: For n = 13, the histogram shows the distribution of N(P_{G}) for our sample graphs. Not only does the maximum number of facets in our sample occur at 6^{6} = N(WM(13)), but there is a significant gap between our maximizer and all other facet counts in our sample.

[2] T. Chen, R. Davis, and D. Mehta, Counting equilibria of the Kuramoto model using birationally invariant intersection index, SIAM J. Appl. Algebra Geom. 2 (2018), 489– 507.

[3] T. Chen and E. Korchevskaia, Graph edge contraction and subdivisions for adjacency polytopes, arxiv preprint arXiv:1912.02841 [math.CO], 2020. Available at https://

arxiv.org/abs/1912.02841.

[4] A. D’Alí, M. Juhnke-Kubitzke, D. Köhne, and L. Venturello, On the gamma-vector of symmetric edge polytopes, SIAM J. Discrete Math. 37 (2023), 487–515.

[5] A. D’Alí, E. Delucchi, and M. Michałek, Many faces of symmetric edge polytopes, Electron. J. Combin. 29 (2022), Paper No. 3.24.

[6] R. J. Faudree and M. Simonovits, On a class of degenerate extremal graph problems, Combinatorica 3 (1983), 83–93.

[7] B. Fosdick, D. Larremore, J. Nishimura, and J. Ugander, Configuring random graph models with fixed degree sequences, SIAM Rev. 60 (2018), 315–355.

[8] M. Henk, J. Richter-Gebert, and G. Ziegler, Basic properties of convex polytopes, in Handbook of Discrete and Computational Geometry, CRC Press Ser. Discrete Math. Appl., 1997, pp. 243–270.

[9] A. Higashitani, Smooth fano polytopes arising from finite directed graphs, Kyoto J. Math. 55 (2015), 579–592.

[10] A. Higashitani, K. Jochemko, and M. Michałek, Arithmetic aspects of symmetric edge polytopes, Mathematika 65 (2019), 763–784.

[11] T. Kálmán and L. Tóthmérész, Ehrhart theory of symmetric edge polytopes via ribbon structures, arxiv preprint arXiv:2201.10501 [math.CO], 2022. Available at https://

arxiv.org/abs/2201.10501.

[12] T. Matsui, A. Higashitani, Y. Nagazawa, H. Ohsugi, and T. Hibi, Roots of Ehrhart polynomials arising from graphs, J. Algebraic Combin. 34 (2011), 721–749.

[13] B. Nill, Classification of pseudo-symmetric simplicial reflexive polytopes, in Algebraic and Geometric Combinatorics, Contemp. Math., Vol. 443, Amer. Math. Soc., 2006, pp. 269–282.

[14] OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2023. Published electronically at https://oeis.org.

[15] H. Ohsugi and K. Shibata, Smooth Fano polytopes whose Ehrhart polynomial has a root with large real part, Discrete Comput. Geom. 47 (2012), 624–628.

[16] H. Ohsugi and A. Tsuchiya, The h^{∗}-polynomials of locally anti-blocking lattice polytopes and their γ-positivity, Discrete Comput. Geom. 66 (2020), 701–722.

[17] H. Ohsugi and A. Tsuchiya, Symmetric edge polytopes and matching generating polynomials, Comb. Theory 1 (2021), Paper No. 9.

[18] H. Robbins, A remark on Stirling’s formula, Amer. Math. Monthly 62 (1955), 26–29.

[19] The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.2),

    2020. Available at https://www.sagemath.org.

2020 Mathematics Subject Classification: Primary 52B20; Secondary 52B05, 52B12. Keywords: symmetric edge polytope, facet, binomial coefficient.

(Concerned with sequences \underline{A027383}, \underline{A360408}, and \underline{A360409}.)

Received February 28 2023; revised versions received July 7 2023; July 11 2023. Published in Journal of Integer Sequences, July 24 2023.

Return to Journal of Integer Sequences home page.