Jonathan L. Gross^a , Toufik Mansour^b , Thomas W. Tucker^c , David G.L. Wang^d

gross@cs.columbia.edu, tmansour@univ.haifa.ac.il, ttucker@colgate.edu, glw@bit.edu.cn

A Ringel ladder can be formed by a self-bar-amalgamation operation on a symmetric ladder, that is, by joining the root vertices on its end-rungs. The present authors have previously derived criteria under which linear chains of copies of one or more graphs have log-concave genus polynomials. Herein we establish Ringel ladders as the first significant non-linear infinite family of graphs known to have log-concave genus polynomials. We construct an algebraic representation of selfbar-amalgamation as a matrix operation, to be applied to a vector representation of the partitioned genus distribution of a symmetric ladder. Analysis of the resulting genus polynomial involves the use of Chebyshev polynomials. This paper continues our quest to affirm the quarter-century-old conjecture that all graphs have log-concave genus polynomials.

Keywords: genus of a graph, genus polynomial, log-concavity, partitioned genus distribution Mathematics Subject Classification : 05A15, 05A20, 05C10

DOI: 10.5614/ejgta.2015.3.2.1

1. Genus Polynomials

Our graphs are implicitly taken to be connected, and our graph embeddings are cellular and orientable. For general background in topological graph theory, see [13, 1]. Prior acquaintance

Received: 21 July 2014, Revised: 02 April 2015, Accepted: 08 April 2015.

^aDepartment of Computer Science, Columbia University, New York, NY 10027, USA

^bDepartment of Mathematics, University of Haifa, 3498838 Haifa, Israel

^cDepartments of Mathematics, Colgate University, Hamilton, NY 13346, USA

^dSchool of Mathematics and Statistics, Beijing Institute of Technology, 102488, P.R. China

with the concepts of partitioned genus distribution (abbreviated here as pgd) and production (e.g., [10, 17]) are necessary preparation for reading this paper. The exposition here is otherwise intended to be accessible both to graph theorists and to combinatorialists.

The number of combinatorially distinct embeddings of a graph G in the orientable surface of genus i is denoted by gi(G). The sequence g0(G), g1(G), g2(G), . . ., is called the genus distribution of G. A genus distribution contains only finitely many positive numbers, and there are no zeros between the first and last positive numbers. The genus polynomial is the polynomial

\[\Gamma_G(x) = g_0(G) + g_1(G)x + g_2(G)x^2 + \dots\]

Log-concave sequences

A sequence A = (ak) n ^k=0 is said to be nonnegative, if a^k ≥ 0 for all k. An element a^k is said to be an internal zero of A if a^k = 0 and if there exist indices i and j with i < k < j, such that aia^j 6= 0. If ak−1ak+1 ≤ a 2 k for all k, then A is said to be log-concave. If there exists an index h with 0 ≤ h ≤ n such that

\[a_0 \le a_1 \le \dots \le a_{h-1} \le a_h \ge a_{h+1} \ge \dots \ge a_n,\]

then A is said to be unimodal. It is well-known that any nonnegative log-concave sequence without internal zeros is unimodal, and that any nonnegative unimodal sequence has no internal zeros. A prior paper [11] by the present authors provides additional contextual information regarding logconcavity and genus distributions.

For convenience, we sometimes abbreviate the phrase "log-concave genus distribution" as LCGD. Proofs that closed-end ladders and doubled paths have LCGDs [4] were based on explicit formulas for their genus distributions. Proof that bouquets have LCGDs [12] was based on a recursion. A conjecture that all graphs have LCGDs was published by [12].

Stahl's method [21, 22] of representing what we have elsewhere formulated as simultaneous recurrences [4] or as a transposition of a production system for a surgical operation on graph embeddings as a matrix of polynomials can simplify a proof that a family of graphs has logconcave genus distributions, without having to derive the genus distribution itself.

