Davenport–Schinzel Trees*

In this paper we study labeled–tree analogues of (generalized) Davenport–Schinzel sequences.We say that two sequences a ₁ ... a _k , b ₁ ... b _k of equal length k are isomorphic, if a _i = a _j i b _i = b _j (for all i, j). For example, the sequences 11232, 33141 are isomorphic. We investigate the maximum size of a labeled (rooted) tree with each vertex labeled by one of n labels in such a way that, besides some technical conditions, the sequence of labels along any path (starting from the root) contains no subsequence isomorphic to a fixed forbidden sequence u.We study two models of such labeled trees. Each of the models is known to be essentially equivalent also to other models. The labeled paths in a special case of one of our models correspond to classical Davenport–Schinzel sequences.We investigate, in particular, for which sequences u the labeled tree has at most O(n) vertices. In both models, we answer this question for any forbidden sequence u over a two-element alphabet and also for a large class of other sequences u.* This research was partially supported by Charles University grants No. 99/158 and 99/159 and by Czech Republic Grant GAR 201/99/0242. Supported by project LN00A056 of The Ministry of Education of the Czech Republic.     

Stochastic Ordering of Infinite Geometric Galton–Watson Trees

We consider Galton–Watson trees with Geom\((p)\) offspring distribution. We let \(T_{\infty }(p)\) denote such a tree conditioned on being infinite. We prove that for any \(1/2\le p_1 <p_2 \le 1\), there exists a coupling between \(T_{\infty }(p_1)\) and \(T_{\infty }(p_2)\) such that \({\mathbb {P}}(T_{\infty }(p_1) \subseteq T_{\infty }(p_2))=1\).     

Trees, Valuations and the Green–Lazarsfeld Set

We study the Green–Lazarsfeld set from the point of view of geometric group theory and compare it with the Bieri–Neumann–Strebel invariant. Applications to the study of fundamental groups of K?hler manifolds are given. Received: March 2007 Revised: June 2007 Accepted: July 2007     

Conditioning Galton–Watson Trees on Large Maximal Outdegree

We propose a new way to condition random trees, that is, conditioning random trees to have large maximal outdegree. Under this conditioning, we show that conditioned critical Galton–Watson trees converge locally to size-biased trees with a unique infinite spine. For the subcritical case, we obtain the local convergence to size-biased trees with a unique infinite node. We also study the tail of the maximal outdegree of subcritical Galton–Watson trees, which is essential for the proof of the local convergence.     

Baum–Connes Conjecture and Group Actions on Trees

We check, that the Baum–Connes conjecture with coefficients, for groups acting on oriented trees, is true if and only if it is true for the stabilizer groups of the vertices.     

Speed of Vertex-Reinforced Jump Process on Galton–Watson Trees

We give an alternative proof of the fact that the vertex-reinforced jump process on Galton–Watson tree has a phase transition between recurrence and transience as a function of \(c\), the initial local time, see Basdevant et al. (Ann Appl Probab 22(4):1728–1743, 2012). Further, applying techniques in Aidékon (Probab Theory Relat Fields 142(3–4):525–559, 2008), we show a phase transition between positive speed and null speed for the associated discrete-time process in the transient regime.     

Critical Multi-type Galton–Watson Trees Conditioned to be Large

Under minimal condition, we prove the local convergence of a critical multi-type Galton–Watson tree conditioned on having a large total progeny by types toward a multi-type Kesten’s tree. We obtain the result by generalizing Neveu’s strong ratio limit theorem for aperiodic random walks on \(\mathbb {Z}^d\).     

The Baum–Connes Conjecture and Discrete Group Actions on Trees

We introduce a property (BC) for discrete groups, which we prove to imply the Baum–Connes conjecture with coefficients and the K-amenability of the group. Then, we show that if is a discrete group which acts on a tree X such that X/ is compact, and the stabilizers of the vertices and the stabilizers of the edges satisfy (BC), then itself satisfies (BC) Finally, we indicate a couple of applications.     

Predator–Prey Dynamics on Infinite Trees: A Branching Random Walk Approach

We are interested in predator–prey dynamics on infinite trees, which can informally be seen as particular two-type branching processes where individuals may die (or be infected) only after their parent dies (or is infected). We study two types of such dynamics: the chase–escape process, introduced by Kordzakhia with a variant by Bordenave who sees it as a rumor propagation model, and the birth-and-assassination process, introduced by Aldous and Krebs. We exhibit a coupling between these processes and branching random walks killed at the origin. This sheds new light on the chase–escape and birth-and-assassination processes, which allows us to recover by probabilistic means previously known results and also to obtain new results. For instance, we find the asymptotic behavior of the tail of the number of infected individuals in both the subcritical and critical regimes for the chase–escape process and show that the birth-and-assassination process ends almost surely at criticality.     

Local Convergence of Large Critical Multi-type Galton–Watson Trees and Applications to Random Maps

We show that large critical multi-type Galton–Watson trees, when conditioned to be large, converge locally in distribution to an infinite tree which is analogous to Kesten’s infinite monotype Galton–Watson tree. This is proven when we condition on the number of vertices of one fixed type, and with an extra technical assumption if we count at least two types. We then apply these results to study local limits of random planar maps, showing that large critical Boltzmann-distributed random maps converge in distribution to an infinite map.     

Chains and Trees: ‘Strong’–‘Weak’ Order in Job Scheduling

We present a summary of recent NP-hardness and polynomial time solvability results for the distinction between strong and weak precedence for chains and trees in scheduling. We distinguish between chains and proper trees which are not chains, and demonstrate that the strong-weak precedence distinction for chains is not inclusive with regards to NP-hardness, and conjecture that the same holds for strong-weak tree precedence. The objective is to show that different interpretations for chain and tree order relations in scheduling might have far reaching computational implications.     

