The structure and distances in Yule recursive trees

Based on uniform recursive trees, we introduce random trees with the factor of time, which are named Yule recursive trees. The structure and the distance between the vertices in Yule recursive trees are investigated in this paper. For arbitrary time t > 0, we first give the probability that a Yule recursive tree Y_t is isomorphic to a given rooted tree γ; and then prove that the asymptotic distribution of ζ_t,m, the number of the branches of size m, is the Poisson distribution with parameter λ = 1/m. Finally, two types of distance between vertices in Yule recursive trees are studied, and some limit theorems for them are established.© 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Projections of the Aldous chain on binary trees: Intertwining and consistency

Consider the Aldous Markov chain on the space of rooted binary trees with n labeled leaves in which at each transition a uniform random leaf is deleted and reattached to a uniform random edge. Now, fix 1 ≤ k<n and project the leaf mass onto the subtree spanned by the first k leaves. This yields a binary tree with edge weights that we call a “decorated k‐tree with total mass n.” We introduce label swapping dynamics for the Aldous chain so that, when it runs in stationarity, the decorated k‐trees evolve as Markov chains themselves, and are projectively consistent over k. The construction of projectively consistent chains is a crucial step in the construction of the Aldous diffusion on continuum trees by the present authors, which is the n→∞ continuum analog of the Aldous chain and will be taken up elsewhere.     

Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees

We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for | U(T) | and thereby arrive at an efficient method of determining | U(T) |. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees | U(T) | grows like O(n³). For some special topology types, we are able to obtain simple closed-form formulae for | U(T) |. Using these results, we find a sharp upper bound on | U(T) | and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric. Received May 18, 2004     

Finding minimal spanning trees in a euclidean coordinate space

The minimal spanning tree problem of a point set in ak-dimensional Euclidean space is considered and a new version of the multifragmentMST-algorithm of Bentley and Friedman is given. The minimal spanning tree is found by repeatedly joining the minimal subtree with the closest subtree. Ak-d tree is used for choosing the connecting edges. Computation time of the algorithm depends on the configuration of the point set: for normally distributed random points the algorithm is very fast. Two extreme cases demandingO(n logn) andO(n ²) operations,n being the cardinality of the point set, are also given.     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998     

Optimizing constrained subtrees of trees

Given a treeG = (V, E) and a weight function defined on subsets of its nodes, we consider two associated problems. The first, called the rooted subtree problem, is to find a maximum weight subtree, with a specified root, from a given set of subtrees.The second problem, called the subtree packing problem, is to find a maximum weight packing of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root.We show that the complexity status of both problems is related, and that the subtree packing problem is polynomial if and only if each rooted subtree problem is polynomial. In addition we show that the convex hulls of the feasible solutions to both problems are related: the convex hull of solutions to the packing problem is given by pasting together the convex hulls of the rooted subtree problems.We examine in detail the case where the set of feasible subtrees rooted at nodei consists of all subtrees with at mostk nodes. For this case we derive valid inequalities, and specify the convex hull whenk 4.Research supported in part by Nato Collaborative Research Grant CRG 900281, Science Program SC1-CT91-620 of the EEC, and contract No 26 of the programme Pôle d'attraction interuniversitaire of the Belgian government.     

Approximate labelled subtree homeomorphism

Given two undirected trees T and P, the Subtree Homeomorphism Problem is to find whether T has a subtree t that can be transformed into P by removing entire subtrees, as well as repeatedly removing a degree-2 node and adding the edge joining its two neighbors. In this paper we extend the Subtree Homeomorphism Problem to a new optimization problem by enriching the subtree-comparison with node-to-node similarity scores. The new problem, called Approximate Labelled Subtree Homeomorphism (ALSH), is to compute the homeomorphic subtree of T which also maximizes the overall node-to-node resemblance. We describe an O(m²n/logm+mnlogn) algorithm for solving ALSH on unordered, unrooted trees, where m and n are the number of vertices in P and T, respectively. We also give an O(mn) algorithm for rooted ordered trees and O(mnlogm) and O(mn) algorithms for unrooted cyclically ordered and unrooted linearly ordered trees, respectively.     

The distribution of the size of the ancestor‐tree and of the induced spanning subtree for random trees

We consider two tree statistics that extend in a natural way the parameters depth of a node resp. distance between two nodes. The ancestor‐tree of p given nodes in a rooted tree T is the subtree of T, spanned by the root and these p nodes and generalizes the depth (ancestor‐tree of a single node), whereas the spanning subtree induced by p given nodes in a tree T generalizes the distance (induced spanning subtree of two nodes). We study the random variables size of the ancestor‐tree resp. spanning subtree size for two tree families, the simply generated trees and the recursive trees. We will assume here the random tree model and also that all () possibilities of selecting p nodes in a tree of size n are equally likely. For random simply generated trees we can then characterize for a fixed number p of chosen nodes the limiting distribution of both parameters as generalized Gamma distributions, where we prove the convergence of the moments too. For some specific simply generated tree families we can give exact formulæ for the first moments. In the instance of random recursive trees, we will show that the considered parameters are asymptotically normally distributed, where we can give also exact formulæ for the expectation and the variance. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004     

On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.Received March 16, 2004     

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.     

Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches

Let p≥2 be an integer and T be an edge-weighted tree. A cut on an edge of T is a splitting of the edge at some point on it. A p-edge-partition of T is a set of p subtrees induced by p−1 cuts. Given p and T, the max-min continuous tree edge-partition problem is to find a p-edge-partition that maximizes the length of the smallest subtree; and the min-max continuous tree edge-partition problem is to find a p-edge-partition that minimizes the length of the largest subtree. In this paper, O(n²)-time algorithms are proposed for these two problems, improving the previous upper bounds by a factor of log (min{p,n}). Along the way, we solve a problem, named the ratio search problem. Given a positive integer m, a (non-ordered) set B of n non-negative real numbers, a real valued non-increasing function F, and a real number t, the problem is to find the largest number z in {b/a|a∈[1,m],b∈B} such that F(z)≥t. We give an O(n+t_F×(logn+logm))-time algorithm for this problem, where t_F is the time required to evaluate the function value F(z) for any real number z.     

Tutte polynomials for trees

We define two two-variable polynomials for rooted trees and one two-variable polynomial for unrooted trees, all of which are based on the coranknullity formulation of the Tutte polynomial of a graph or matroid. For the rooted polynomials, we show that the polynomial completely determines the rooted tree, i.e., rooted trees T₁ and T₂ are isomorphic if and only if f(T₁) = f(T₂). The corresponding question is open in the unrooted case, although we can reconstruct the degree sequence, number of subtrees of size k for all k, and the number of paths of length k for all k from the (unrooted) polynomial. The key difference between these three polynomials and the standard Tutte polynomial is the rank function used; we use pruning and branching ranks to define the polynomials. We also give a subtree expansion of the polynomials and a deletion-contraction recursion they satisfy.     

Isolating a Leaf in Rooted Trees via Random Cuttings

We consider a recursive procedure for destroying rooted trees and isolating a leaf by removing a random edge and keeping the subtree, which does not contain the original root. For two tree families, the simply generated tree families and increasing tree families, we study here the number of random cuts that are necessary to isolate a leaf. We can show limiting distribution results of this parameter for simply generated trees and certain increasing trees. This work was supported by the Austrian Science Foundation FWF, grant S9608-N13.     

On the average number of nodes in a subtree of a tree

For any tree T (labelled, not rooted) of order n, it will be shown that the average number of nodes in a subtree of T is at least $\text{(n + 2)}\text{3}$, with this minimum achieved iff T is a path. For T rooted, the average number of nodes in a subtree containing the root is at least $\text{(n + 1)}\text{2}$ and always exceeds the average over all unrooted subtrees. For the maximum mean, examples show that there are arbitrarily large trees in which the average subtree contains essentially all of the nodes. The mean subtree order as a function on trees is also shown to be monotone with respect to inclusion.     

Über eine Abschätzung der Amplituden in freien Schwingungs-problemen veränderlicher Kreisfrequenz

Summary Consider any differential equation of the form given under (1) below and, ifx(t) is any solution of (1) which is real-valued and does not vanish identically, letC be a half-waveatb of the curvex=x(t) in a (t, x)-plane [by this is meant thatx(a)=0 andx(b)=0 but |x(t)|>0 ifa<t<b]. Then ana priori upper limitation, involving the moments of the coefficient function of (1) [cf. the three integrals in formula (2) of the text, wherea=0 andb=h], is obtained for the ratiom/f. Herem denotes the maximum amplitude occurring inC, andf the area of the region surrounded by the segmentatb on thet-axis and the graph ofC in the (t, x)-plane (this region is always convex).     

Precise Asymptotic Formulas for Semilinear Eigenvalue Problems

. We consider the nonlinear Sturm-Liouville problem¶¶-u"(t) = | u(t) | ^p-1u(t) - lu(t), t ? I :=(0,1), u(0) = u(1) = 0 -u'(t) = \mid u(t)\mid^{p-1}u(t) - \lambda u(t), t \in I :=(0,1), u(0) = u(1) = 0 ,¶¶ where p > 1 and l ? R \lambda \in {\bf R} is an eigenvalue parameter. To investigate the global L²-bifurcation phenomena, we establish asymptotic formulas for the n-th bifurcation branch l = l_n (a) \lambda = \lambda_n (\alpha) with precise remainder term, where a \alpha is the L² norm of the eigenfunction associated with l \lambda .     

A Linear Time Algorithm for Finding ak-Tree Core

Given a tree containingnvertices, consider the sum of the distance between all vertices and ak-leaf subtree (subtree which contains exactlykleaves). Ak-tree core is ak-leaf subtree which minimizes the sum of the distances. In this paper, we propose a linear time algorithm for finding ak-tree core for a givenk.     

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     

On the Combinatorics of Rooted Binary Phylogenetic Trees

We study subtree-prune-and-regraft (SPR) operations on leaf-labelled rooted binary trees, also known as rooted binary phylogenetic trees. This study is motivated by the problem of graphically representing evolutionary histories of biological sequences subject to recombination. We investigate some basic properties of the induced SPR-metric on the space of leaf-labelled rooted binary trees with n leaves. In contrast to the case of unrooted trees, the number |U(T)| of trees in which are one SPR operation away from a given tree depends on the topology of T. In this paper, we construct recursion relations which allow one to determine the unit-neighbourhood size |U(T)| efficiently for any tree topology. In fact, using the recursion relations we are able to derive a simple closed-form formula for the unit-neighbourhood size. As a corollary, we construct sharp upper and lower bounds on the size of unit-neighbourhoods and investigate the diameter of . Lastly, we consider an enumeration problem relevant to population genetics.AMS Subject Classification: 05C05, 92D15.