The containment profile of hyper-recursive trees

DOI10.1017/JPR.2021.50MaRDI QIDQ5067223zbMATH OpenOpenAlexFDO

Authors Joshua Sparks, Srinivasan Balaji, Hosam M. Mahmoud

Publication date 1 April 2022

Published in Journal of Applied Probability (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphlimit lawmartingalephase transition

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Central limit and other weak theorems (60F05) Stochastic network models in operations research (90B15)

Abstract: We investigate vertex levels of containment in a random hypergraph grown in the spirit of a recursive tree. We consider a local profile tracking the evolution of the containment of a particular vertex over time, and a global profile concerned about counts of the number of vertices of a particular containment level. For the local containment profile, we obtain the exact mean, variance and probability distribution in terms of standard combinatorial quantities like generalized harmonic numbers and Stirling numbers of the first kind. Asymptotically, we observe phases: the early vertices have an asymptotically normal distribution, intermediate vertices have a Poisson distribution, and late vertices have a degenerate distribution. As for the global containment profile, we establish an asymptotically normal distribution for the number of vertices at the smallest containment level as well as their covariances with the number of vertices at the second smallest containment level and the variances of these numbers.

Recommendations

• The degree profile in some classes of random graphs that generalize recursive trees
• Asymptotic degree distribution in random recursive trees
• Random recursive hypergraphs
• Profiles of random trees: Plane-oriented recursive trees
• Profiles of random trees: plane-oriented recursive trees

Cites work

• Algorithmics of nonuniformity: tools and paradigms
• Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees
• Fundamentals of Stein's method
• scientific article; zbMATH DE number 4007433 (Why is no real title available?)
• scientific article; zbMATH DE number 3723610 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1409903 (Why is no real title available?)
• Introduction to Random Graphs
• Local and global degree profiles of randomly grown self-similar hooking networks under uniform and preferential attachment
• Phase Changes in Subtree Varieties in Random Recursive and Binary Search Trees
• Probability with Martingales
• Probability: a graduate course
• Random Trees
• The asymptotic expansion of a ratio of gamma functions
• Trees grown under young-age preferential attachment

Cited in

(4)

• Random recursive hypergraphs
• On several properties of a class of hybrid recursive trees
• Applying affine urn models to the global profile of hyperrecursive trees
• On affine multicolor urns grown under multiple drawing

This page was built for publication: The containment profile of hyper-recursive trees

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