Uniform temporal trees
The paper introduces the notion of a uniform temporal tree. To define this, one starts from the infinite \(n\)-ary rooted tree and assigns a label to each edge that is uniformly distributed random variable on \([0,1]\), independently of any other edge. These labels induce labels on the vertices, where each non-root vertex inherits the label of the edge that is the nearest to the root. The root is assigned a label \(p\in (0,1]\). Then the vertices that are kept in the tree are those for which there is a decreasing (in terms of the values of the labels) path starting at the root. One can see that this random sub-tree is almost surely finite. The main results that are proved in this paper consider basic features of this random tree. In particular, a law of large numbers (as \(n\to \infty\)) is proved for the size of this random tree as well as its height. Furthermore, the depth of a uniformly selected vertex is also considered and a law of large numbers is proved for this random variable. Finally, the degree distribution is considered and a law of large numbers is obtained for the number of vertices of outdegree \(k\) for any fixed \(k\geq 0\).
- A converse to Scheffé's theorem
- Applications of the theory of records in the study of random trees
- Asymptotic degree distribution in random recursive trees
- Branching processes in the analysis of the heights of trees
- Chernoff's theorem in the branching random walk
- Depth of vertices with high degree in random recursive trees
- High degrees in random recursive trees
- scientific article; zbMATH DE number 3954145 (Why is no real title available?)
- Increasing paths in regular trees
- Long monotone trails in random edge-labellings of random graphs
- Minima in branching random walks
- Note on the heights of random recursive trees and random m‐ary search trees
- On the Altitude of Nodes in Random Trees
- Probability
- Random Trees
- Sharp Thresholds in Random Simple Temporal Graphs
- Sur un nouveau théorème-limite de la théorie des probabilités.
- Temporal network theory
- The first- and last-birth problems for a multitype age-dependent branching process
- The number of accessible paths in the hypercube
- The strong convergence of maximal degrees in uniform random recursive trees and dags
- Universal Limit Laws for Depths in Random Trees
- Wahrscheinlichkeitstheorie
This page was built for publication: Uniform temporal trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6873736)
