Broadcasting‐induced colorings of preferential attachment trees

DOI10.1002/RSA.21142MaRDI QIDQ6076722zbMATH OpenFDO

Authors

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.15050

zbMATH Keywords

generating functionsbroadcastingpercolationpreferential attachmentrandom treesPólya urns

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Exact enumeration problems, generating functions (05A15)

Abstract: In this work we consider random two-colourings of random linear preferential attachment trees, which includes random recursive trees, random plane-oriented recursive trees, random binary search trees, and a class of random $d$-ary trees. The random colouring is defined by assigning the root of the tree the colour red or blue with equal probability, and all other vertices are assigned the colour of their parent with probability $p$ and the other colour otherwise. These colourings have been previously studied in other contexts, including Ising models and broadcasting, and can be considered as generalizations of bond percolation. With the help of P'olya urns, we prove limiting distributions, after proper rescalings, for the number of vertices of each colour, the number of monochromatic subtrees of each colour, as well as the number of leaves and fringe subtrees with two-colourings. Using methods from analytic combinatorics, we also provide precise descriptions of the limiting distribution after proper rescaling of the size of the root cluster; the largest monochromatic subtree containing the root. The description of the limiting distributions extends previous work on bond percolation in random preferential attachment trees.

Recommendations

• scientific article; zbMATH DE number 7703235
• Broadcasting on random recursive trees
• Reconstruction/non-reconstruction thresholds for colourings of general Galton-Watson trees
• Enumeration of equicolorable trees

Cites work

• scientific article; zbMATH DE number 4053643 (Why is no real title available?)
• scientific article; zbMATH DE number 2151257 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• An impossibility result for reconstruction in the degree-corrected stochastic block model
• Analytic combinatorics
• Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
• Asymptotic degree distribution in random recursive trees
• Belief propagation, robust reconstruction and optimal recovery of block models
• Broadcasting on random recursive trees
• Broadcasting on trees and the Ising model.
• Emergence of Scaling in Random Networks
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• New insights on the reinforced elephant random walk using a martingale approach
• Note on the heights of random recursive trees and random m‐ary search trees
• On a class of random walks with reinforced memory
• On the number of terminal vertices in certain random trees with an application to stemma construction in philology
• Probability on trees and networks
• Probability: a graduate course
• Progress in high-dimensional percolation and random graphs
• Random Trees
• Sur les séries de Taylor n'ayant que des singularites algebrico- logarithmiques sur leur cercle de convergence
• The Mittag-Leffler process and a scaling limit for the block counting process of the Bolthausen-Sznitman coalescent
• The Multiplicative Process
• The degree sequence of a scale-free random graph process
• The fragmentation process of an infinite recursive tree and Ornstein-Uhlenbeck type processes
• The shark random swim. (Lévy flight with memory)
• The total progeny in a branching process and a related random walk

This page was built for publication: Broadcasting‐induced colorings of preferential attachment trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6076722)