On the independence number of some random trees

DOI10.1214/20-ECP345zbMATH Open1468.60015arXiv2003.08712MaRDI QIDQ2201542FDOQ2201542

Svante Janson

Publication date: 29 September 2020

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

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.

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

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
• 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

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)

Cites Work

• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• Asymptotic fringe distributions for general families of random trees
• The growth and composition of branching populations
• Title not available (Why is that?)
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• The stable doubly infinite pedigree process of supercritical branching populations
• Title not available (Why is that?)
• Packing and covering constants for certain families of trees. I
• Packing and Covering Constants for Certain Families of Trees. II
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lectures on the Poisson Process
• Title not available (Why is that?)
• Analysis of three graph parameters for random trees

Cited In (8)

• Title not available (Why is that?)
• Title not available (Why is that?)
• On generalized independent subsets of trees
• On the bipartition numbers of random trees. II
• An introduction to random trees
• On the asymptotic behavior of the independence number of a random \((n,n)\)-tree
• On the distribution of eigenvalues of increasing trees
• THE EXPECTED INDEPENDENT DOMINATION NUMBER OF RANDOM DIRECTED ROOTED 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)