Symmetries in trees and parking functions

We investigate a particular symmetry in labeled trees first discovered by Gessel, which can be stated as follows: In the set of rooted labeled trees on n+1 vertices rooted at the smallest vertex, the number of trees with a descents and b+1 leaves equals the number of trees with b descents and a+1 leaves. We present two new ways to prove the symmetry resulting from decompositions of trees, which lead to three different bijections from trees to trees in which leaves and descents are swapped. We also interpret the symmetry in terms of parking functions: the number of parking functions on [n] with a descents and b unfavorable spaces (defined in this paper) equals the number of parking functions on [n] with b descents and a unfavorable spaces. We conclude with a generalization of these results to binary trees.RésuméNous étudions une symétrie particulière dans les arbres étiquetés, découverte par Gessel, qu'on peut énoncer comme suit: Dans l'ensemble des arbres étiquetés pointés avec n+1 sommets, pointés au sommet minimum, le nombre d'arbres avec a descentes et b+1 feuilles égale le nombre d'arbres avec b descentes et a+1 feuilles. Nous présentons deux nouvelles démonstrations de la symétrie, qui resultent des décompositions des arbres; à partir des décompositions, nous obtenons trois bijections des arbres sur les arbres qui échangent les feuilles et les descentes. De plus, nous interprétons la symétrie en termes des “fonctions de stationnement” (parking functions): le nombre des fonctions de stationnement avec a descentes et b positions défavorables (définies dans cette article) égale le nombre de fonctions de stationnement avec b positions défavorable et a descentes. Nous donnons aussi une généralisation de ces resultats aux arbres binaires.     

Weakly monotone functions

The definition of monotone function in the sense of Lebesgue is extended to the Sobolev spacesW ^1,p ,p >n ? 1. It is proven that such weakly monotone functions are continuous except in a singular set ofp-capacity zero that is empty in the casep =n. Applications to the regularity of mappings with finite dilatation appearing in nonlinear elasticity theory are given.     

Rational Parking Functions and Catalan Numbers

The “classical” parking functions, counted by the Cayley number (n+1) ^n?1, carry a natural permutation representation of the symmetric group S _n in which the number of orbits is the Catalan number \({\frac{1}{n+1} \left( \begin{array}{ll} 2n \\ n \end{array} \right)}\). In this paper, we will generalize this setup to “rational” parking functions indexed by a pair (a, b) of coprime positive integers. These parking functions, which are counted by b ^a?1, carry a permutation representation of S _a in which the number of orbits is the “rational” Catalan number \({\frac{1}{a+b} \left( \begin{array}{ll} a+b \\ a \end{array} \right)}\). First, we compute the Frobenius characteristic of the S _a -module of (a, b)-parking functions, giving explicit expansions of this symmetric function in the complete homogeneous basis, the power-sum basis, and the Schur basis. Second, we study q-analogues of the rational Catalan numbers, conjecturing new combinatorial formulas for the rational q-Catalan numbers \({\frac{1}{[a+b]_{q}} {{\left[ \begin{array}{ll} a+b \\ a \end{array} \right]}_{q}}}\) and for the q-binomial coefficients \({{{\left[ \begin{array}{ll} n \\ k \end{array} \right]}_{q}}}\). We give a bijective explanation of the division by [a+b] _q that proves the equivalence of these two conjectures. Third, we present combinatorial definitions for q, t-analogues of rational Catalan numbers and parking functions, generalizing the Shuffle Conjecture for the classical case. We present several conjectures regarding the joint symmetry and t = 1/q specializations of these polynomials. An appendix computes these polynomials explicitly for small values of a and b.     

Quasi-polynomial functions over bounded distributive lattices

