/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 10 (2016) 255-268
Iterated claws have real-rooted genus polynomials
Jonathan L. Gross * Department of Computer Science, Columbia University, New York, NY 10027, USA
Toufik Mansour
Department of Mathematics, University of Haifa, 3498838 Haifa, Israel
Thomas W. Tucker t
Department of Mathematics, Colgate University, Hamilton, NY 13346, USA
David G. L. Wang í
School of Mathematics and Statistics, Beijing Institute of Technology, 102488 Beijing, P.
R. China
Received 10 September 2013, accepted 27 September 2015, published online 30 November 2015 Abstract
We prove that the genus polynomials of the graphs called iterated claws are real-rooted. This continues our work directed toward the 25-year-old conjecture that the genus distribution of every graph is log-concave. We have previously established log-concavity for sequences of graphs constructed by iterative vertex-amalgamation or iterative edge-amalgamation of graphs that satisfy a commonly observable condition on their partitioned genus distributions, even though it had been proved previously that iterative amalgamation does not always preserve real-rootedness of the genus polynomial of the iterated graph. In this paper, the iterated topological operation is adding a claw, rather than vertex- or edge-amalgamation. Our analysis here illustrates some advantages of employing a matrix representation of the transposition of a set of productions.
Keywords: Topological graph theory, graph genus polynomials, log-concavity, real-rootedness. Math. Subj. Class.: 05A15, 05A20, 05C10
♦Supported by Simons Foundation Grant #315001. t Supported by Simons Foundation Grant #317689.
* Supported by National Natural Science Foundation of China Grant No. 11101010 E-mail addresses: gross@cs.columbia.edu (Jonathan L. Gross), tmansour@univ.haifa.ac.il (Toufik Mansour), ttucker@colgate.edu (Thomas W. Tucker), david.combin@gmail.com; glw@bit.edu.cn (David G. L. Wang)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
255
63	Ars Math. Contemp. 10 (2016) 255-268
1 Introduction
Graphs are implicitly taken to be connected. Our graph embeddings are cellular and orientable. For general background in topological graph theory, see [1, 9]. Prior acquaintance with the concepts of partitioned genus distribution (abbreviated here as pgd) and production (e.g., see [5, 11]) is prerequisite to reading this paper. Subject to this prerequisite, the exposition here is intended to be accessible both to graph theorists and to combinatorialists.
The genus distribution of a graph G is the sequence g0(G), g\(G), g2(G), ..., where gi(G) is the number of combinatorially distinct embeddings of G in the orientable surface of genus i. 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
rG(z) = go(G) + gi(G)z + g2(G)z2 + ...
We say that a sequence A = (ak)n=0 is nonnegative if ak > 0 for all k. An element ak is said to be an internal zero of A if there exist indices i and j with i < k < j, such that aiaj = 0 and ak = 0. If ak-1ak+1 < akk for all k, then A is said to be log-concave. If there exists an index h with 0 < h < n such that
ao < ai < • • • < ah-i < ah > ah+i > ••• > an,
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 [7] by the present authors provides additional contextual information regarding log-concavity and genus distributions.
1.1 The LCGD Conjecture and Real-Rootedness Problems
For convenience, we sometimes abbreviate the phrase "log-concave genus distribution" as LCGD. Proofs that closed-end ladders and doubled paths have LCGDs [2] were based on closed formulas for their genus distributions. Proof that bouquets have LCGDs [8] was based on a recursion. The following conjecture was formulated in [8]:
LCGD Conjecture: Every graph has a log-concave genus distribution.
Stahl [12] used the term "H-linear" to describe chains of graphs obtained by amalgamating copies of a fixed graph H. He conjectured that a number of "H-linear" families of graphs have genus polynomials with nonpositive real roots, which implies the log-concavity of their sequences of coefficients, by Newton's theorem. (Since all the coefficients of a genus polynomial are non-negative, it follows that all the roots are non-positive.) Although it was shown [14] that the genus polynomials of some such families do indeed have real roots, Stahl's conjecture of real-rootedness for W4-linear graphs (where W4 is the 4-wheel) was disproved by Liu and Wang [10].
Our previous paper [7] 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, [7] does support Stahl's expectation that chains of copies of a graph are a relatively accessible aspect of the general LCGD problem. Moreover, Wagner [14] has proved the real-rootedness of the genus polynomials for a number of graph families for which Stahl made specific conjectures of real-rootedness.
J. Gross et al.: Iterated claws have real-rooted genus polynomials
257
This leads to a couple of research problems that are subordinate to the LCGD Conjecture, as follows:
Real-rootedness Problem: Characterize the graphs whose genus polynomials are not real-rooted.
Real-rootedness Chain Problem: Characterize the graphs H whose genus polynomials are real-rooted but whose H-linear chains contain graphs whose genus polynomials are not real-rooted.
Furthermore, we shall see here that Stahl's method of representing what we have elsewhere ([4, 6]) presented 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 log-concave genus distributions.
1.2 Interlacing Roots in a Genus Polynomial Sequence
The earliest proofs [2, 8] of the log-concavity of the genus polynomials for a sequence of graphs appealed directly to the condition aj_1aj+1 < a2. The need for more powerful techniques motivated the development of the linear combination techniques of [7]. Here, to prove the log-concavity of the genus polynomials for the sequence of iterated claws, we combine Newton's theorem that a real-rooted polynomial is log-concave (Theorem 4.1) with a focus on interlacing of roots of consecutive genus polynomials for the graphs in the sequence to prove their log-concavity.
2 The Sequence of Iterated Claws
Let the rooted graph (Y0, u0) be isomorphic to the dipole D3, and let the root u0 be either vertex of D3. For n = 1, 2,..., we define the iterated claw (Yn,un) to be the graph obtained the following surgical operation:
Newclaw: Subdivide each of the three edges incident on the root vertex un-1 of the iterated claw (Yn-1, un-1), and then join the three new vertices obtained thereby to a new root vertex un.
Figure 1 illustrates the graph (Y3, u3).