Newton's theorem that real-rooted polynomials with non-negative coefficients are log-concave is one way of getting log-concavity. Stahl [22] made the general conjecture (Conjecture 6.4) that all genus polynomials are real-rooted, and he gave a collection of specific test families. Shortly thereafter, Wagner [24] proved that the genus distributions for the related closed-end ladders and various other test families suggested by [22] are real-rooted. However, Liu and Wang [16] answered Stahl's general conjecture in the negative, by exhibiting a chain of copies of the wheel graph W4, one of Stahl's test families, that is not real-rooted. Our previous paper [11] proves, nonetheless, that the genus distribution of every graph in the W4-linear sequence is log-concave. Thus, even though Stahl's proposed approach to log-concavity via roots of genus polynomials is sometimes infeasible, results in [11] do support Stahl's expectation that chains of copies of a graph are a relatively accessible aspect of the general LCGD problem. The genus distributions for the family of Ringel ladders, whose log-concavity is proved in this paper, are not real-rooted either.

Log-concavity of genus distributions for directed graph embeddings has been studied by [2] and [3]. Another related area is the continuing study of maximum genus of graphs, of which [15] is an example.

Linear, ring-like, and tree-like families

Stahl used the term"H-linear" to describe chains of graphs that are constructed by amalgamating copies of a fixed graph H. Such amalgamations are typically on a pair of vertices, one in each of the amalgamands, or on a pair of edges. It seems reasonable to generalize the usage of linear in several ways, for instance, by allowing graphs in the chain to be selected from a finite set.

We use the term ring-like to describe a graph that results from any of the following topological operations on a doubly rooted linear chain with one root in the first graph of the chain and one in the last graph:

• 1. a self-amalgamation of two root-vertices;
• 2. a self-amalgamation of two root-edges;
• 3. joining one root-vertex to the other root-vertex (which is called a self-bar-amalgamation).

Every graph can be regarded as tree-like in the sense of tree decompositions. However, we use this term only when a graph is not linear or ring-like. For any fixed tree-width w and fixed maximum degree ∆, there is a quadratic-time algorithm [8] to calculate the genus polynomial of graphs of parameters w and ∆. One plausible approach to the general LCGD conjecture might be to prove it for fixed tree-width and fixed maximum degree. Recurrences have been given for the the genus distributions of cubic outerplanar graphs [6], 4-regular outerplanar graphs [18], and cubic Halin graphs [7], all three of which are tree-like. However, none of these genus distributions have been proved to be log-concave. Nor have any other tree-like graphs been proved to have LCGDs.

This paper is organized as follows. Section 2 describes a representation of partitioning of the genus distribution into ten parts as a pgd-vector. Section 3 describes how productions are used to describe the effect of a graph operation on the pgd-vector. Section 4 analyzes how selfbar amalgamation affects the genus distribution. Section 5 offers a new derivation of the genus distributions of the Ringel ladders and proof that these genus distributions are log-concave.

2. Partitioned Genus Distributions

A fundamental strategy in the calculation of genus distributions, from the outset [4], has been to partition a genus distribution according to the incidence of face-boundary walks on one or more roots. We abbreviate "face-boundary walk" as fb-walk. For a graph (G, u, s) with two 2-valent root-vertices, we can partition the number gi(G) into the following four parts:

• ddi(G) the number of embeddings of (G, u, v) in the surface Sⁱ such that two distinct fb-walks are incident on root u and two on root v;
• dsi(G) the number of embeddings in Sⁱ such that two distinct fb-walks are incident on root u and only one on root v;

• sdi(G) the number of embeddings in Sⁱ such that one fb-walk is twice incident on root u and two distinct fb-walks are incident on root v;
• ssi(G) the number of embeddings in Sⁱ such that one fb-walk is twice incident on root u and one is twice incident on root v.

Clearly, we have

\[g_i(G) = dd_i(G) + ds_i(G) + sd_i(G) + ss_i(G).\]

Each of the four parts is sub-partitioned:

• dd⁰ i (G) the number of type-dd embeddings of (G, u, v) in Sⁱ such that neither fb-walk incident at root u is incident at root v;
• dd⁰ i (G) the number of type-dd embeddings in Sⁱ such that one fb-walk incident at root u is incident at root v;
• dd⁰⁰ i (G) the number of type-dd embeddings in Sⁱ such that both fb-walks incident at root u are incident at root v;
• ds⁰ i (G) the number of type-ds embeddings in Sⁱ such that neither fb-walk incident at root u is incident at root v;
• ds⁰ i (G) the number of type-ds embeddings in Sⁱ such that one fb-walk incident at root u is incident at root v;
• sd⁰ i (G) the number of type-sd embeddings in Sⁱ such that the fb-walk incident at root u is not incident on root v;
• sd⁰ i (G) the number of type-sd embeddings in Sⁱ such that the fb-walk at root u is also incident at root v;
• ss⁰ i (G) the number of type-ss embeddings in Sⁱ such that the fb-walk incident at root u is not incident on root v;
• ss¹ i (G) the number of type-ss embeddings in Sⁱ such that the fb-walk incident at root u is incident at root v, and the incident pattern is uuvv;
• ss² i (G) the number of type-ss embeddings in Sⁱ such that the fb-walk incident at root u is incident at root v, and the incident pattern is uvuv.

