Zolotarev polynomials and reduction of Shabat polynomials into a positive characteristic

The paper is focused on the study of Shabat polynomials over fields of different characteristics and their deformation into polynomials with three critical values. Using this deformation, we obtain prime numbers of bad reduction for Shabat polynomials corresponding to trees of diameter 4.     

On plane trees with a prescribed number of valency set realizations

We describe valency sets of plane bicolored trees with a prescribed number of realizations by plane trees. Three special types of plane trees are defined: chains, trees of diameter 4, and special trees of diameter 6. We prove that there is a finite number of valency sets that have R realizations as plane trees and do not belong to these special types. The number of edges of such trees is less than or equal to 12R  + 2. The complete lists of valency sets of plane bicolored trees with 1, 2, or 3 realizations are presented. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 9–17, 2007.     

On the generalized Chebyshev polynomials corresponding to plane trees of diameter 4

The combinatorial classification of plane trees by the number of realizations of their valency sets has distinguished some special classes of plane trees. One of them, the plane trees of diameter 4, turned out to be a very interesting object of investigation from the Galois action point of view. In this paper, we present equation sets for some subclasses of trees of diameter 4, calculate discriminants of the corresponding generalized Chebyshev polynomials, some related polynomials, and their fields of definitions, and use this to get some information about the Galois action on plane trees. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 19–33, 2007.     

Hook Length Polynomials for Plane Forests of a Certain Type

The original motivation for the study of hook length polynomials was to find a combinatorial proof for a hook length formula for binary trees given by Postnikov, as well as a proof for a hook length polynomial formula conjectured by Lascoux. In this paper, we define the hook length polynomial for plane forests of a given degree sequence type and show that it can be factored into a product of linear forms. Some other enumerative results on forests are also given.     

Fourier Expansion of Disk Automorphisms via Scattering in Layered Media

A family of orthogonal polynomials on the disk (which we call scattering polynomials) serves to formulate a remarkable Fourier expansion of the composition of a sequence of Poincaré disk automorphisms. Scattering polynomials are tied to an exotic Riemannian structure on the disk that is hybrid between hyperbolic and Euclidean geometries, and the expansion therefore links this exotic structure to the usual hyperbolic one. The resulting identity is intimately connected with the scattering of plane waves in piecewise constant layered media. Indeed, a recently established combinatorial analysis of scattering sequences provides a key ingredient of the proof. At the same time, the polynomial obtained by truncation of the Fourier expansion elegantly encodes the structure of the nonlinear measurement operator associated with the finite time duration scattering experiment.     

The butterfly decomposition of plane trees

We introduce the notion of doubly rooted plane trees and give a decomposition of these trees, called the butterfly decomposition, which turns out to have many applications. From the butterfly decomposition we obtain a one-to-one correspondence between doubly rooted plane trees and free Dyck paths, which implies a simple derivation of a relation between the Catalan numbers and the central binomial coefficients. We also establish a one-to-one correspondence between leaf-colored doubly rooted plane trees and free Schröder paths. The classical Chung-Feller theorem as well as some generalizations and variations follow quickly from the butterfly decomposition. We next obtain two involutions on free Dyck paths and free Schröder paths, leading to parity results and combinatorial identities. We also use the butterfly decomposition to give a combinatorial treatment of Klazar's generating function for the number of chains in plane trees. Finally we study the total size of chains in plane trees with n edges and show that the average size of such chains tends asymptotically to (n+9)/6.     

Fibonacci polynomials: compositions and cyclic products

Fibonacci (alias Chebyshev) polynomials enjoy particular composition properties. These can be seen (and proved) from a combinatorial perspective by interpreting these polynomials as matching polynomials. An enumerative technique for cyclic structures is applied to obtain a generating polynomial identity for cyclic products of binomial coefficients in terms of matching polynomials.     

Variations of the Catalan numbers from some nonassociative binary operations

We investigate certain nonassociative binary operations that satisfy a four-parameter generalization of the associative law. From this we obtain variations of the ubiquitous Catalan numbers and connections to many interesting combinatorial objects such as binary trees, plane trees, lattice paths, and permutations.     

Reversion of power series and the extended Raney coefficients

In direct as well as diagonal reversion of a system of power series, the reversion coefficients may be expressed as polynomials in the coefficients of the original power series. These polynomials have coefficients which are natural numbers (Raney coefficients). We provide a combinatorial interpretation for Raney coefficients. Specifically, each such coefficient counts a certain collection of ordered colored trees. We also provide a simple determinantal formula for Raney coefficients which involves multinomial coefficients.

     

Recurrence relation with two indices and plane compositions

The aim of this paper is to study analytical and combinatorial methods to solve a special type of recurrence relation with two indices. It is shown that the recurrence relation enumerates a natural combinatorial object called a plane composition. In addition, further interesting recurrence relations arise in the study of statistics for these plane compositions.     

Chains in the Bruhat order

We study a family of polynomials whose values express degrees of Schubert varieties in the generalized complex flag manifold G/B. The polynomials are given by weighted sums over saturated chains in the Bruhat order. We derive several explicit formulas for these polynomials, and investigate their relations with Schubert polynomials, harmonic polynomials, Demazure characters, and generalized Littlewood-Richardson coefficients. In the second half of the paper, we study the classical flag manifold and discuss related combinatorial objects: flagged Schur polynomials, 312-avoiding permutations, generalized Gelfand-Tsetlin polytopes, the inverse Schubert-Kostka matrix, parking functions, and binary trees. A.P. was supported in part by National Science Foundation grant DMS-0201494 and by Alfred P. Sloan Foundation research fellowship. R.S. was supported in part by National Science Foundation grant DMS-9988459.     