V2
Figure 1: The rooted graph (Y3,u3).
The graph K13 is commonly called a claw graph, which accounts for our name iterated claw. The notation Yn reflects the fact that a claw graph looks like the letter Y. We observe
x
x
2
3
258
Ars Math. Contemp. 10 (2016) 255-268
that Y1 = K3 3. A recursion for the genus distribution of the iterated claw graphs is derived in [6]. We observe that, whereas all of Stahl's examples [12] of graphs with log-concave genus distributions are planar, the sequence of iterated claws has rising minimum genus. (Example 3.2 of [7] is another sequence of rising minimum genus. However, the graphs in that sequence have cutpoints, unlike the iterated claws.)
We have seen in previous studies of genus distribution (especially [3]) that the number of productions and simultaneous recursions rises rapidly with the number of roots and the valences of the roots. The surgical operation newclaw is designed to circumvent this problem.
For a single-rooted iterated claw (Yn, un), we can define three partial genus distributions, also called partials. Let
an,i = the number of embeddings Yn ^ Si such that
three different fb-walks are incident on the root un ; bni = the number of embeddings Yn ^ Si such that exactly
two different fb-walks are incident on the root un; cn i = the number of embeddings Yn ^ Si such that
one fb-walk is incident three times on the root un.
We also define partial genus polynomials to be the generating functions
œ
An(z) ^ ] an,iZ
i=0
Bn(z) = Y bn,iZi
i=0
œ
Cn(z) ^^ cn,izl.
i=0
Clearly, the full genus distribution is the sum of the partials. That is, for i = 0,1,2,..., we have
and
gi(Yn)	an,i + bn,i + cn,i
Tyn (z) = An (z) + Bn(z) + Cri(z). We define gn,i = gi(Yn).
Remark 2.1. Partitioned genus distributions and recursion systems for pgds were first used by Furst, Gross, and Statman [2]. Stahl [12] was first to employ a matrix equivalent of a production system to investigate log-concavity.
Theorem 2.2. For n > 1, the effect on the pgd of applying the operation newclaw to the iterated claw (Yn-I,un-1) corresponds to the following system of three productions:
ai —>	I2bi+i +4ci+2
bi —> 2 ai +12bi+1 +2ci+1 Ci —> 8ai	+ 8ci+i
(2.1) (2.2) (2.3)
J. Gross et al.: Iterated claws have real-rooted genus polynomials
259
Proof. This is Theorem 4.5 of [6].
□
Corollary 2.3. For n > 1, the effect on the pgd of applying the operation newclaw to the iterated claw (Yn-i, un-i) corresponds to the following recurrence relations:
an,i =	2bn-i,i + 8c„-i,j	(2.4)
bn,i = 12an-i,i-i + 12bn-i,i-i	(2.5)
Cn,i = 4a„-i,i-2 + 2b„-i,i-i + 8c„-i,i-i	(2.6)
Proof. The recurrence system (2.4), (2.5), (2.6) is induced by the production system (2.1), (2.2), (2.3).	□
It is convenient to express such a recurrence system in matrix form:
V(Yn) = M(z) • V(Yn-i)
with the production matrix
M(z) -
0	2	8
12z	12z	0
4z2	2z	8z
(2.7)
(2.8)
	"Ao(z)"		2