In [6] the authors introduced the notion of quasi-polynomial function as being a mapping f : X ⁿ → X defined and valued on a bounded chain X and which can be factorized as ${f(x_1,\ldots,x_n)=p(\varphi(x_1),\ldots,\varphi(x_n))}In [6] the authors introduced the notion of quasi-polynomial function as being a mapping f : X ⁿ → X defined and valued on a bounded chain X and which can be factorized as f(x₁,?,x_n)=p(j(x₁),?,j(x_n)){f(x_1,\ldots,x_n)=p(\varphi(x_1),\ldots,\varphi(x_n))} , where p is a polynomial function (i.e., a combination of variables and constants using the chain operations ù{\wedge} and ú{\vee}) and j{\varphi} is an order-preserving map. In the current paper we study this notion in the more general setting where the underlying domain and codomain sets are, possibly different, bounded distributive lattices, and where the inner function is not necessarily order-preserving. These functions appear naturally within the scope of decision making under uncertainty since, as shown in this paper, they subsume overall preference functionals associated with Sugeno integrals whose variables are transformed by a given utility function. To axiomatize the class of quasi-polynomial functions, we propose several generalizations of well-established properties in aggregation theory, as well as show that some of the characterizations given in [6] still hold in this general setting. Moreover, we investigate the so-called transformed polynomial functions (essentially, compositions of unary mappings with polynomial functions) and show that, under certain conditions, they reduce to quasi-polynomial functions.     

On convergence analysis of space homeomorphisms

Various theorems on convergence of general spatial homeomorphisms are proved and, on this basis, theorems on convergence and compactness for classes of the so-called ring Q-homeomorphisms are obtained. In particular, it is established that a family of all ring Q-homeomorphisms f in ? ⁿ fixing two points is compact provided that the function Q is of finite mean oscillation. The corresponding applications have been given to mappings in the Sobolev classes W _loc ^1,p for the case p > n ? 1.     

Compactly supported positive definite radial functions

We provide criteria for positive definiteness of radial functions with compact support. Based on these criteria we will produce a series of positive definite and compactly supported radial functions, which will be very useful in applications. The simplest ones arecut-off polynomials, which consist of a single polynomial piece on [0, 1] and vanish on [1, ∞). More precisely, for any given dimensionn and prescribedC ^k smoothness, there is a function inC ^k (? ⁿ ), which is a positive definite radial function with compact support and is a cut-off polynomial as a function of Euclidean distance. Another example is derived from odd-degreeB-splines.     

Bijections on Rooted Trees with Fixed Size of Maximal Decreasing Subtrees

Recently, Seo and Shin showed that the number of rooted trees on [n + 1] = 1, 2, . . . , n+1 such that the maximal decreasing subtree with the same root has k + 1 vertices is equal to the number of functions f : [n] → [n] such that the image of f contains [k]. We give a bijective proof of this theorem.     

Uniform asymptotic expansion for a class of polynomials biorthogonal on the unit circle

An asymptotic expansion including error bounds is given for polynomials {P _n, Q_n} that are biorthogonal on the unit circle with respect to the weight function (1?e^iθ)^α+β(1?e^?iθ)^α?β. The asymptotic parameter isn; the expansion is uniform with respect toz in compact subsets ofC{0}. The pointz=1 is an interesting point, where the asymptotic behavior of the polynomials strongly changes. The approximants in the expansions are confluent hyper-geometric functions. The polynomials are special cases of the Gauss hyper-geometric functions. In fact, with the results of the paper it follows how (in a uniform way) the confluent hypergeometric function is obtained as the limit of the hypergeometric function₂ F ₁(a, b; c; z/b), asb→±∞,z≠b, withz=0 as “transition” point in the uniform expansion.     

An O(n2) simplex algorithm for a class of linear programs with tree structure

