{'fraction_non_alphanumeric': 0.05750969981621401, 'fraction_numerical': 0.01648968756381458, 'mean_word_length': 3.969808448560193, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Log-Concavity of Combinations of Sequences and Applications to Genus Distributions

We formulate conditions on a set of log-concave sequences, under which any linear combination of those sequences is log-concave, and further, of conditions under which linear combinations of log-concave sequences that have been transformed by convolution are log-concave. These conditions involve relations on sequences called \textit{synchronicity} and \textit{ratio-dominance}, and a characterization of some bivariate sequences as \textit{lexicographic}. We are motivated by the 25-year old conjecture that the genus distribution of every graph is log-concave. Although calculating genus distributions is NP-hard, they have been calculated explicitly for many graphs of tractable size, and the three conditions have been observed to occur in the \textit{partitioned genus distributions} of all such graphs. They are used here to prove the log-concavity of the genus distributions of graphs constructed by iterative amalgamation of double-rooted graph fragments whose genus distributions adhere to these conditions, even though it is known that the genus polynomials of some such graphs have imaginary roots. A blend of topological and combinatorial arguments demonstrates that log-concavity is preserved through the iterations.


Introduction
The aim of this paper is two-fold. We are motivated by a long-standing conjecture [26] that the genus distribution of every graph is log-concave. Our initial objective was to confirm this conjecture for several families of graphs. We transform this predominantly topological conjecture here into log-concavity problems for the sum of convolutions of some sequences called partial genus distributions. A simultaneous objective is to contribute new methods to the theory of log-concavity. Our topological graph-theoretic problem leads us to consider special binary relations between log-concave sequences, and also some special bivariate functions that may appear in collections of log-concave sequences. We think that our newly developed concepts of synchronicity, ratio-dominance, and lexicographicity are interesting in their own rights in log-concavity theory. We develop several properties involving convolutions and these notions, including some criteria for the log-concavity of sums of sequences and for the log-concavity of sums of convolutions.
1.1. Historical background. Topological graph theory dates back to Heawood (1890) [29] and Heffter (1891) [30], who transformed the four-color map problem for the plane, into the Heawood problem, which specifies the maximum number of map colors needed for the surfaces of higher genus and for non-orientable surfaces as well. The solution of this problem by Ringel and Youngs (1968) (see [54]) led to development of the study of embeddings of various families of graphs in higher genus surfaces and to simultaneous study of all the possible maps on a given surface. There have subsequently evolved substantial enumerative branches of graph embeddings, according to genus, and maps, according to numbers of edges, with frequent interplay between topological graph theory and combinatorics, as in the present paper.
For instance, a combinatorial formula of Jackson [33] (1987), based on group character theory, is critical to the calculation of the genus distributions of bouquets [26] (bouquets are graphs with one vertex and any number of self-loops). Recent calculations of genus distributions of star-ladders [12] and of embedding distributions of circular ladders [13] use Chebyshev polynomials and the overlap matrix of Mohar [46]. The log-concavity problem for genus distributions, our general target here, is presently one of the oldest unsolved oft-cited problems in topological graph theory.
There have always been two approaches to graph embeddings: fix the graph and vary the surface, or fix the surface and vary the graph. The Heawood Map Theorem can be viewed either way: find the largest complete graph embeddable in the surface of genus g, or find the lowest genus surface in which a given complete graph can be embedded. Genus distribution, along with minimum and maximum genus, are examples of fix-the-graph. Robertson and Seymour's [55] Kuratowski theorem for general surfaces, which solves a problem of Erdös and König [40], is an example of fix-thesurface. Another example is the theory of maps, where the graph embedding itself is fixed and its automorphisms are investigated. For example, until very recently, nothing was known about the regular maps (maps having full rotational symmetry) in a surface of given genus g > 5; a full classification of such maps when g = p + 1 for p prime is given in [16]. Methods there are entirely algebraic, even involving parts of the classification of finite simple groups.
The study of graphs in surfaces has an uncanny history, beginning with the Euler characteristic, of informing combinatorics, topology, and algebra. Kuratowski's Theorem leads to the proof by Robertson and Seymour [56] of the purely graphtheoretic Wagner's Conjecture. Symmetries of maps leads, via Belyi's Theorem, to Grothendieck's dessins d'enfants program [28] to study the absolute Galois group of the rationals by its action on maps [28,35]. It would not be surprising if genus distribution similarly informs enumerative combinatorics.
1.2. Log-concave sequences. Unimodal and log-concave sequences occur naturally in combinatorics, algebra, analysis, geometry, computer science, probability and statistics. We refer the reader to the survey papers of Stanley [62] and Brenti [5] for various results on unimodality and log-concavity.
The log-concavity of particular families of sequences and conditions that imply logconcavity have often been studied before. One such family is Pólya frequency sequences. By the Aissen-Schoenberg-Whitney theorem [1], the sequence (a k ) n k=0 is a Pólya frequency sequence if and only if the polynomial n k=0 a k x k is real-rooted. On the other hand, by a theorem of Newton (see, e.g., [4]), the sequence of coefficients of a real-rooted polynomial is log-concave. This provides an approach for proving the log-concavity of a sequence.
In fact, polynomials arising from combinatorics are often real-rooted; see [36,43,48,60,63]. It is also not uncommon to find classes of polynomials with some members realrooted (and, thus, log-concave), yet with other members log-concave, despite imaginary roots. For example, Wang and Zhao [65] showed that all coordinator polynomials of Weyl group lattices are log-concave, while those of type B n are not real-rooted. In this paper, we confirm the log-concavity of another well-studied sequence from topological graph theory, which was proved to be non-real-rooted, by using one of our criteria for log-concavity.
Recently some probabilists and statisticians care about the negative dependence of random variables. According to Efron [18] and Joag-Dev and Proschan [34], if the independent random variables X 1 , X 2 , . . ., X n have log-concave distributions, then their sum X 1 + X 2 + · · · + X n is stochastically increasing, which in turn results in the negative association of the distribution of (X 1 , X 2 , . . . , X n ) conditional on i∈A X i , for any nonempty subset A of the set {1, 2, . . . , n}.
A recent paper of Huh [32] illustrates analogous interplay between log-concavity and purely chromatic graph theory. Huh proves the unimodality of the chromatic polynomial of any graph, and thereby affirms a conjecture of Read [52] and partially affirms its generalization by Rota [57], Heron [31] and Welsh [68] into the context of matroids.
In this paper, we introduce three new concepts regarding nonnegative log-concave sequences. A principal intent is to develop a tool to deal with a sum of convolutions of log-concave sequences. First, we introduce the binary relation synchronicity of two log-concave sequences, which is symmetric but not transitive; it characterizes pairs of sequences that have synchronously non-increasing ratios of successive elements. As will be seen, synchronized sequences form a monoid, under the usual addition operation. Second, we introduce the binary relation ratio-dominance between two synchronized log-concave sequences, involving comparison of the ratios of successive terms of the same index. We give some criteria for the ratio-dominance relation between two convolutions. In particular, both synchronicity and ratio-dominance are preserved by the convolution transformation associated with any log-concave sequence. Third, we examine collections of log-concave sequences that admit a certain lexicographic condition, which will be used to deal with the ratio-dominance relation between two sums of convolutions of log-concave sequences.
1.3. Genus distribution of a graph. The graph embeddings we discuss are cellular and orientable. Graphs are implicitly taken to be connected. For general background in topological graph theory, see [2,27]. Some prior acquaintance with partitioned genus distributions (e.g., [24,49]) would likely be helpful to a reader of this paper.
The genus distribution of a graph G is the sequence g 0 (G), g 1 (G), g 2 (G), . . ., where g i (G) is the number of combinatorially distinct embeddings of G in the orientable surface of genus i. It follows from the interpolation theorem (see [2,17]) that any genus distribution contains only finitely many positive numbers and that there are no zeros between the first and last positive numbers.
Proofs that the genus distributions of closed-end ladders and of doubled paths are log-concave [19] were based on closed formulas for those genus distributions. Proof that the genus distributions of bouquets are log-concave [26] was based on a recursion.
Stahl [61] 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 these families of graphs have genus polynomials whose roots are real and nonpositive, which implies the log-concavity of their sequences of coefficients. Although it was shown [64] that some of the families do indeed have such genus polynomials, Stahl's conjecture was disproved by Liu and Wang [43].
In particular, Example 6.7 of [61] is a sequence of W 4 -linear graphs, in Stahl's terminology, where W 4 is the 4-wheel. One of the genus polynomials of these graphs was proved to have non-real zeros in [43]. We demonstrate in §3.1, nonetheless, that the genus distribution of every graph in this W 4 -linear sequence is log-concave. Thus, even though Stahl's proposed approach via roots of genus polynomials is insufficient, this paper does support Stahl's expectation that log-concavity of the genus distributions of chains of copies of a graph is a relatively accessible aspect of the general problem. Genus distributions of several non-linear families of graphs are proved to be log-concave in [25].
1.4. Outline of this paper. In §2, we define some possible relationships applying to sequences, and we then derive some purely combinatorial results regarding these relationships, which are used in §3 to establish the log-concavity of the genus distributions of graphs constructed by vertex-and edge-amalgamation operations. We briefly review the theory of partitioned genus distributions at the outset of §3. We present recurrences in §3.1 and §3.2 for calculating the partitioned genus distributions of the graphs in chains of graphs joined iteratively by amalgamations. We establish in these two subsections conditions on the partitioned genus distributions of the amalgamands under which the genus distribution of the vertex-and edge-amalgamated graphs, respectively, and their partial genus distributions are log-concave.

New Development of Log-Concave Sequences
We start by reviewing basic concepts and notation for log-concave sequences. We say that a sequence A = (a k ) n k=0 is nonnegative if a k ≥ 0 for all k. An element a k is said to be an internal zero of A if there exist indices i and j with i < k < j, such that a i a j = 0 and a k = 0. Throughout this paper, all sequences are assumed to be nonnegative and without internal zeros.
If a k−1 a k+1 ≤ a 2 k for all k, then A is said to be log-concave. If there exists and index h with 0 ≤ h ≤ n such that a 0 ≤ a 1 ≤ · · · ≤ a h−1 ≤ a h ≥ a h+1 ≥ · · · ≥ 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. Let B = (b k ) m k=0 be another sequence. The convolution of A and B, denoted as A * B, is defined to be the coefficient sequence To avoid confusion, we remark that in mathematical analysis, some people use the terminology "convolution" to mean the Hadamard product k a k b k x k of the functions f (x) and g(x), which is a topic quite different from ours. By the Cauchy-Binet theorem, the convolution of two log-concave sequences without internal zeros is logconcave; see [45] and [62,Proposition 2].
For any finite sequence A = (a k ) n k=0 , we identify A with the infinite sequence (a k ) ∞ k=−∞ , where a k = a k for 0 ≤ k ≤ n, and a k = 0 otherwise. It is obvious that this identification is compatible with the definitions of unimodality, log-concavity, and convolution. In the sequel, we will frequently employ inequalities of the form a b ≤ c d , where a, b, c, d ≥ 0. For convenience, we consider the inequality a b ≤ c d to hold by default if a = b = 0, or c = d = 0, or b = d = 0. Notation. We write uA to denote the scalar multiple sequence (ua k ), for any constant u ≥ 0. The notation A+B stands for the sequence (a k +b k ). Greek letters α k = a k /a k−1 and β k = b k /b k−1 denote ratios of successive terms of a sequence. Thus, a sequence A is log-concave if and only if the sequence (α k ) is non-increasing in k. For 1 ≤ i ≤ n, let A i = (a i,k ) k be sequences. Then we denote the indexed collection (A i ) n i=1 of sequences by A n . For any sets S and T , we write S ≤ T (or T ≥ S, equivalently) if s ≤ t for all s ∈ S and t ∈ T .
The following lemma will be useful in subsequent subsections.
Proof. The desired inequality is equivalent to the inequality which is true because every summand is non-positive.
In the next two subsections, we introduce the binary relations of synchronicity and ratio-dominance for log-concave sequences, and we give several properties regarding these relations and convolutions of log-concave sequences. In §2.3, we introduce the concept of a lexicographic sequence and we establish a criterion (Theorem 2.15) for the ratio-dominance relation between sums of convolutions of log-concave sequences.
2.1. The synchronicity relation. We say that two nonnegative sequences A and B are synchronized, denoted as A ∼ B, if both are log-concave, and they satisfy Alternatively, the synchronicity of A and B can be defined by the rule Therefore, A ∼ B implies uA ∼ vB for any u, v ≥ 0. In other words, scalar multiplications preserve synchronicity. It is clear that the synchronicity relation ∼ is symmetric. We should be aware of that it is not transitive. We denote by L ∼ the set of indexed collections of pairwise synchronized sequences.
. Then A n ∈ L ∼ if and only if A i ∼ A j for all 1 ≤ i < j ≤ n. We will use the next lemma to prove the synchronicity of sums of synchronized sequences.
Lemma 2.2. Let the three sequences A, B, C be log-concave and nonnegative. If Proof. By Lemma 2.1 (or by direct calculation), we deduce that By the synchronicity rule (2.1), we infer that A + B ∼ C.
Since scalars preserve the synchronicity relation, we see that the 2n sequences Now we show that convolution with the same log-concave sequence preserves synchronicity of two sequences.
Theorem 2.4. Let A, B, C be three log-concave nonnegative sequences without internal zeros. If A ∼ B, then the convolution sequences A * C and B * C are synchronized.
Proof. Since the convolution of two log-concave sequences without internal zeros is log-concave, it follows that the sequences A * C and B * C are log-concave.
To prove that the sequences A * C and B * C are synchronized, we arrange the terms of the product (A * C) k−1 (B * C) k+1 into an array of k rows of k + 2 terms each, in which we number the rows and columns starting at zero, where row j is We similarly arrange the terms of the product (A * C) k (B * C) k into an array of k + 1 rows of k + 1 terms each, in which row j is To prove that (A * C) k−1 (B * C) k+1 ≤ (A * C) k (B * C) k , we will demonstrate that the sum of the terms in the second array is at least as large as the sum of the terms in the first array.
We observe that the k terms in column 0 of the first array are and that the first k terms in column 0 of the second array are Each term a j b 0 c k−j−1 c k+1 is less than or equal to the corresponding term a j b 0 c k−j c k , since, by log-concavity of C, respectively, we have We observe further that the k terms in the (k + 1)-st column of the first array are and that, excluding the term in column 0, the other k terms in row k of the second array are The term a j b k+1 c k−j−1 c 0 of the first array is less than or equal to the corresponding term a k b j+1 c k−j−1 c 0 of the second array, since (by synchronicity of by rows 0 through k − 1 and columns 1 through k, with the sum of the entries in the square subarray of the second array formed by rows 0 through k − 1 and columns 1 through k.
The terms on the main diagonals of these two square arrays are equal. We now consider the sum of any term with i > j, and, hence, below the main diagonal of the first square subarray, and the term whose location is its reflection through that main diagonal. We compare this to the sum of the two terms in the corresponding locations of the second square subarray. By synchronicity of sequences A and B, and since j < i, we have It follows that We conclude that the sum (2.2) is less than or equal to the sum (2.3), and, accordingly, that A similar argument establishes that Thus, the sequences A * C and B * C are synchronized.

2.2.
The ratio-dominance relation. Let A = (a k ) and B = (b k ) be two nonnegative sequences. We say that B is ratio-dominant over A, denoted as B A (or A B equivalently), if A ∼ B and a k+1 b k ≤ a k b k+1 for all k. Alternatively, the ratio-dominance relation can be defined by It is clear that A B implies both A and B are log-concave, and uA vB for any u, v ≥ 0. In other words, the scalars preserve the ratio-dominance relation. From Definition (2.4), we can see that transitivity of the ratio-dominance relation holds if the sequences are pairwise synchronized. Lemma 2.5 will be used in proving Corollary 2.17.
Before exploring basic properties of ratio-dominance, we mention two connections between our ratio-dominance relation and constructs that have been introduced in previous studies of log-concavity.
A nonnegative sequence A = (a k ) is said to be ultra-log-concave of order n, if the sequence (a k / n k ) n k=0 is log-concave, and a k = 0 for k > n. So A is ultra-log-concave of order ∞ if the sequence (k!a k ) is log-concave; see [42]. On the other hand, by (2.4), the ratio-dominance of (ka k ) over A reads as While the second inequality holds trivially, the first inequality represents the logconcavity of the sequence (k!a k ). Therefore, the sequence A is ultra-log-concave of order ∞ if and only if the sequence (ka k ) is ratio-dominant over A.
The other connection relates to Borcea et al.'s work [3, Section 6], which studied the negative dependence properties of almost exchangeable measures. More precisely, they considered log-concave sequences A and B such that It is clear that A ∼ B implies Condition (i), and thus, A B implies both (i) and (ii). As will be seen in the next section, to get the log-concavity of some genus distributions, however, verifying the ratio-dominance relation appears to be easier than checking (i).
We now give some basic observations regarding the ratio-dominance relation. First of all, we shall see by the following theorem that pairwise synchronized sequences can be characterized in terms of ratio-dominance relations. Let A n = (A i ) n i=1 be a sequence of nonnegative sequences.
Notation. In what follows, we use α j,k and β j,k to denote the ratios a j,k /a j,k−1 and b j,k /b j,k−1 , respectively. Theorem 2.6. The following statements are equivalent.
(ii) There exists a sequence B such that A n B.
(iii) There exists a sequence C such that A n C.
Proof. We shall show equivalence of (i) and (ii). The equivalence of (i) and (iii) is along the same line. Suppose that A n ∈ L ∼ . Then let k 0 be the largest index k such that there exists an integer i such that 1 ≤ i ≤ n, with Consider the sequence B defined by b k 0 = 1 and Notation. The notations A n ∈ L (and, respectively, , for all 1 ≤ i < j ≤ n, facilitate expression of a ratio-dominance analogue to Theorem 2.6.
Theorem 2.7. The following statements are equivalent.
(i) A n ∈ L .
In particular, we have α j,k+1 ≤ α i,k ≤ α j,k . By (2.4), we deduce A n ∈ L . This completes the proof. Now we give one of the main results of in this section, which will be used in the next subsection to establish several ratio-dominance relations between convolutions. Proof. Let A * D = (s k ) and B * C = (t k ). We also define L = s n+1 s n and R = t n t n−1 .
To prove Theorem 2.8, it is sufficient to establish the inequality L ≤ R, since the inequality s n−1 t n+1 ≤ s n t n will then follow by symmetry. Toward that objective, we first observe that ∂L ∂d 0 = a n+1 s n − a n s n+1 s 2 n = 1 s 2 n n i=0 d i (a n−i a n+1 − a n+1−i a n ) − a 0 a n d n+1 ≤ 0. Therefore, For any 0 ≤ k ≤ n, we now define Then Inequality (2.6) reads L ≤ g 0 , and we pause here in the proof of Theorem 2.8 for the following lemma.
Lemma 2.9. For any number k such that 0 ≤ k ≤ n − 1, we have g k ≤ g k+1 , where g k is defined by Equation (2.7).
Proof. Let 0 ≤ k ≤ n − 1. Denote the sum in the denominator of g k by M . Then which is nonnegative, by the log-concavity of D. Since A B, we deduce that This completes the proof of Lemma 2.9.
Then, to prove that L ≤ R, it suffices to show The difference between the sides of Inequality (2.8) is 0≤i≤n 0≤j≤n On the other hand, since C D, we derive that This proves Inequality (2.8), and it thereby completes the proof of Theorem 2.8.
We caution that A B and C D do not together imply that A + C B + D. Next is an immediate corollary of Theorem 2.8. Corollary 2.10. Let A n and B n be two sequences of nonnegative sequences without internal zeros. Suppose that A n ∈ L and B n ∈ L , then the sequences A k * B k are pairwise synchronized. In other words, we have For any sequences A n and B m of nonnegative sequences, we write A n B m if A i B j for any 1 ≤ i ≤ n and 1 ≤ j ≤ m. Proof. Let u 1 , u 2 , . . . , u n , v 1 , v 2 , . . . , v m ≥ 0. By Lemma 2.1, we have This proves the desired ratio-dominance relation, by Definition (2.4). Theorem 2.11 will be used to prove the ratio-dominance relation between sums of sequences. The inverse statement does not hold, unless there are some synchronicity relations between the sequences. We give the simplest case as follows, which can be proved directly from the definitions. We mention that the ratio-dominance relation A B or A B implies the synchronicity A ∼ B, which, in turn, implies the log-concavity of A and of B. This leads to the following two sufficiency criteria for the log-concavities of sequences, which are obtained respectively from Theorem 2.3 and Corollary 2.10.
Theorem 2.13. Suppose that A n ∈ L ∼ . For any u 1 , u 2 , . . . , u n ≥ 0, the sequence n i=1 u i A i is log-concave. Theorem 2.14. Suppose that A n ∈ L and B n ∈ L . For any u 1 , u 2 , . . . , u n ≥ 0, the sequence n i=1 u i A i * B i is log-concave.
We remark that Theorem 2.3, Theorem 2.8, Corollary 2.10 and Theorem 2.11 are not only interesting in their own rights, but also potentially useful toward the conjectures in §4 regarding log-concavity of partial genus distributions of graphs.

Lexicographic bivariate functions.
For every 1 ≤ i ≤ n, let F i = (f i,k ) k be a nonnegative sequence. We distinguish the sequence F i from the sequence A i by allowing f i,k = +∞. More precisely, we suppose that 0 ≤ f i,k ≤ +∞ for any i and k. Regarding f i,k as bivariate functions, we say that the finite sequence (F i ) n i=1 of sequences is lexicographic if Equivalently, the lexicographicity of the bivariate function f i,k can be defined by (2.10) f 1,k ≤ f 2,k ≤ · · · ≤ f n,k ≤ f 1,k+1 for all k.
That is, the entries in each column of a representation of (f i,k ) as an array are in non-decreasing order, and they are less than or equal to every entry in subsequent columns.
Theorem 2.15. Let A n , B n , W n be three sequences of nonnegative sequences without internal zeros. Suppose that W n ∈ L , and the bivariate functions b i,t /a i,t and a i,t−1 /b i,t are both lexicographic. Then we have In other words, Inequality (2.11) holds true for any W n ∈ L if (2.12) b 1,t a 1,t ≤ b 2,t a 2,t ≤ · · · ≤ b n,t a n,t ≤ b 1,t+1 a 1,t+1 and for all t.
Proof. By Definition (2.4), Relation (2.11) is equivalent to We shall now deal with these two respective inequalities. The first inequality in (2.14) is equivalent to the inequality When i = j, the inner summation in (2.15) becomes Let s < t. Since W i is log-concave, we have On the other hand, we have Therefore, the i = j part of the summand in (2.15) is nonpositive. For the i = j part, we can make the transformation 1≤i =j≤n s,t Let i < j. Then W i W j , which implies that w i,k+1−s w j,k−t − w j,k+1−t w i,k−s is nonpositive (resp., nonnegative) if s ≤ t (resp., s > t). Therefore, (2.15) holds true if a j,t−1 b i,s − a i,s−1 b j,t is nonnegative (resp., nonpositive) for all i < j, when s ≤ t (resp., s > t). Since A j ∼ B j , the function b j,t /a j,t−1 in t is non-increasing. Therefore, Condition (2.14) is equivalent to the iterated inequality Along the same line, the second inequality in (2.14) holds if Combining (2.16) and (2.17), we find that they can be recast as Now we are going to further reduce the above inequality system. Note that (2.18) holds for all i < j if and only if it holds for all j = i + 1, that is, By the second inequality in (2.20), the function a i,t /b i,t+1 in i is non-decreasing. So (2.21) holds for all i < j if and only if it holds for i = 1 and j = n, that is, Similarly, the second inequality in (2.19) is equivalent to The inequalities (2.22) and (2.23) can be written together as Finally, it is clear that the combination of (2.20) and (2.24) is equivalent to the two lexicographical conditions. Using n = 2, Theorem 2.15 will be applied in the next section toward proving the log-concavity of the genus distributions of some families of graphs. When n = 1, Theorem 2.15 reduces to the following extension of Theorem 2.4, i.e., the convolution transformation induced from the same log-concave sequence preserves ratio-dominance.  Proof. Since A D and B C, we deduce A * C ∼ B * D by Theorem 2.8. By Corollary 2.16, we have A * C B * C and B * C B * D. Now the desired relation follows immediately from Lemma 2.5.
To provide a better interpretation of the lexicographic conditions in the statement of Theorem 2.15, the next theorem gives some of its consequences.
Theorem 2.18. Let A n and B n be two sequences of nonnegative sequences. Suppose that both the functions b i,t /a i,t and a i,t−1 /b i,t are lexicographic. Then A n ∈ L , B n ∈ L and A i B i for all 1 ≤ i ≤ n.

Proof. By the definition (2.4), the relation
Note that all the transformations beyond Relation (2.17) are equivalences. The first inequality in (2.25) can be seen from (2.19), while the second is clear from (2.20). This proves that A n ∈ L . For the same reason, we have B n ∈ L . As aforementioned, the relation A i B i can be seen from (2.12) and (2.13). This completes the proof.
2.4. The offset sequence. In this subsection, we introduce a concept to be used in the next section, which is interesting in its own right. For any sequence A = (a k ), we define the associated offset sequence A + = (a + k ) by a + k = a k−1 for all k. It is easy to prove the following proposition.
Proposition 2.19. Let A and B be nonnegative sequences. Then we have the following equivalence relations: In particular, A A + .
We remark that A B does not imply A ∼ B + . The next theorem is a corollary of Theorem 2.8, with a proof similar to the last part of the proof of Theorem 2.8. Proof. By Proposition 2.19, we have C C + . Applying Theorem 2.8, we deduce B * C ∼ A * C + . Now it suffices to show that The difference between the sides of the above inequality can be transformed as On the other hand, the logconcavity of the sequence C implies c n−i c n−1−j − c n−i−1 c n−j ≤ 0. Therefore, every summand in the above sum is nonnegative. This completes the proof.

Partial Genus Distributions
We denote the oriented surface of genus i by S i . For any vertex-rooted (or edgerooted) graph (G, y), with y either a 2-valent vertex or an edge with two 2-valent endpoints, we define g i (G) : the number of embedding G → S i . d i (G, y) : the number of embeddings G → S i , such that two different face-boundary walks are incident on y. s i (G, y) : the number of embeddings G → S i such that a single face-boundary walk is twice incident on root y. We observe that g i (G) = d i (G, y) + s i (G, y).
We define the genus distribution polynomial as the power series Γ(G)(x) = g 0 (G) + g 1 (G)x + g 2 (G)x 2 + · · · and the partial genus distribution polynomials by We say that the genus distribution Γ(G) is partitioned into the partial genus distributions D(G, y) and S(G, y), and we refer to the pair {D(G, y), S(G, y)} as a partitioned genus distribution.
More generally we allow any subgraph of a graph to serve as a root. The number of partial genus distributions needed for calculations involving amalgamations rises rapidly with the number of vertices and edges in the root subgraph. The best understood instances are when the root comprises two vertices or two edges. We say then that the graph is doubly rooted. Just as a single-root partial genus distribution refines a total genus distribution, a double-root partial genus distribution refines a single-root distribution.
We observe that genus distributions are integer sequences with non-negative terms, only finitely many non-zero terms, and no internal zeros (due to the "interpolation theorem"). It is not presently known whether partial genus distributions can have internal zeros.
Remark. Although calculating the minimum genus of a graph is known to be NPhard, it has been proved that for any fixed treewidth and bounded degree, there is a quadratic-time algorithm [22] for calculating genus distributions and partial genus distributions. Nonetheless, it is not a practical algorithm. The values in the partial genus distributions given in this paper were calculated by a "brute force" computer program created by Imran Khan. Using symmetries, it is not difficult to calculate the partial genus distribution values used in Examples 3.1, 3.2, and 3.4 by hand. A hand calculation for Example 3.5 would be tedious.
3.1. Iterative amalgamation at vertex-roots. In this subsection, we present a theorem that will enable us to establish conditions sufficient for all the members of a sequence of graphs constructed by iterative vertex-amalgamation to have logconcave genus distributions. For amalgamations involving a doubly vertex-rooted graph (G, u, v) with two 2-valent roots, the following partitioning of the embedding counting variable g i (G) is described in [20]: . We use two upper-case letters to denote the corresponding double-root partial genus distributions, for which purpose we signify the graph by a subscript. For instance, DS (G,u,v) denotes the sequence It is sometimes convenient to use the groupings . When we form a linear chain of copies of a graph G, we suppress the first root in the initial copy of G, and we define Proof. This theorem is a form of Corollary 3.8 of [24].
Theorem 3.2. Let (G, t) be a vertex-rooted graph such that D (G,t) S (G,t) . Let (H, u, v) be a doubly vertex-rooted graph. We introduce the following abbreviations: (H,u,v) , Then the partial genus distributions D (X,v) and S (X,v) of the vertex-rooted graph (X, v), obtained from G H by merging vertices t and u, are both log-concave; moreover, we have D (X,v) S (X,v) .
Proof. In view of (3.1) and (3.2), we observe that Therefore, we deduce D (X,v) S (X,v) by Theorem 2.15 directly. This completes the proof. Corollary 3.3. Let (G, t) be a vertex-rooted graph such that D (G,t) S (G,t) . Let (H k , u k , v k ) n k=1 be a sequence of doubly vertex-rooted graphs, whose partial genus distributions satisfy Relation (3.4). Then the iteratively vertex-amalgamated graph has log-concave partial genus distributions D (Xn,vn) and S (Xn,vn) , and D (Xn,vn) S (Xn,vn) . Moreover, the genus distribution Γ(X) is log-concave.
Proof. The proof is by iterative application of Theorem 3.2 and application of Lemma 2.2 to the sum Γ(X) = D (Xn,vn) + S (Xn,vn) . None of them has internal zeros. Since any inequality of the form 0 0 ≤ x y is considered to be true, the lexicographical conditions in (3.4)  It is easy to verify that Γ(X) is indeed log-concave. Note that any inequality of the form 0 0 ≤ x y is considered to be true. Therefore, as a consequence of Corollary 3.3, despite the Liu-Wang disproof of Stahl's conjecture that the roots of the genus polynomials of all these W 4 -chains are real, we conclude that every W 4 -chain constructed by iterative vertex-amalgamation has a log-concave genus distribution. Moreover, the single-root partials of every W 4 -chain are log-concave and synchronized. None of them has internal zeros. Moreover, in this case, the lexicographical conditions in (3.4) reduce to  It is again easy to verify that D (X,v) S (X,v) , and that Γ(X) is log-concave. We conclude that every M L 4 -chain constructed by iterative vertex-amalgamation has logconcave genus distribution and log-concave single-root partial genus distributions. Example 3.3. By combining Example 3.1 and Example 3.2, we see that if X is a vertex-amalgamation chain of copies of W 4 and M L 4 , interspersed arbitrarily with each other, then the genus distribution Γ(X) is log-concave. Moreover, the single-root partials are log-concave and synchronized.

3.2.
Iterative amalgamation at edge-roots. This section presents the edge amalgamation analogy to the vertex-amalgamation discussion in §3.1. When a graph has two edge-roots and both endpoints of both edge-roots are 2-valent, the partitioning is similar to the case of two 2-valent vertex-roots. However, the recursions used for constructing linear chains of copies of a graph have different coefficients. Definitions of the double-edge-rooted partials are given in [49]. A key difference from vertex-amalgamation is that the two ways of merging two root edges can lead to nonisomorphic graphs with the same partial genus distributions. Proof. This theorem is a corollary of Theorems 3.2, 3.3, and 3.4 (collectively) of [49].
It is easy to derive the next result, analogous to Theorem 3.2, if one notices that D (W,f ) = 2D (G,e) * A 1 + (2D (G,e) + 4S (G,e) ) * A 2 , Theorem 3.5. Let (G, e) be an edge-rooted graph such that D (G,e) S (G,e) . Let (H, g, f ) be a doubly edge-rooted graph. We introduce the following abbreviations: Suppose that Then the partial genus distributions D (W,f ) and S (W,f ) of the edge-rooted graph (W, f ), obtained from G H by merging edges e and g, are both log-concave; moreover, we have D (W,f ) S (W,f ) .
We observe that Relation (3.4) and Relation (3.9) are of the same form.
Corollary 3.6. Let (G, e) be an edge-rooted graph such that the partial distributions D (G,t) and S (G,t) are log-concave and that D (G,e) S (G,e) . Let (H k , u k , v k ) n k=1 be a sequence of doubly edge-rooted graphs whose partial genus distributions are all logconcave and satisfy Relation (3.9). Then the iteratively edge-amalgamated graph (W n , f n ) = (G, e) * (H 1 , g 1 , f 1 ) * · · · * (H n , g n , f n ) has log-concave partial genus distributions D (Wn,fn) and S (Wn,fn) , and D (Wn,fn) S (Wn,fn) . Moreover, the genus distribution Γ(W ) is log-concave. Proof. The proof is by iterative application of Theorem 3.2 and application of Lemma 2.2 to the sum Γ(W ) = D (Wn,fn) + S (Wn,fn) .
Example 3.4. Let (G, e) be the complete graph K 4 with a root-edge created as the middle segment of a trisection of any edge of K 4 . Let (H, g, f ) be K 4 with two rootedges created as the middle segments of non-adjacent edges of K 4 , as illustrated in The doubly edge-rooted graph (H, g, f ) has the following non-zero partial genus distributions:  We conclude that every K 4 -chain constructed by iterating edge-amalgamations has a log-concave genus distribution. Moreover, the single-root partials are log-concave and synchronized.
Example 3.5. Let (G, e) be the circulant graph circ(7 : 1, 2) with root-edges created as middle segments of trisections of edges, as shown in Figure 3 e G H f g The doubly edge-rooted graph (H, g, f ) has the following non-zero partial genus distributions:  We conclude that every one of these circ(7 : 1, 2)-chains has a log-concave genus distribution. Moreover, the single-root partials are log-concave and synchronized. This example illustrates that the properties we need to apply these new methods are not restricted to very small graphs.

Conclusions
We have introduced some new methods for proving the log-concavity of a linear combination of log-concave sequences and of log-concave sequences that have been transformed by convolutions. We have used these methods to show that linear chains of graphs that satisfy certain conditions known to be true of many graphs, and which are possibly true for all graphs, have log-concave genus distributions. This motivates further study and development of these new methods for application to proving the log-concavity of the genus distributions of larger classes of graphs.
We have proved that, given a collection of graphs that are doubly vertex-rooted or doubly edge-rooted, whose partitioned genus distributions satisfy conditions given in Corollary 3.3 or Corollary 3.6, respectively, a linear chain formed from those graphs by iterative amalgamation has a log-concave genus distribution and log-concave partial genus distributions, as well.
We offer two restricted forms of the log-concavity conjecture for genus distributions of graphs. For Conjecture 4.1, the productions in Table 2.1 of [20] lead to an expression for Γ(X) as a linear combination of double-root partials and some of their offset sequences. For Conjecture 4.2, Theorems 2.6 and 2.7 of [51] give productions for the two ways to self-amalgamate a doubly edge-rooted graph.  To the best of our knowledge, no one has found a graph whose genus distribution or partial genus distribution has internal zeros. We have not encountered any graph with a non-log-concave partial genus distribution. Based on these observations, we pose a third conjecture.