Dynamical Pruning of Rooted Trees with Applications to 1-D Ballistic Annihilation
- PDF / 1,442,152 Bytes
- 55 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 177 Views
Dynamical Pruning of Rooted Trees with Applications to 1-D Ballistic Annihilation Yevgeniy Kovchegov1
· Ilya Zaliapin2
Received: 11 October 2019 / Accepted: 15 June 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We introduce generalized dynamical pruning on rooted binary trees with edge lengths that encompasses a number of discrete and continuous pruning operations, including the tree erasure and Horton pruning. The pruning removes parts of a tree T , starting from the leaves, according to a pruning function defined on descendant subtrees within T . We prove the invariance of critical binary Galton–Watson tree with exponential edge lengths with respect to the generalized dynamical pruning for an arbitrary admissible pruning function. These results facilitate analysis of the continuum 1-D ballistic annihilation model A + A → ∅ for a constant particle density and initial velocity that alternates between the values of ±1. We show that the model’s shock wave is isometric to the level set tree of the potential function, and the model evolution is equivalent to the generalized dynamical pruning of the shock wave tree. Keywords Random self-similar trees · Galton–Watson process · Ballistic annihilation · Chemical kinetics
1 Introduction Pruning of tree graphs is a natural operation that induces a contracting map [28] on a suitable space of trees, with the empty tree φ as the fixed point. Examples of prunings studied in probability literature include erasure from leaves at unit speed [17,21,38], cutting the leaves [14,31,33], and eliminating nodes/edges at random [1,5]. A recent survey of random tree measures invariant with respect to cutting the leaves is given in [34].
Communicated by Pablo A Ferrari.
B
Ilya Zaliapin [email protected] Yevgeniy Kovchegov [email protected]
1
Department of Mathematics, Oregon State University, Corvallis, OR, USA
2
Department of Mathematics and Statistics, University of Nevada, Reno, NV, USA
123
Y. Kovchegov, I. Zaliapin
1.1 Generalized Dynamical Pruning We consider here the erasure of a tree from the leaves down at a non-constant tree-dependent rate. Specifically, we introduce generalized dynamical pruning St (ϕ, T ) of a rooted tree T that eliminates all subtrees Δx,T (defined as the points descendant to point x in T ) for which the value of a function ϕ(Δx,T ) is below t (see Sect. 3 for a formal definition). The generalized dynamical pruning encompasses a number of discrete and continuous pruning operations, depending on the choice of function ϕ. For instance, the tree erasure from leaves at unit speed [17,21,38] corresponds to the pruning function ϕ(T ) equal to the height of T ; and the Horton pruning [14,33] corresponds to ϕ(T ) equal to the Horton–Strahler order of T . For most selections of ϕ(T ), the map induced by the generalized dynamical pruning does not have a semigroup property, which distinguishes it from the operations studied in the literature. In Sect. 4.3, Theorem 2 we establish invariance of the space of critical bi
Data Loading...