A context-free grammar for the e-positivity of the trivariate second-order Eulerian polynomials

Ma-Ma-Yeh made a beautiful observation that a transformation of the grammar of Dumont instantly leads to the γ-positivity of the Eulerian polynomials. We notice that the transformed grammar bears a striking resemblance to the grammar for 0-1-2 increasing trees also due to Dumont. The appearance of the factor of two fits perfectly in a grammatical labeling of 0-1-2 increasing plane trees. Furthermore, the grammatical calculus is instrumental to the computation of the generating functions. This approach can be adapted to study the e-positivity of the trivariate second-order Eulerian polynomials first introduced by Dumont in the contexts of ternary trees and Stirling permutations, and independently defined by Janson, in connection with the joint distribution of the numbers of ascents, descents and plateaux over Stirling permutations.     

A bijective proof of Jackson's formula for the number of factorizations of a cycle

Factorizations of the cyclic permutation into two permutations with respectively n and m cycles, or, equivalently, unicellular bicolored maps with N edges and n white and m black vertices, have been enumerated independantly by Jackson and Adrianov using evaluations of characters of the symmetric group. In this paper we present a bijection between unicellular partitioned bicolored maps and couples made of an ordered bicolored tree and a partial permutation, that allows for a combinatorial derivation of these results.Our work is closely related to a recent construction of Goulden and Nica for the celebrated Harer-Zagier formula, and indeed we provide a unified presentation of both bijections in terms of Eulerian tours in graphs.     

The CRT is the scaling limit of unordered binary trees

We prove that a uniform, rooted unordered binary tree (also known as rooted, binary Pólya tree) with n leaves has the Brownian continuum random tree as its scaling limit for the Gromov‐Hausdorff topology. The limit is thus, up to a constant factor, the same as that of uniform plane trees or labeled trees. Our analysis rests on a combinatorial and probabilistic study of appropriate trimming procedures of trees. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 467–501, 2011     

Minimum degree of the difference of two polynomials over {\mathbb Q}, and weighted plane trees

A weighted bicolored plane tree (or just tree for short) is a bicolored plane tree whose edges are endowed with positive integral weights. The degree of a vertex is defined as the sum of the weights of the edges incident to this vertex. Using the theory of dessins d’enfants, which studies the action of the absolute Galois group on graphs embedded into Riemann surfaces, we show that a weighted plane tree is a graphical representation of a pair of coprime polynomials \(P,Q\in {\mathbb C}\,[x]\) such that: (a)  \(\deg P = \deg Q\) , and \(P\) and \(Q\) have the same leading coefficient; (b) the multiplicities of the roots of  \(P\) (respectively, of  \(Q\) ) are equal to the degrees of the black (respectively, white) vertices of the corresponding tree; (c) the degree of the difference \(P-Q\) attains the minimum which is possible for the given multiplicities of the roots of \(P\)  and  \(Q\) . Moreover, if a tree in question is uniquely determined by the set of its black and white vertex degrees (we call such trees unitrees), then the corresponding polynomials are defined over \({\mathbb Q}\) . The pairs of polynomials \(P,Q\) such that the degree of the difference \(P-Q\) attains the minimum, and especially those defined over \({\mathbb Q}\) , are related to some important questions of number theory. Dozens of papers, from 1965 (Birch et al. in Norske Vid Selsk Forh 38:65–69, 1965) to 2010 (Beukers and Stewart in J Number Theory 130:660–679, 2010), were dedicated to their study. The main result of this paper is a complete classification of the unitrees, which provides us with the most massive class of such pairs defined over  \({\mathbb Q}\) . We also study combinatorial invariants of the Galois action on trees, as well as on the corresponding polynomial pairs, which permit us to find yet more examples defined over  \({\mathbb Q}\) . In a subsequent paper, we compute the polynomials \(P,Q\) corresponding to all the unitrees.     

Parabolic Kazhdan–Lusztig polynomials for quasi-minuscule quotients

We study the parabolic Kazhdan–Lusztig polynomials for the quasi-minuscule quotients of Weyl groups. We give explicit closed combinatorial formulas for the parabolic Kazhdan–Lusztig polynomials of type q. Our study implies that these are always either zero or a monic power of q, and that they are not combinatorial invariants. We conjecture a combinatorial interpretation for the parabolic Kazhdan–Lusztig polynomials of type −1.     

On cographic regular matroids

The presentation of alternating permutatioas via labelled binary trees is used to define polynomials H_2n?1(x) as enumerating polynomials for the height of peaks in alternating permutations of length 2n?1. A divisibility property of the coefficients of these polynomials is proved, which generalizes and explains combinatirially a well-known property of the tangent numbers. Furthermore, a version of the exponential generating function for the H_2n?1(x) is given, leading to a new combinatorial interpretation of Dumont's modified Ghandi-polynomials.     

Variable neighborhood search for extremal graphs 3

In the set of bicolored trees with given numbers of black and of white vertices we describe those for which the largest eigenvalue is extremal (maximal or minimal). The results are first obtained by the automated system AutoGraphiX, developed in GERAD (Montreal), and verified afterwards by theoretical means.     

Plane trees with nine edges. Catalog

Generalized Chebyshev polynomials and definition fields are computed for all pairwise nonisotopic plane trees with nine edges. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 159–195, 2007.