We define the pgd-vector of the graph(G, u, v) to be the vector

dd⁰⁰(G) dd⁰ (G) dd⁰ (G) ds⁰ (G) ds⁰ (G) sd⁰ (G) sd⁰ (G) ss⁰ (G) ss¹ (G) ss² (G)

with ten coordinates, each a polynomial in x. For instance,

\[ds'(G) = d\tilde{s_0}(G) + ds'_1(G)x + ds'_2(G)x^2 + \cdots\]

3. Symmetric Ladders

We define the symmetric ladder \((\ddot{L}_n, u, v)\) to be the graph obtained from the cartesian product \(P_2 \square P_{n+2}\) by contracting the respective edges at both ends that join a pair of 2-valent vertices and designating the remaining two 2-valent vertices at the ends of the ladder as root-vertices. The symmetric ladders \((\ddot{L}_1, u, v)\) and \((\ddot{L}_2, u, v)\) are illustrated in Figure 3.1. The location of the roots of a symmetric ladder at opposite ends causes it to have a different partitioned genus distribution from other ladders to which it is isomorphic when the roots are disregarded.

Figure 3.1. The symmetric ladders \(\ddot{L}_1\) and \(\ddot{L}_2\).

A production is an algebraic representation of the set of possible effects of a graph operation on a graph embedding. For instance, adding a rung to an embedded symmetric ladder \((\ddot{L}_n, u, v)\) involves inserting a new vertex on each side of the root-vertex v and then joining the two new vertices. Since both the resulting new vertices are trivalent, the number of embeddings of \((\ddot{L}_{n+1}, u, v)\) that can result is 4. Thus, the sum of the coefficients in the consequent of the production (the right side) is 4. Figures 3.2 and 3.3 are topological derivations of the following ten productions used to derive the partitioned genus distribution of \((\ddot{L}_{n+1}, u, v)\) from the partitioned genus distribution of \((\ddot{L}_n, u, v)\).

\[\begin{array}{cccc} dd_i^0 & \longrightarrow & 2dd_i^0 + 2sd_{i+1}^0 \\ dd_i' & \longrightarrow & dd_i^0 + dd_i' + 2sd_{i+1}' \\ dd_i'' & \longrightarrow & 2dd_i' + 2ss_{i+1}^2 \\ ds_i^0 & \longrightarrow & 2ds_i^0 + 2ss_{i+1}^0 \\ ds_i' & \longrightarrow & ds_i^0 + ds_i' + 2ss_{i+1}^1 \\ sd_i^0 & \longrightarrow & 4dd_i^0 \\ sd_i' & \longrightarrow & 4dd_i' \\ ss_i^0 & \longrightarrow & 4ds_i' \\ ss_i^1 & \longrightarrow & 4ds_i' \\ ss_i^2 & \longrightarrow & 2ds_i' + 2dd_i'' \end{array}\]

Figure 3.2. Five productions for construction of symmetric ladders.

Figure 3.3. Five more productions for symmetric ladders.

Theorem 3.1. The pgd-vector of the symmetric ladder \((\ddot{L}_0, u, v)\) is

\[V_{L_0} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}. \tag{3.1}\]

For n>0, the pgd-vector of the symmetric ladder \((\ddot{L}_n,u,v)\) is the product of the row-vector \(V_{L_{n-1}}\) with the \(10\times 10\) production matrix

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

Proof. Each of the ten rows of the matrix M represents one of the ten productions. For instance, the first two rows represent the productions

\[dd_i^0 \longrightarrow 2dd_i^0 + 2sd_{i+1}^0\]
\[dd_i' \longrightarrow dd_i^0 + dd_i' + 2sd_{i+1}' \square\]

Example 3.1. We iteratively calculate pgd-vectors of the symmetric ladders \(L_n\) for \(n \leq 4\)

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

4. Self-Bar-Amalgamations

We recall from Section 1 that the self-bar-amalgamation of any doubly vertex-rooted graph (G, u, v), which is denoted \(\overline{\ast}_{uv}(G, u, v)\), is formed by joining the roots u and v. The present case of interest is when the two roots are 2-valent and non-adjacent. We observe that if G is a cubic 2-connected graph and if each of the two roots is created by placing a new vertex in the interior of an edge of G, then the result of the self-bar amalgamation is again a 2-connected cubic graph.

Theorem 4.1. Let (G, u, v) be a graph with two non-adjacent 2-valent vertex roots. The (non-partitioned) genus distribution of the graph \(\overline{*}_{uv}(G, u, v)\), obtained by self-bar-amalgamation, can be calculated as the dot-product of the pgd-vector \(V_G\) with the following row-vector:

\[B = \begin{pmatrix} 4x & 1+3x & 2+2x & 4x & 2+2x & 4x & 2+2x & 4x & 4 & 4 \end{pmatrix}. \tag{4.1}\]

Proof. Figures 4.1 and 4.2 derive the ten corresponding productions.

\[dd_i^0 \longrightarrow 4g_{i+1}\] \[dd_i' \longrightarrow g_i + 3g_{i+1}\] \[dd'' \longrightarrow 2g_i + 2g_{i+1}\] \[ds_i^0 \longrightarrow 4g_{i+1}\] \[ds_i' \longrightarrow 2g_i + 2g_{i+1}\] \[sd_i^0 \longrightarrow 4g_{i+1}\] \[sd_i' \longrightarrow 2g_i + 2g_{i+1}\] \[sd_i' \longrightarrow 4g_{i+1}\] \[ss_i^0 \longrightarrow 4g_{i+1}\] \[ss_i^0 \longrightarrow 4g_i\] \[ss_i^1 \longrightarrow 4g_i\] \[ss_i^2 \longrightarrow 4g_i \square\]

Figure 4.1. Five productions for self-bar-amalgamation.

Figure 4.2. Five more productions for self-bar-amalgamation.

5. Ringel Ladders

We define a Ringel ladder RLⁿ to be the result of a self-bar-amalgamation on the symmetric ladder (L¨ ⁿ, u, v). Such ladders were introduced by Gustin [14] and used extensively by Ringel [19] in his solution with Youngs [20] of the Heawood map-coloring problem. The Ringel ladder RL⁴ is illustrated in Figure 5.1.

Figure 5.1. The Ringel ladder RL4.

The genus distributions of Ringel ladders were first calculated by Tesar [23]. Our rederivation here is to facilitate our proof of their log-concavity.

Example 5.1. We take dot products of the pgd-vectors calculated in Example 3.1

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

with the vector (4.1)

\[B = \begin{pmatrix} 4x & 1+3x & 2+2x & 4x & 2+2x & 4x & 2+2x & 4x & 4 \end{pmatrix}\]

to obtain the genus polynomials of the corresponding Ringel ladders.

\[\Gamma_{RL_0}(x) = 2 + 2x\] \[\Gamma_{RL_1}(x) = 2 + 14x\] \[\Gamma_{RL_2}(x) = 2 + 38x + 24x^2\] \[\Gamma_{RL_3}(x) = 2 + 70x + 184x^2\] \[\Gamma_{RL_4}(x) = 2 + 118x + 648x^2 + 256x^3\]

Theorem 5.1. The genus distribution of the Ringel ladder \(RL_n\) is given by taking the dot product of the vector B with the product of the vector \(V_{L_0}\) and the matrix \(M^n\), where B is given by (4.1), and M is given by (3.2).

Proof. This follows immediately from Theorem 4.1.

To deduce an explicit expression of \(\Gamma_{RL_n}(x)\), we shall use Chebyshev polynomials. Chebyshev polynomials of the second kind are defined by the recurrence relation

\[U_p(x) = 2xU_{p-1}(x) - U_{p-2}(x),\]

with \(U_0(x) = 1\) and \(U_1(x) = 2x\). It can be equivalently defined by the generating function

\[\sum_{p\geq 0} U_p(x)t^p = \frac{1}{1 - 2xt + t^2}.\] (5.1)

The \(p^{\mathrm{th}}\) Chebyshev polynomial \(U_p(x)\) can be expressed by

\[U_p(x) = \sum_{j>0} (-1)^j \binom{p-j}{j} (2x)^{p-2j}.\]

Theorem 5.2. The genus distribution of the Ringel ladder RLⁿ is given by

\[\Gamma_{RL_n}(x) = (1-x) \sum_{j \ge 0} \left( \binom{n-j}{j} + \binom{n-j+1}{j} \right) (8x)^j + x2^{n+1} \sum_{j \ge 0} \left( \binom{n-j}{j} + \binom{n-j+1}{j} \right) (2x)^j.\]

Proof. Using Theorem 5.1 and mathematical software such as Maple, we calculate the generating function

\[\sum_{n\geq 0} V_{L_0} M^n t^n = (a, b, c, 2xta, 2xtb, 2xta, 2xtb, 4x^2 t^2 a, 4x^2 t^2 b, 2xtc),\]

where

\[a = \frac{2t^2}{(1 - 2t - 8xt^2)(1 - t - 8xt^2)(1 - 4xt^2)},\] \[b = \frac{2t}{(1 - t - 8xt^2)(1 - 4xt^2)},\] \[c = \frac{1}{1 - 4xt^2}.\]

This implies

\[\sum_{n\geq 0} \Gamma_{RL_n}(x)t^n = \sum_{n\geq 0} V_{L_0} M^n B^T t^n\] \[= V_{L_0} (1 - tM)^{-1} B^T\] \[= \frac{2(1 - x)(1 + 4xt)}{1 - t - 8xt^2} + \frac{4x(1 + 2xt)}{1 - 2t - 8xt^2}.\]

From Definition (5.1), we can denote the coefficient ΓRLⁿ (x) of t n in the above generating function in the following form.

\[\Gamma_{RL_n}(x) = (1-x)\sqrt{-8x}^{n+1} \left(\frac{2}{\sqrt{-8x}}U_n\left(\frac{1}{2\sqrt{-8x}}\right) - U_{n-1}\left(\frac{1}{2\sqrt{-8x}}\right)\right) + x\sqrt{-8x}^{n+1} \left(\frac{4}{\sqrt{-8x}}U_n\left(\frac{1}{\sqrt{-8x}}\right) - U_{n-1}\left(\frac{1}{\sqrt{-8x}}\right)\right) = (1-x)\sum_{j\geq 0} \left(2\binom{n-j}{j} + \binom{n-j}{j-1}\right)(8x)^j + x\sum_{j\geq 0} \left(2\binom{n-j}{j} + \binom{n-j}{j-1}\right)2^{n+1+j}x^j.\]

Using the Pascal recursion n k + n k−1 = n+1 k , we get the desired expression.

Theorem 5.3. The Ringel ladders RLⁿ have log-concave genus distributions. Proof. Let an,j be the coefficient of x ^j of ΓRLⁿ (x/2). By Theorem 5.2, we have

\[a_{n,j} = \left[ \binom{n-j}{j} + \binom{n-j+1}{j} - \frac{1}{8} \binom{n-j+1}{j-1} - \frac{1}{8} \binom{n-j+2}{j-1} \right] 4^{j} + 2^{n} \left[ \binom{n-j+1}{j-1} + \binom{n-j+2}{j-1} \right].\]

Note that an,j = 0 for j ≥ bn/2c+2. We define fn(j) = a 2 n,j −an,j−1an,j+1. When j = bn/2c+1, we have an,j+1 = 0 and thus fn(j) = a 2 n,j ≥ 0. So it suffices to show that

\[f_n(j) \ge 0\] for all \(n \ge 2\) and \(1 \le j \le n/2\). (5.2)

Using Maple, it is routine to verify that Inequality (5.2) holds true for n < 100. We now suppose that n ≥ 100, and we define

\[g_n(j) = f_n(j) \cdot \frac{64 \, j! \, (j+1)! \, (n-2j+5)! \, (n-2j+3)!}{(n-j)! \, (n-j-1)!}. \tag{5.3}\]

We employ the expression (5.3) because it can be written, if one replaces j by x, in the form

\[g_n(x) = 16^x s_2 + 2^{n+2x+1} x(n-x+1)(s_1 + 2^{n-2x} s_0),\] (5.4)

where s2, s¹ and s⁰ are polynomials in n and x as follows:

\[s_2 = 256n(n+5)(n+4)(n+3)^2(n+2)^2(n+1)^2 \\ -4(n+3)(n+2)(n+1) \cdot \\ (848n^5 + 10503n^4 + 46749n^3 + 88974n^2 + 64168n + 7680)x \\ + (19140n^7 + 303416n^6 + 1959723n^5 + 6630515n^4 + 12527817n^3 \\ + 12930761n^2 + 6465660n + 1080000)x^2 \\ + (59628n^6 + 799668n^5 + 4257252n^4 + 11406255n^3 \\ + 15964242n^2 + 10757127n + 2565612)x^3 \\ + (110781n^5 + 1228365n^4 + 5215302n^3 \\ + 10470267n^2 + 9734049n + 3223854)x^4 \\ - (122760n^4 + 1099197n^3 + 3570660n^2 + 4898043n + 2323908)x^5 \\ + (75141n^3 + 542916n^2 + 1286307n + 964224)x^6 \\ - (19602n^2 + 137214n + 213840)x^7 + 19602x^8,\]

\[s_1 = 4n(n+4)(n+3)(n+2)(n+1)(184n^2 + 595n + 538) \\ - (288n^7 + 10832n^6 + 97908n^5 + 388214n^4 + 782118n^3 \\ + 803168n^2 + 363528n + 39360)x \\ + (3492n^6 + 66912n^5 + 417975n^4 + 1177485n^3 \\ + 1603200n^2 + 969000n + 174744)x^2 \\ - (17964n^5 + 225066n^4 + 972648n^3 + 1831368n^2 + 1476624n + 375000)x^3 \\ + (50805n^4 + 445635n^3 + 1302147n^2 + 1485999n + 534402)x^4 \\ - (85266n^3 + 519912n^2 + 949644n + 510462)x^5 \\ + (84861n^2 + 331209n + 293922)x^6 - (46332n + 88938)x^7 + 10692x^8,\]

and

\[\frac{s_0}{32(x+1)(n-x)} = 4(n+4)(n+3)(n+2)^2(n+1)\] \[-(20n^4 + 185n^3 + 616n^2 + 883n + 468)x\] \[+(33n^3 + 222n^2 + 501n + 402)x^2 - (18n^2 + 90n + 144)x^3 + 18x^4.\]

In view of (5.2), (5.3) and (5.4), it suffices to show that both s² and s1+2ⁿ−2^x s⁰ are nonnegative for x ≤ n/2.

First, we show that s² ≥ 0. Toward this objective, we write x = kn. Then 0 ≤ k ≤ 1/2. Define s˜² = s2/n. Then s˜² is a polynomial of degree 8 in n. For 0 ≤ j ≤ 8, define

\[q_j = \frac{d^j}{dn^j} \tilde{s}_2.\]

Then we have

\[q_8 = 40320(1 - 2k)(3k - 2)^2(33k^2 - 33k + 8)^2 \ge 0.\]

So q⁷ is increasing in n for any 0 ≤ k ≤ 1/2. We compute

\[\begin{aligned} q_7\big|_{n=4} &= 98794080k^8 - 3852969120k^7 + 14855037120k^6 \\ &- 25338685680k^5 + 24057719280k^4 - 13647130560k^3 \\ &+ 4616115840k^2 - 861376320k + 68382720. \end{aligned}\]

It is elementary to prove that

\[q_7\big|_{n=4} > 0\] for all \(k \in [0, 1/2]\).

Alternatively, one may find this positivity by drawing its figure in Maple. It follows that q⁶ is increasing in the interval [4, ∞) of n. Next, we can compute

\[\begin{aligned} q_6\big|_{n=4} &= 395176320k^8 - 9243020160k^7 + 36108808560k^6 \\ &- 64328152320k^5 + 64252375200k^4 - 38420136000k^3 \\ &+ 13701665520k^2 - 2694375360k + 225239040. \end{aligned}\]

Again, it is routine to prove that

\[q_6\big|_{n=4} > 0\] for all \(k \in [0, 1/2]\).

So \(q_5\) is increasing in n on the interval \([4, \infty)\). Continuing in this bootstrapping way, we can prove that all \(q_4\), \(q_3\), \(q_2\), \(q_1\), \(q_0\) are increasing for \(n \in [4, \infty)\). Since

\[\begin{aligned} q_0\big|_{n=4} &= 321159168k^8 - 4408639488k^7 + 20075655168k^6 \\ &- 46290382848k^5 + 62167349376k^4 - 50943602304k^3 \\ &+ 25184659968k^2 - 6919073280k + 812851200 \end{aligned}\]

is positive for all \(k \in [0, 1/2]\), we conclude that \(q_0 > 0\) for all \(n \ge 4\) and all \(k \in [0, 1/2]\). That is, \(s_2 > 0\).

On the other hand, we define

\[p_n = s_1 + 2^{n-2x} s_0\]

It remains to show \(p_n \ge 0\) for all \(x \in [0, n/2]\). We shall do that for the intervals [0, n/3] and [n/3, n/2], respectively.

For the first interval, we claim that

\[s_0 \ge 0\] for all \(n \ge 100\) and all \(0 \le x \le n/2\). (5.5)

We will show (5.5) by using the same derivative method. In fact, consider

\[\tilde{s_0}(x) = \frac{s_0}{32(x+1)(n-x)}.\]

Note that \(\tilde{s_0}(x)\) is a polynomial in x of degree 4. For \(0 \le j \le 4\), denote

\[\frac{d^j}{dx^j}\tilde{s_0}(x) = \tilde{s}_0^{(j)}(x).\]

Since \(\tilde{s}_0^{(4)}(x) = 432 > 0\), the 3rd derivative

\[\tilde{s_0}^{(3)}(x) = 432x - 108(n^2 + 5n + 8)\]

is increasing on the interval [0, n/2]. Since

\[\tilde{s_0}^{(3)}(n/2) = -108(n^2 + 3n + 8) < 0,\]

we infer that \(\tilde{s_0}^{(3)}(x) < 0\) for all \(x \in [0, n/2]\). So the second derivative

\[\tilde{s_0}^{(2)}(x) = 6(11n^3 + 74n^2 + 167n + 134) - 108(n^2 + 5n + 8)x + 216x^2\]

is decreasing. Since

\[\tilde{s_0}^{(2)}(n/2) = 6(2n^3 + 38n^2 + 95n + 134) > 0,\]

we deduce that s˜⁰ (2)(x) > 0 for all x. Therefore,

\[\tilde{s_0}^{(1)}(x) = -(20n^4 + 185n^3 + 616n^2 + 883n + 468) + 6(11n^3 + 74n^2 + 167n + 134)x - 54(n^2 + 5n + 8)x^2 + 72x^3\]

is increasing. Since

\[\tilde{s_0}^{(1)}(n/2) = -2(n^4 + 43n^3 + 446n^2 + 962n + 936) < 0,\]

we find s˜⁰ (1)(x) < 0. It follows that s˜0(x) is decreasing. Since

\[\tilde{s}_0(n/2) = \frac{1}{8}(7n^4 + 154n^3 + 1112n^2 + 2096n + 1536) > 0,\]

we infer that s0(x) ≥ 0 and this completes the proof for Claim (5.5).

Now, for x ∈ [0, n/3], it suffices to prove that p1(x) = s¹ + 2n/³ s⁰ ≥ 0. This can be done by considering derivatives of p1(x), with respect to x, along the same way. So we omit the proof.

For the other interval [n/3, n/2], we compute

\[f_n(n/2) = \frac{4^n}{1474560}(397n^6 + 9528n^5 + 102100n^4 + 619680n^3 + 2315488n^2 + 5041152n + 5898240) > 0.\]

So we can suppose x ∈ [n/3, n/2 − 1], i.e., n ∈ [2x + 2, 3x]. Define

\[h_j(n) = \frac{d^j}{dn^j} p_n\]

Expanding in n − 2 − 2x, the function 2 ²x−ⁿh8(n) can be recast as

\[2^{2x-n}h_8(n) = \sum_{i=0}^{6} \sum_{j=0}^{7-i} a_{ij}x^j(n-2-2x)^i,\]

where aij ≥ 0. So h8(n) ≥ 0 for all n ∈ [2x + 2, 3x]. It is elementary to prove that the univariate function h7(2x + 2) is non-negative. Again, it is routine to see this by drawing a graph of the function h⁷ with the aid of Maple. It follows that h7(n) ≥ 0 for all n ∈ [2x + 2, 3x]. Then, we check with Maple that h6(2x+2) ≥ 0, from which it follows that h6(n) ≥ 0 for all n ∈ [2x+2, 3x]. Continuing in this way, we can show that, for all n ∈ [2x + 2, 3x], we have

\[h_5(n) \ge 0, \quad h_4(n) \ge 0, \quad \cdots, \quad h_0(n) \ge 0\]

In particular, we have pⁿ = h0(n) ≥ 0.

Acknowledgement

^aSupported by Simons Foundation Grant #315001.

^cSupported by Simons Foundation Grant #317689.

^dSupported by Beijing Institute of Technology Research Fund Program for Young Scholars.

References

• [1] L.W. Beineke, R.J. Wilson, J.L. Gross, and T.W. Tucker, editors, Topics in Topological Graph Theory, Cambridge Univ. Press, 2009.
• [2] C.P. Bonnington, M. Conder, M. Morton, and P. McKenna, J. Combin. Theory Ser. B 85 (2002), 1–20.
• [3] Y. Chen, J.L. Gross, and X. Hu, Enumeration of digraph embeddings, Euro. J. Combin. 36 (2014), 660–678.
• [4] M. Furst, J.L. Gross and R. Statman, Genus distributions for two class of graphs, J. Combin. Theory Ser. B 46 (1989), 523–534.
• [5] J. L. Gross, Genus distribution of graph amalgamations: Self-pasting at root-vertices, Australasian J. Combin. 49 (2011), 19–38.
• [6] J.L. Gross, Genus distributions of cubic outerplanar graphs, J. of Graph Algorithms and Applications 15 (2011), 295–316.
• [7] J.L.Gross, Embeddings of cubic Halin graphs: a surface-by-surface inventory, Ars Math. Contemporanea 6 (2013), 37–56. Online June 2012.
• [8] J.L. Gross, Embeddings of graphs of fixed treewidth and bounded degree, Ars Math. Contemporanea 7 (2014), 379–403. Online Dec 2013. Presented at AMS Annual Meeting at Boston, January 2012.
• [9] J.L. Gross and M.L. Furst, Hierarchy for imbedding-distribution invariants of a graph, J. Graph Theory 11 (1987), 205–220.
• [10] J.L. Gross, I.F. Khan, and M.I. Poshni, Genus distribution of graph amalgamations: Pasting at root-vertices, Ars Combin. 94 (2010), 33–53.
• [11] J.L. Gross, T. Mansour, T.W. Tucker, and D.G.L. Wang, Log-concavity of combinations of sequences and applications to genus distributions, SIAM J. Discrete Math., to appear.
• [12] J.L. Gross, D.P. Robbins, and T.W. Tucker, Genus distributions for bouquets of circles, J. Combin. Theory Ser. B 47 (1989), 292–306.
• [13] J.L. Gross and T.W. Tucker, Topological Graph Theory, Dover, 2001 (original ed. Wiley, 1987).
• [14] W. Gustin, Orientable embedding of Cayley graphs, Bull. Amer. Math. Soc. 69 (1963), 272– 275.
• [15] M. Kotrbcik and M. Skoviera, Matchings, cycle bases, and the maximum genus of a graph, Electronic J. Combin. 19(3) (2012), P3.

• [16] L.L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, Adv. in Appl. Math. 38 (2007), 542–560.
• [17] M.I. Poshni, I.F. Khan, and J.L. Gross, Genus distribution of graphs under edgeamalgamations, Ars Math. Contemp. 3 (2010), 69–86.
• [18] M.I. Poshni, I.F. Khan, and J.L. Gross, Genus distribution of 4-regular outerplanar graphs, Electronic J. Combin. 18 (2011), #P212.
• [19] G. Ringel Map Color Theorem, Springer-Verlag, 1974.
• [20] G. Ringel and J.W.T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. USA 60 (1968), 438–445.
• [21] S. Stahl, Permutation-partition pairs. III. Embedding distributions of linear families of graphs, J. Combin. Theory, Ser. B 52 (1991), 191–218.
• [22] S. Stahl, On the zeros of some genus polynomials, Canad. J. Math. 49 (1997), 617–640.
• [23] E.H. Tesar, Genus distribution of Ringel ladders, Discrete Math. 216 (2000), 235–252.
• [24] D.G. Wagner, Zeros of genus polynomials of graphs in some linear families, Univ. Waterloo Research Report CORR 97-15 (1997), 9pp.