In connection with the optimal design of centralized circuit-free networks linear 0–1 programming problems arise which are related to rooted trees. For each problem the variables correspond to the edges of a given rooted tree T. Each path from a leaf to the root of T, together with edge weights, defines a linear constraint, and a global linear objective is to be maximized. We consider relaxations of such problems where the variables are not restricted to 0 or 1 but are allowed to vary continouosly between these bounds. The values of the optimal solutions of such relaxations may be used in a branch and bound procedure for the original 0–1 problem. While in [10] a primal algorithm for these relaxations is discussed, in this paper, we deal with the dual linear program and present a version of the simplex algorithm for its solution which can be implemented to run in time O(n²). For balanced trees T this time can be reduced to O(n log n).     

On some classes of bounded univalent mappings in several complex variables

Let B ⁿ be the Euclidean unit ball in C ⁿ . In this paper, we study several properties of strongly starlike mappings of order α (0 < α < 1) and bounded convex mappings on B ⁿ . We prove that K-quasiregular strongly starlike mappings of order α on B ⁿ have continuous and univalent extensions to ${\overline{B}^n}$ . We show that bounded convex mappings on B ⁿ are strongly starlike of some order α. We give a coefficient estimate for K-quasiregular strongly starlike mappings of order α on B ⁿ . Finally, we give examples of strongly starlike mappings of order α and bounded convex mappings on B ⁿ .     

Counting labelled trees with given indegree sequence

For a labelled tree on the vertex set [n]:={1,2,…,n}, define the direction of each edge ij to be i→j if i<j. The indegree sequence of T can be considered as a partition λ?n−1. The enumeration of trees with a given indegree sequence arises in counting secant planes of curves in projective spaces. Recently Ethan Cotterill conjectured a formula for the number of trees on [n] with indegree sequence corresponding to a partition λ. In this paper we give two proofs of Cotterill's conjecture: one is “semi-combinatorial” based on induction, the other is a bijective proof.     

The lower order of functions of the classB

The class of functions Φ(z, t) defined for z∈ Cⁿ and t ≥0 such that the functions Φ(z, ¦w¦), w∈C, are plurisubharmonic in Cⁿ⁺¹ is called the classD. A typical example of functions of the classB are functions of the form \(\ln M_g (z,t) = \mathop {\ln \sup |}\limits_{|w| = t} g(z,w)|\) where g(z, w), z∈Cⁿ, w∈C, is an entire function in Cⁿ⁺¹. In this note it is proved under certain restrictions on the function Φ(z, t)εB that its lower order relative to the variable t is the same for all z∈Cⁿ except, possibly, for the points z of a set of zero Γ capacity. See [5].     

Cascade search principle and its applications to the coincidence problems of n one-valued or multi-valued mappings

The problem of the construction of a multi-cascade with a given limit subset A is considered in a metric space X. A multi-cascade is a discrete multi-valued dynamic system with the translation semigroup (Z?0,+). The cascade search principle using so-called search functionals is suggested. It gives a solution of the problem. Also, an estimation is obtained for the distance between any initial point x and every correspondent limit point. Several applications of one-valued and multi-valued versions of the mentioned cascade search principle are given for the cases when the limit subset A is (1) the full (or expanded) preimage of a closed subspace under a mapping from X to another metric space; (2) the coincidence set (or expanded coincidence set) of n mappings from X to another metric space (n>1); (3) the common preimage (or the expanded one) of a closed subspace under n mappings; and (4) the common fixed point set of n mappings of the space X into itself (n?1). Generalizations of the previous authors results are obtained. And, in particular cases, generalizations of some recent results by A.V. Arutyunov on coincidences of two mappings and a generalization of Banach fixed point principle are obtained.     

Almost-periodic algebras and their automorphisms

The problem concerning the form of the maximal ideal space of an almost-periodic algebra formed by functions on ? ^m is considered. It is shown that this space is homeomorphic to the topological group dual to the group of frequencies of the algebra under consideration. In the case of a quasiperiodic algebra, the mappings of ? ⁿ generating automorphisms of the algebra are described. Several specific examples are given and a relation to the theory of quasicrystals is indicated.     

