On the independence number of some random trees

DOI10.1214/20-ECP345MaRDI QIDQ2201542zbMATHFDO

Authors Svante Janson

Publication date 29 September 2020

Published in Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

independence numberrandom treesrandom recursive treebinary search treeCrump-Mode-Jagers branching process

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial probability (60C05)

Abstract: We show that for many models of random trees, the independence number divided by the size converges almost surely to a constant as the size grows to infinity; the trees that we consider include random recursive trees, binary and $m$-ary search trees, preferential attachment trees, and others. The limiting constant is computed, analytically or numerically, for several examples. The method is based on Crump-Mode-Jagers branching processes.

Recommendations

• On the asymptotic behavior of the independence number of a random \((n,n)\)-tree
• On the number of independent sets in a tree
• scientific article; zbMATH DE number 888944
• On the \(k\)-component independence number of a tree
• On the spectral radius of trees with given independence number
• On the number of independent sets in the trees of a fixed diameter
• scientific article; zbMATH DE number 179305
• scientific article; zbMATH DE number 1792637
• On the number of independent subsets in trees with restricted degrees
• THE EXPECTED INDEPENDENT DOMINATION NUMBER OF RANDOM DIRECTED ROOTED TREES

Cites work

• scientific article; zbMATH DE number 4053643 (Why is no real title available?)
• scientific article; zbMATH DE number 3504991 (Why is no real title available?)
• scientific article; zbMATH DE number 3577214 (Why is no real title available?)
• scientific article; zbMATH DE number 3415878 (Why is no real title available?)
• Analysis of three graph parameters for random trees
• Asymptotic fringe distributions for general families of random trees
• Emergence of Scaling in Random Networks
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• Introduction to chemical graph theory
• Lectures on the Poisson Process
• Packing and Covering Constants for Certain Families of Trees. II
• Packing and covering constants for certain families of trees. I
• Random graphs and complex networks. Volume 1
• The growth and composition of branching populations
• The stable doubly infinite pedigree process of supercritical branching populations

Cited in

(19)

• scientific article; zbMATH DE number 1792637 (Why is no real title available?)
• Persisting randomness in randomly growing discrete structures: graphs and search trees
• THE EXPECTED INDEPENDENT DOMINATION NUMBER OF RANDOM DIRECTED ROOTED TREES
• On the distribution of eigenvalues of increasing trees
• Surprising identities for the greedy independent set on Cayley trees
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• A note on the independence number, domination number and related parameters of random binary search trees and random recursive trees
• Random recursive trees and preferential attachment trees are random split trees
• Some probabilistic trees with algebraic roots
• Analysis of three graph parameters for random trees
• An introduction to random trees
• Persisting randomness in randomly growing discrete structures: graphs and search trees
• Pick two points in a tree
• On the independent set sequence of a tree
• On the asymptotic behavior of the independence number of a random \((n,n)\)-tree
• On the number of transversals in random trees
• scientific article; zbMATH DE number 32144 (Why is no real title available?)
• On the bipartition numbers of random trees. II
• On generalized independent subsets of trees

This page was built for publication: On the independence number of some random trees

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