Geometry of plane trees

The “true form” of plane trees, i.e., the geometry of sets p ⁻¹[0, 1], where p is a Chebyshev polynomial, is considered. Empiric data about the true form are studied and systematized. Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 13, No. 6, pp. 149–158, 2007.     

Ballots and plane trees

The correspondence of certain plane trees and binary sequences reported by D. A. Klarner in [1], and a ballot interpretation of the latter, are used to make an independent evaluation of the number of classes of isomorphic, (k + 1)-valent, planted plane trees with kn + 2 points. This provides an interesting multivariable identity for binomial coefficients.     

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.     

The height of multiple edge plane trees

Multi-edge trees as introduced in a recent paper of Dziemiańczuk are plane trees where multiple edges are allowed. We first show that d-ary multi-edge trees where the out-degrees are bounded by d are in bijection with classical d-ary trees. This allows us to analyse parameters such as the height. The main part of this paper is concerned with multi-edge trees counted by their number of edges. The distribution of the number of vertices as well as the height are analysed asymptotically.     

On-line steiner trees in the Euclidean plane

Suppose we are given a sequence ofn points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of lengths of its edges. The points appear one at a time, and at each step the on-line algorithm must construct a connected graph that contains all current points by connecting the new point to the previously constructed graph. This can be done by joining the new point (not necessarily by a straight line) to any point of the previous graph (not necessarily one of the given points). The performance of our algorithm is measured by its competitive ratio: the supremum, over all sequences of points, of the ratio between the total length of the graph constructed by our algorithm and the total length of the best Steiner tree that connects all the points. There are known on-line algorithms whose competitive ratio isO(logn) even for all metric spaces, but the only lower bound known is of [IW] for some contrived discrete metric space. Moreover, for the plane, on-line algorithms could have been more powerful and achieve a better competitive ratio, and no nontrivial lower bounds for the best possible competitive ratio were known. Here we prove an almost tight lower bound of Ω(logn/log logn) for the competitive ratio of any on-line algorithm. The lower bound holds for deterministic algorithms as well as for randomized ones, and obviously holds in any Euclidean space of dimension greater than 2 as well. Noga Alon was supported in part by a USA-Israeli BSF grant.     

Ordered partitions and drawings of rooted plane trees

We study the bounded regions in a generic slice of the hyperplane arrangement in Rⁿ${\mathbb{R}}^n$ consisting of the hyperplanes defined by _xi$x_i$ and _xi+_xj$x_i+x_j$. The bounded regions are in bijection with several classes of combinatorial objects, including the ordered partitions of [n]$\left[n\right]$ all of whose left-to-right minima occur at odd locations and the drawings of rooted plane trees with n+1$n+1$ vertices. These are sequences of rooted plane trees such that each tree in a sequence can be obtained from the next one by removing a leaf.     

On the average hyperoscillations of planted plane trees

Assume that the leaves of a planted plane tree are enumerated from left to right by 1, 2, .... Thej-ths-turn of the tree is defined to be the root of the (unique) subtree of minimal height with leavesj, j+1, ...,j+s−1. If all trees withn nodes are regarded equally likely, the average level number of thej-ths-turn tends to a finite limitα _s (j), which is of orderj ^1/2. Thej-th ”s-hyperoscillation”α ₁(j)−α _s+1(j) is given by 1/2α ₁(s)+O(j ^−1/2) and therefore tends (forj → ∞) to a constant behaving like √8/π·s ^1/2 fors → ∞. These results are obtained by setting up appropriate generating functions, which are expanded about their (algebraic) singularities nearest to the origin, so that the asymptotic formulas are consequences of the so-called Darboux-Pólyamethod.     

Non-existence of distinct codirected locally minimal trees on a plane

Locally minimal graphs on a plane are considered. A simpler proof is given for the uniqueness of a globally minimal tree on a plane in the case of general position. The proof presented here uses only local minimality of trees and is of independent interest.     

On the enumeration of certain sets of planted plane trees

Using the definition of planted plane trees given by D. A. Klarner (“A correspondence between sets of trees,” Indag. Math.31 (1969), 292–296) the number of nonisomorphic classes of certain sets of these trees is enumerated by obtaining a one-to-one correspondence between these classes and certain sets of nondecreasing vectors with integral components. A one-to-one correspondence between sets of (r + 1)-ary sequences and a certain set of planted plane trees is also established, which permits enumeration of this set. Finally, a natural generalization of Klarner's one-to-one correspondence between the above sets of trees and certain sets of edge-chromatic trees is obtained.     

On the trees associated to plane curve singularities and ideals

Si comparano diverse nozioni d’equisingolarità per le curve tracciate sopra una superficie complessa liscia, e per gli ideali di dimensione finita dell’anello locale d’uno dei suoi punti. Si vede che, in generale, questi nozioni sono diverse, ma (per le curve) queste coincidono se esse fossero membri della stessa famiglia continua.     

Fringe analysis of plane trees related to cutting and pruning

Rooted plane trees are reduced by four different operations on the fringe. The number of surviving nodes after reducing the tree repeatedly for a fixed number of times is asymptotically analyzed. The four different operations include cutting all or only the leftmost leaves or maximal paths. This generalizes the concept of pruning a tree. The results include exact expressions and asymptotic expansions for the expected value and the variance as well as central limit theorems.     

Enumeration of coloured plane trees with a given type partition

Tutte's result for the number of planted plane trees with a given degree partition is rederived by a variety of methods and in particular by a simple piecewise construction technique. A theorem of Gordon and Temple is applied in order to give a general relationship between the number of planted plane trees and the number of rooted plane trees and the degree partition restriction is generalised to type partition. The piecewise construction method is successfully used to derive the number of planted plane trees with a given 2-colour degree partition, also derived by Tutte, and an algorithm for the k-coloured case is developed. This algorithm may be used to obtain more specific results. These models are relevant to the statistical mechanics of polymers and this is discussed briefly.     

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.     

The number of spanning trees of plane graphs with reflective symmetry

A plane graph is called symmetric if it is invariant under the reflection across some straight line (called symmetry axis). Let G be a symmetric plane graph. We prove that if there is no edge in G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product of the number of spanning trees of two smaller graphs, each of which has about half the number of vertices of G.