Convoluted C-cosine functions and semigroups. Relations with ultradistribution and hyperfunction sines

Convoluted C-cosine functions and semigroups in a Banach space setting extending the classes of fractionally integrated C-cosine functions and semigroups are systematically analyzed. Structural properties of such operator families are obtained. Relations between convoluted C-cosine functions and analytic convoluted C-semigroups, introduced and investigated in this paper are given through the convoluted version of the abstract Weierstrass formula which is also proved in the paper. Ultradistribution and hyperfunction sines are connected with analytic convoluted semigroups and ultradistribution semigroups. Several examples of operators generating convoluted cosine functions, (analytic) convoluted semigroups as well as hyperfunction and ultradistribution sines illustrate the abstract approach of the authors. As an application, it is proved that the polyharmonic operator Δn², n∈N, acting on L²[0,π] with appropriate boundary conditions, generates an exponentially bounded Kn-convoluted cosine function, and consequently, an exponentially bounded analytic Kn+1-convoluted semigroup of angle , for suitable exponentially bounded kernels Kn and Kn+1.     

Pattern avoidance in binary trees

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.     

Fourier frequencies in affine iterated function systems

We examine two questions regarding Fourier frequencies for a class of iterated function systems (IFS). These are iteration limits arising from a fixed finite families of affine and contractive mappings in Rd, and the “IFS” refers to such a finite system of transformations, or functions. The iteration limits are pairs (X,μ) where X is a compact subset of Rd (the support of μ), and the measure μ is a probability measure determined uniquely by the initial IFS mappings, and a certain strong invariance axiom. The two questions we study are: (1) existence of an orthogonal Fourier basis in the Hilbert space L²(X,μ); and (2) explicit constructions of Fourier bases from the given data defining the IFS.     

A sharp threshold for minimum bounded-depth and bounded-diameter spanning trees and Steiner trees in random networks

In the complete graph on n vertices, when each edge has a weight which is an exponential random variable, Frieze proved that the minimum spanning tree has weight tending to ζ(3) = 1/1³ + 1/2³ + 1/3³ +… as n → ∞. We consider spanning trees constrained to have depth bounded by k from a specified root. We prove that if k ≥ log₂ logn+ω(1), where ω(1) is any function going to ∞ with n, then the minimum bounded-depth spanning tree still has weight tending to ζ(3) as n → ∞, and that if k < log₂ logn, then the weight is doubly-exponentially large in log₂ logn ? k. It is NP-hard to find the minimum bounded-depth spanning tree, but when k≤log₂ logn?ω(1), a simple greedy algorithm is asymptotically optimal, and when k ≥ log₂ logn+ω(1), an algorithm which makes small changes to the minimum (unbounded depth) spanning tree is asymptotically optimal. We prove similar results for minimum bounded-depth Steiner trees, where the tree must connect a specified set of m vertices, and may or may not include other vertices. In particular, when m=const×n, if k≥log₂ logn+ω(1), the minimum bounded-depth Steiner tree on the complete graph has asymptotically the same weight as the minimum Steiner tree, and if 1 ≤ k ≤ log₂ logn?ω(1), the weight tends to $(1 - 2^{ - k} )\sqrt {8m/n} \left[ {\sqrt {2mn} /2^k } \right]^{1/(2^k - 1)}$ in both expectation and probability. The same results hold for minimum bounded-diameter Steiner trees when the diameter bound is 2k; when the diameter bound is increased from 2k to 2k+1, the minimum Steiner tree weight is reduced by a factor of $2^{1/(2^k - 1)}$ .     

A sequential dual simplex algorithm for the linear assignment problem

We present a sequential dual-simplex algorithm for the linear problem which has the same complexity as the algorithms of Balinski [3,4] and Goldfarb [8]: O(n²) pivots, O(n² log n + nm) time. Our algorithm works with the (dual) strongly feasible trees and can handle rectangular systems quite naturally.