KKM—A Topological Approach For Trees

The Knaster–Kuratowski–Mazurkiewicz (KKM) theorem is a powerful tool in many areas of mathematics. In this paper we introduce a version of the KKM theorem for trees and use it to prove several combinatorial theorems.A 2-tree hypergraph is a family of nonempty subsets of T R (where T and R are trees), each of which has a connected intersection with T and with R. A homogeneous 2-tree hypergraph is a family of subsets of T each of which is the union of two connected sets.For each such hypergraph H we denote by (H) the minimal cardinality of a set intersecting all sets in the hypergraph and by (H) the maximal number of disjoint sets in it.In this paper we prove that in a 2-tree hypergraph (H)2(H) and in a homogeneous 2-tree hypergraph (H)3(H). This improves the result of Alon [3], that (H)8(H) in both cases.Similar results are proved for d-tree hypergraphs and homogeneous d-tree hypergraphs, which are defined in a similar way. All the results improve the results of Alon [3] and generalize the results of Kaiser [1] for intervals.     

Trees and ultrametric Möbius structures

We define the concept of an ultrametric Möbius space (Z,M) and show that the boundary at infinity of a nonelementary geodesically complete tree is naturally an ultrametric Möbius space. In addition, we construct to a given ultrametric Möbius space (Z,M) a nonelementary geodesically complete tree, unique up to isometry, with (Z,M) being its boundary at infinity. This yields a one-to-one correspondence.     

Entropy Theorem for Random Fields on Trees

We study the entropy theorem or the asymptotic equipartition property (AEP)for random fields on bomogeneous trees.A tree is a graph which is connected and contains no circuits. We discuss mainlya homogeneous tree T on which each vertex has N neighboring vertices. T is bipartitegraph because we can partition its vertex set into two equivalence classes, where α～β     

Typical Behavior of the Harmonic Measure in Critical Galton–Watson Trees with Infinite Variance Offspring Distribution

We study the typical behavior of the harmonic measure in large critical Galton–Watson trees whose offspring distribution is in the domain of attraction of a stable distribution with index \(\alpha \in (1,2]\). Let \(\mu _n\) denote the hitting distribution of height n by simple random walk on the critical Galton–Watson tree conditioned on non-extinction at generation n. We extend the results of Lin (Typical behavior of the harmonic measure in critical Galton–Watson trees, arXiv:1502.05584, 2015) to prove that, with high probability, the mass of the harmonic measure \(\mu _n\) carried by a random vertex uniformly chosen from height n is approximately equal to \(n^{-\lambda _\alpha }\), where the constant \(\lambda _\alpha >\frac{1}{\alpha -1}\) depends only on the index \(\alpha \). In the analogous continuous model, this constant \(\lambda _\alpha \) turns out to be the typical local dimension of the continuous harmonic measure. Using an explicit formula for \(\lambda _\alpha \), we are able to show that \(\lambda _\alpha \) decreases with respect to \(\alpha \in (1,2]\), and it goes to infinity at the same speed as \((\alpha -1)^{-2}\) when \(\alpha \) approaches 1.     

A Graceful Algorithm of a Class of Trees

Let T be a tree with v vertices. It is said to be graceful if we can label the vertices with numbers 1,2,……,v in such a manner that the differences of any two adjacent vertices will again form the set {1,2,…,v-1}.Ringel conjectured, in1963, that every tree has a such labelling [1]. Ringel's conjecture remains unsettled. In this article, we shall investigate a class of graceful trees. Definition The,T_λ~((n)) is a tree with v_n vertices. Its vertices are v_i(j=0,1,…,n+1);v_(?)(j_o=1,2,…,n;j_1=1,2,…,k_1;……; j=1,2,…,k,≤λ), where λ,n,k_1,     

Trees and tensors on Kähler manifolds

We present an organized method to convert between partial derivatives of metrics (functions) and covariant derivatives of curvature tensors (functions) on Kähler manifolds. Basically, it reduces the highly recursive computation in tensor calculus to the enumeration of certain trees with external legs.     

Steiner Minimal Trees in Rectilinear and Octilinear Planes

This paper considers the Steiner Minimal Tree （SMT） problem in the rectilinear and octilinear planes. The study is motivated by the physical design of VLSI： The rectilinear case corresponds to the currently used M-architecture, which uses either horizontal or vertical routing, while the octilinear case corresponds to a new routing technique, X-architecture, that is based on the pervasive use of diagonal directions. The experimental studies show that the X-architecture demonstrates a length reduction of more than 10-20%. In this paper, we make a theoretical study on the lengths of SMTs in these two planes. Our mathematical analysis confirms that the length reduction is significant as the previous experimental studies claimed, but the reduction for three points is not as significant as for two points. We also obtain the lower and upper bounds on the expected lengths of SMTs in these two planes for arbitrary number of points.     

“Trees under attack”: a Ray–Knight representation of Feller’s branching diffusion with logistic growth

We obtain a representation of Feller’s branching diffusion with logistic growth in terms of the local times of a reflected Brownian motion H with a drift that is affine linear in the local time accumulated by H at its current level. As in the classical Ray–Knight representation, the excursions of H are the exploration paths of the trees of descendants of the ancestors at time t = 0, and the local time of H at height t measures the population size at time t. We cope with the dependence in the reproduction by introducing a pecking order of individuals: an individual explored at time s and living at time t = H _s is prone to be killed by any of its contemporaneans that have been explored so far. The proof of our main result relies on approximating H with a sequence of Harris paths H ^N which figure in a Ray–Knight representation of the total mass of a branching particle system. We obtain a suitable joint convergence of H ^N together with its local times and with the Girsanov densities that introduce the dependence in the reproduction.