V (Yo) =	Bo(z)	=	0
	Co(z)		2z
Since the initial graph Y0 in the sequence of iterated claws is isomorphic to the dipole D3, the initial column vector for the sequence V(Yn) is
(2.9)
Proposition 2.4. The column vector V (Yn) is the product of the matrix power M n(z) with the column vector V(Y0).
Corollary 2.5. The column vector V(Yn) is the product of the matrix power Mn+1(z) with the (artificially labeled) column vector
( °
V (Y_i) = ( °
W4y
Corollary 2.6. To prove that every iterated claw has an LCGD, it is sufficient to prove that the sum of the third column of the matrix Mn(z) is a log-concave polynomial.
3 Characterizing Genus Polynomials for Iterated Claws
In this section, we investigate some properties of the genus polynomials of iterated claws. Corollary 2.6 leads us to focus on the sum of the third column of the matrix Mn(z), which is expressible as (1,1,1)Mn(z)(4V(Y_1)), which implies that it equals 4 times the genus polynomial of the iterated claw Yn-1. Theorem 3.1 formulates a generating function f (z,t) for this sequence of sums, and Theorem 3.2 uses the generating function to construct an expression for the genus polynomials from which we establish interlacing of roots in Section 4.
260
Ars Math. Contemp. 10 (2016) 255-268
Theorem 3.1. The generating function f (z,t) = £ „>0(1,1,1)M„(z)(4V (Y_i ))t„ for the sequence of sums of the third column of M n(z) has the closed form
f(z,t) = _1 + (8 - 12z)t -^ 33 .	(3.1)
JK ' ' 1 - 20zt + 8z(8z - 3)t2 + 384z3t3	v y
Proof. Let (p„, q„, r„) = (1,1,1)Mn(z) for all n > 0. Then
(pn+i,q„+i,r„+i) = (p„ ,q„,r„)M (z)	(3.2)
= (12zq„ + 4z2r„, 2p„ + 12zq„ + 2zr„, 8p„ + 8zr„).
The third coordinate of Equation (3.2) implies that
P„ = 8(r„+i - 8zr„).	(3.3)
By combining (3.3) with the first coordinate of (3.2) we obtain
q„ = 7^(r„+2 - 8zr„+i - 32z2r„).	(3.4) 96z
The second coordinate of (3.2) yields
q„+i = 2p„ + 12zq„ + 2zr„	(3.5) Substituting (3.3) and (3.4) (twice) into (3.5) leads to the recurrence relation
r„ = 20zr„_i + 8z(3 - 8z)r„_2 - 384z3r„_3	(3.6)
with
ro = 1,
ri = 8 + 8z,	(3.7) r2 = 160z + 96z2.
By multiplying Recurrence (3.6) by tn and summing over all n > 0, we obtain Generating
Function (3.1).	□
It is easy to see that rYn (z) = rn+i/4, where r„ is defined in the proof of Theorem 3.1. In terms of rYn (z), the recurrence relation (3.6) becomes
(z) = 20zrYn_1 (z) + 8z(3 - 8z)ry„-2(z) - 384z3ry„_3 (z). (3.8)
Theorem 3.2 provides an explicit expression for the genus polynomial rYn (z), a result is of independent interest. It is not used here toward proof of log-concavity.
Theorem 3.2. The genus polynomial of the iterated claw Y„ is given by
(1,1,1)M„+i(z)V(Y_i) = 2„_i(h„+i(z)+2(2 - 3z)h„(z) - 6zh„_i(z)),
where
h„(z)= E (J + ^ (J + (J + l3) (1 + ^ (1	3j+ii (2z)„_j.
J. Gross et al.: Iterated claws have real-rooted genus polynomials	261
Proof. By Theorem 3.1, we have
/ (z,t) = Dm, DM"*«*- ™r =
n>0
Thus,
1 - 20 zt + 8z(8z - 3)t2 + 384z3t3 '
f (z/2, t/2)
1 + (4 - 3z)t - 3zt2 1 - 5zt + z(4z - 3)t2 + 6z3t3
1 + (4 - 3z)t - 3zt2 (1 - 2zt - 2z2t2)(1 - 3zt) - 3zt2 ^ (1 + (4 - 3z)t - 3zt2)3jzjt2j
(1 - 3zt)j+1(1 + V'3zt)j+1(1 - V'3zt)j+1 '
/m-1+j\
) —
coefficient of tn, we derive the equation
Using the combinatorial identity (1 - at) m = Xj>0 /+j) ajtj, and then finding the
(1,1,1)M"(z/2)V(Yo) = 2" (h„(z) + 2(2 - 3z)h„_i(z) - 6zh„_2(z)), which, by Corollary 2.5, completes the proof.	□
Now let g„,j be the coefficient of z® in rYn (z). The following table of values of g„,j for n < 4 is derived in [6].
gn,i	i — 0	1	2	3	4	5
n — 0	2	2	0	0	0	0
1	0	40	24	0	0	0
2	0	48	720	256	0	0
3	0	0	1920	11648	2816	0
4	0	0	1152	52608	177664	30720
Denote by Ps,t the set of polynomials of the form J2fc=s afczk, where ak is a positive integer for any s < k < t. The above table suggests that rYn(z) G P|_(n+1)/2J,n+1 for n < 4. Theorem 3.3 shows that it holds true in general. Like Theorem 3.2, this enumerative result is of independent interest and is not used toward proof of log-concavity.
Theorem 3.3. For all n > 0, the polynomial rYn(z) G P[(n+1)/2J,n+1. Moreover, we have the leading coefficient
and, for any number i such that |_(n + 1)/2j +1 < i < n, we have
9n,i > 11gn-1,i-1-
(3.10)
262
Ars Math. Contemp. 10 (2016) 255-268
Proof. We see in the table above, for n < 4, that Ymin(Yn) = |(n + 1)/2J and that 7max(Y„) = n + 1, or equivalently, that ^(z) € Pl(«+i)/2J,"+i• We see also, for n < 4, that Equation (3.9) and Inequality (3.10) are true. Now suppose that n > 5. For convenience, let =0 for all i < 0. We can also take =0 for i > k + 1, by induction using (3.8), for k < n. From Recurrence (3.8) and the induction hypothesis, we have
= 20gn_i,i_i +24g„_2,i-i - 64gn-2,i-2 - 384gn-3,i-3, n > 3. (3.11)
For i > n +1, the induction hypothesis implies that each of the four terms on the right side of Recurrence (3.11) is zero-valued. So the degree of rYn (z) is at most n +1. Let
si = gi,i+1. Taking i = n +1 in (3.11), we get
with the initial values so = 2, s1 = 24, s2 = 256. The above recurrence can be solved by a standard generating function method, see [15, p.8]. In practice, we use the command rsolve in the software Maple and get the explicit formula directly as
It follows that gn,n+1 > 0. Hence the degree of rYn (z) is exactly n +1.
Similarly, for i < |(n + 1)/2j, the four terms on the right side of (3.11) are zero-valued, so the minimum genus of Yn is at least |_(n + 1)/2j. Moreover, applying (3.11) with i = |_(n + 1)/2j and using the induction hypothesis gk,i = 0 for all i < |(k + 1)/2j with k < n, we find the first term is positive for n odd and zero for n even, the second term is always positive, and the third and fourth terms are always zero. In other words,
gn,L(n+1)/2J = 2°gn-1,L(n+1)/2J-1 + 24gn-2, L(n+1)/2J_ 1 > 24gn-2, |_(n+1)/2J-1 >
This confirms the minimum genus of Yn is exactly |(n + 1)/2j.
Now consider i such that |(n + 1)/2j +1 < i < n. By (3.11), and using (3.10) inductively, we deduce
gn,i = 11gn-1,i-1 + 24g„-2,i-1 + (9g„-1,i-1 - 64g„-2,i-2 - 384g„-3,i-3)
>	11gn-1,i-1 + 24g„-2,i-1 + (35g„-2,i-2 - 384g
n-3,i-3)
>	11gn-1,i-1 + 24gn-2,i-1 + gn-3,i-3
>	11gn- 1,i-1.
So Inequality (3.10) holds true. It follows that gn,i > 0. Hence
Sn = 20Sn-1 - 64Sn-2 - 384Sn-3,
(3.12)
rY„ (z) € PL(n+1)/2J,n+1.
This completes the proof.
□
J. Gross et al.: Iterated claws have real-rooted genus polynomials
263
4 Genus Polynomials for Iterated Claws are Real-Rooted
Our goal in this section is to establish in Theorem 4.3 the real-rootedness of the genus polynomials rYn (z) of the iterated claws, via an associated sequence Wn (z) of normalized polynomials. It follows from this real-rootedness that the genus polynomials for iterated claws are log-concave, by the following theorem of Newton.
Theorem 4.1 (Newton's theorem). Let a0, ai, ..., an be real numbers and let all the roots of the polynomial
n
P (x) = ^ ajx® j=o
be real. Then > aj_1aj+1 for j = 1,..., n — 1.
Proof. For instance, see Theorem 2 of [13].	□
To proceed, we "normalize" the polynomials rYn (z) by defining
Wn(z) = z-L(n+1)/2JrYn (z),	(4.1)
so that Wn(z) starts from a non-zero constant term, and has the same non-zero roots as rYn (z). We use the symbol dn to denote the degree of Wn(z), that is,
dn = deg Wn(z) = (n + 1) —
n + 1		"n + 1"
_ 2		2
(4.2)
By Theorem 3.3, we have Wn(z) G P0,dn. Substituting (4.1) into the recurrence relation (3.8), we derive
W (z) = i20zWn-i(z)+8(3 — 8z)Wn-2(z) — 384z2Wn-3(z), if n is even, n(z) = |^20Wn_1(z) + 8(3 — 8z)Wn-2(z) — 384zWn-3(z), if n is odd,
(4.3)
with the initial polynomials
Wo(z) = 2(1 + z),
W1(z) = 8(5+ 3z),	(4.4)
W2(z) = 16(3+ 45z + 16z2).
Let P denote the union Un>0P0,n = Un>0{^n=0 akzk | ak G Z+}. Lemma 4.2 is ultimately a consequence of the intermediate value theorem.
Lemma 4.2. Let P(x), Q(x) G P. Suppose that P(x) has roots x1 < x2 < • • • < xdeg P, and that Q(x) has roots y1 < y2 < • • • < ydeg q. If deg Q — deg P G {0,1} and if the roots interlace so that
x1 < y1 < x2 < y2 < • • • ,
then
( —1)i+deg PP(yi) > 0 for all 1 < i < deg Q,	(4.5)
( — 1)j+deg QQ(xj) < 0 for all 1 < j < deg P.	(4.6)
264
Ars Math. Contemp. 10 (2016) 255-268
Proof. Since P(x) is a polynomial with positive coefficients, we have
(_1)deg Pp(_TO) > g.
(4.7)
We suppose first that degP(x) is odd, and we consider the curve P(x). We see that Inequality (4.7) reduces to P(-to) < 0. Thus, the curve P(x) starts in the lower half plane and intersects the x-axis at its first root, xi. From there, the curve P(x) proceeds without going below the x-axis, until it meets the second root, x2. Since x1 < y1 < x2, we recognize that (4.5) holds for i = 1, i.e.,
After passing through x2, the curve P (x) stays below the x-axis up to the third root, x3. It is clear that the curve P(x) continues going forward, intersecting the x-axis in this alternating way. It follows from this alternation that
From (4.8) and (4.9), we conclude that (4.5) holds for all 1 < i < deg Q, when deg P(x) is odd.
We next suppose that deg P(x) is even. In this case, we can draw the curve P(x) so that it starts in the upper half plane, first intersects the x-axis at x1, then goes below the axis up to x2, and continues alternatingly. Therefore the sign-alternating relation (4.9) still holds. Since P(y1) < 0 when deg P(x) is even, we have proved (4.5).
It is obvious that Inequality (4.6) can be shown along the same line. This completes the proof of Lemma 4.2.	□
Now we proceed with our main theorem on the genus polynomial of iterated claws. Beyond proving real-rootedness of the genus polynomials, we derive two interlacing relationships on their roots.
Theorem 4.3. For every n > 0, the polynomial Wn(z) is real-rooted. Moreover, if the roots of Wk (z) are denoted by xk1 < xk 2 < • • •, then we have the following interlacing properties:
(i)	for every n > 2, the polynomial Wn(z) has one more root than Wn-2(z), and the roots interlace so that
x„,1 < x„_2,1 < x„,2 < x„_2,2 < ••• < xn,d„-1 < x„_2,d„-1 < x„,dn;
(ii)	for every n > 1, the polynomial Wn (z) has either one more (when n is even) or the same number (when n is odd) of roots as Wn-1(z), and the roots interlace so that
x„,1 < xn-1,1 < x„,2 < xn—1,2 < ••• < x„-1,dn-1 < xn,dn when n even;
P(yi) > 0.
(4.8)
P(yfc)P(yfc+i) < 0 forall 1 < k < degQ - 1.
(4.9)
and
Xn,i < xn-i,i < x„,2 < xn_i,2 < ••• < x„,dn < i„-i,d„ when n odd.
J. Gross et al.: Iterated claws have real-rooted genus polynomials
265
Proof. From the initial polynomials (4.4), it is easy to verify Theorem 4.3 for n < 2. We suppose that n > 3 and proceed inductively.
For every k < n - 1, we denote the roots of Wk (z) by < xk 2 < • • • < xkjdfc. For convenience, we define xfcj0 = -to and xkjdfc+1 = 0, for all k < n - 1. To clarify the interlacing properties, we now consider the signs of the function Wm(z) at -to and at the origin, for any m > 0. Since Wm(z) is a polynomial of degree dm, with all coefficients non-negative, we deduce that
( —1)dm Wm(-TO) > 0.	(4.10)
Having the constant term positive implies that
Wm(0)= g„,0 > 0.	(4.11)
By the intermediate value theorem and Inequality (4.10), for the polynomial Wn(z) to have dn = deg Wn(z) distinct negative roots and for Part (i) of Theorem 4.3 to hold, it is necessary and sufficient that
(-1)dn+j Wn(x„-2,j) > 0 for 1 < j < d„-2 + 1.	(4.12)
In fact, for j = dn-2 + 1, Inequality (4.12) becomes
(_ 1)dn+dn-2+1w„(0) > 0.	(4.13)
By (4.11), Inequality (4.13) holds if and only if dn + dn-2 is odd, which is true since
dn + 2
"n + 1"		n - 1	=2	n - 1
	+			
2		2		2
+ 1.
Now consider any j such that 1 < j < dn-2. We are going to prove (4.12). We will use the particular indicator function Ieven, which is defined by
J1, if n is even,
Ieven(n) = \
0, if n is odd.
Note that x„_2j is a root of Wn-2(z). By Recurrence (4.3), we have
W„(z„-2,j) = Xj20W„-i(x„-2,j) - 384x„_2,jW„_3(x„-2j)) . (4.14)
Since x„_2jj < 0, the factor £^—2 jn) contributes (-1)n+1 to the sign of the right hand side of (4.14). On the other hand, it is clear that the sign of the parenthesized factor can be determined if both the summands 20Wn_1(xn_2 j) and -384x„_2j Wn_3(i„_2,j) have the same sign. Therefore, Inequality (4.12) holds if
(-1)dn+j+n+1W„_i(x„_2,j) > 0,	(4.15)
(-1)dn+j+n+1W„_3(x„-2,j) > 0.	(4.16)
By the induction hypothesis on part (ii) of this theorem, we can substitute P = Wn-1 and Q = Wn-2 into Lemma 4.2. Then Inequality (4.5) gives
(-1)dn-i+jW„-1(x„_2,j) > 0.	(4.17)
266
Ars Math. Contemp. 10 (2016) 255-268
Thus, Inequality (4.15) holds if and only if the total power
dn + j + n + 1 + dn-1 + j =
"n + 1"		n
	+	—
2		2
+ n + 2 j + 1
of (-1) in (4.15) and (4.17) is even, which is clear by a simple parity argument. Moreover, again using the induction hypothesis on part (ii), we can make substitutions P(x) = Wn-2(x) and Q(x) = Wn-3(x) into Lemma 4.2. Then Inequality (4.6) gives
(_1)dn-3+jW„_3(x„-2,j) < 0. Thus, Inequality (4.16) holds if and only if the total power
dn + j + n + 1 + dn-3 + j
n + 1 2
+
n2
+ n + 2j + 1
(4.18)
(4.19)
of (_1) in (4.16) and (4.18) is odd, which is also clear by a simple parity argument. This completes the proof of (4.12), and the proof of Part (i).
The approach to proving Part (ii) is similar to that used to prove Part (i). By the intermediate value theorem and Inequality (4.10), Part (ii) holds if and only if
(_1)dn+j Wn(xn-1,j ) > 0 for 1 < j < dn-1,
(4.20)
and also for j = dn-1 + 1 when n is even. In fact, when n is even and j = dn-1 + 1, we have
(_1)dn+dn-1 + 1Wn(0) > 0.	(4.21)
By (4.11), Inequality (4.21) holds if and only if (_1)dn+dn-i + 1 = 1, which is clear since
dn + dn 1 + 1 =
"n + 1"		n
	+	—
2		2
+ 1 = n + 2.
For 1 < j < dn-1, we are now going to show (4.20). By setting x = xn-1,j, Recurrence (4.3) turns into
Wn(xn-1,j) = 8(3 _ 8xn-1,j)W„_2(x„_1,j) _ 384xn+Iij(n)Wn-3(xn-1,j). (4.22)
Since xn-1,j < 0, we see that 8(3_8xn-1,j) > 0, and that the factor _384xn-1e'jen( ) contributes (_1)n+1 to the sign of the right-hand side of (4.22). Therefore, Inequality (4.20) holds if
(_1)dn+j Wn-2(xn-1,j) > 0,
(_1)dn+j+n+1Wn-3(xn-1,j) > 0.
(4.23)
(4.24)
Substituting P(x) = Wn-1(x) and Q(x) = Wn-2(x) into Lemma 4.2, we find that Inequality (4.6) yields
(_1)dn-2 + j Wn-2(xn-1,j) < 0 when 1 < j < dn-1. Thus, Inequality (4.23) holds if and only if the total power
(4.25)
dn + j + dn-2 + j
"n + 1"		n _ 1
	+	
2		2
+ 2 j
J. Gross et al.: Iterated claws have real-rooted genus polynomials
267
of (-1) in (4.23) and (4.25) is odd, which holds true, obviously, by parity. On the other hand, by the induction hypothesis on Part (i) and substituting P(x) = Wn-1(x) and Q(x) = Wn-3(x) into Lemma 4.2, Inequality (4.6) becomes
(-1)dn-3+j Wn-3(xn-1,j ) < 0.	(4.26)
Therefore, Inequality (4.24) holds if and only if the total power dn + j + n + 1 + dn-3 + j of (-1) in (4.24) and (4.26) is odd, which coincides with (4.19). This completes the proof of (4.20), ergo the proof of Part (ii), and hence the entire theorem.	□
Corollary 4.4. The sequence of coefficients for every genus polynomial rYn (z) is log-concave.
Proof. Recalling Equation (4.1), we have
ry„ (z) = zL(n+1)/2JWn(z).
By Theorem 4.3, we know that the polynomial Wn(z) is real-rooted. It follows that the polynomial rYn (z) is real-rooted. Applying Theorem 4.1 (Newton's theorem), we know that the polynomial rYn (z) is log-concave.	□
5 On Real-Rootedness
In the study of genus polynomials, the role of real-rootedness may rise beyond being a sufficient condition for log-concavity. The introductory section presents two basic research problems specifically on real-rootedness. One may reasonably anticipate that continuing study of the roots of genus polynomials will lead to new insights into the imbeddings of graphs.
References
[1]	L. W. Beineke and R. J. Wilson (eds.), Topics in topological graph theory, volume 128 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2009, doi:10.1017/CBO9781139087223, with academic consultants J.L. Gross and T.W. Tucker, http://dx.doi.org/10.1017/CBO9781139087223.
[2]	M. L. Furst, J. L. Gross and R. Statman, Genus distributions for two first classes of graphs, J. Combin. Theory Ser.B 46 (1989), 22-36, doi:10.1016/0095-8956(89)90004-X, http://dx. doi.org/10.1016/0095-8956(89)900 04-X.
[3]	J. Gross, Embeddings of graphs of fixed treewidth and bounded degree, Ars Math. Contemp. 7 (2014), 379-403, presented at AMS Meeting in Boston, January 2012.
[4]	J.L. Gross, Genus distribution of graph amalgamations: self-pasting at root-vertices, Australas. J. Combin. 49 (2011), 19-38.
[5]	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.
[6]	J. L. Gross, I. F. Khan and M. I. Poshni, Genus distributions for iterated claws, Electron. J. Combin. 21 (2014), Paper 1.12, 21.
268
Ars Math. Contemp. 10 (2016) 255-268
[7]	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. 29 (2015), 10021029, doi:10.1137/140978867, http://dx.doi.org/10.1137/14 0 9788 67.
[8]	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, doi:10.1016/0095-8956(89)90030-0, http:// dx.doi.org/10.1016/00 95-8 956(89)90030-0.
[9]	J. L. Gross and T. W. Tucker, Topological graph theory, Dover Publications, Inc., Mineola, NY, 2001, reprint of the 1987 original [Wiley, New York; MR0898434 (88h:05034)] with a new preface and supplementary bibliography.
[10]	L. L. Liu and Y. Wang, A unified approach to polynomial sequences with only real zeros, Adv. in Appl. Math. 38 (2007), 542-560, doi:10.1016/j.aam.2006.02.003, http://dx.doi. org/10.1016/j.aam.2 00 6.02.00 3.
[11]	M. I. Poshni, I. F. Khan and J. L. Gross, Genus distributions of graphs under edge-amalgamations, Ars Math. Contemp. 3 (2010), 69-86.
[12]	S. Stahl, On the zeros of some genus polynomials, Canad. J. Math. 49 (1997), 617-640, doi: 10.4153/CJM-1997-029-5, http://dx.doi.org/10.4153/CJM-1997-02 9-5.
[13]	R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, in: Graph theory and its applications: East and West (Jinan, 1986), New York Acad. Sci., New York, volume 576 of Ann. New York Acad. Sci., pp. 500-535, 1989, doi:10.1111/j.1749-6632. 1989.tb16434.x, http://dx.doi.org/10.1111Zj.174 9- 6 632.1989.tb16434. x.
[14]	D. Wagner, Zeros of genus polynomials of graphs in some linear families, Technical Report CORR 97-15, Univ. Waterloo, 1997, 9pp.
[15]	H. S. Wilf, generatingfunctionology, A K Peters, Ltd., Wellesley, MA, 3rd edition, 2006.