Concentration of the maximum size of an induced subtree in moderately sparse random graphs

2025/06/03 by Juan Carlos Buitrago Oropeza, Oropeza, Juan Carlos Buitrago
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Graph theory and applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2506.02801

openalex publication_date 2025/06/03 · openalex created_date 2025/10/14 · openalex updated_date 2026/07/28

Abstract

Kamaldinov, Skorkin, and Zhukovskii proved that the maximum size of an induced subtree in the binomial random graph G(n,p) is concentrated at two consecutive points, whenever p∈(0,1) is a constant. Using improved bounds on the second moment of the number of induced subtrees, we show that the same result holds when n^{-(e-2)/(3e-2)+ε}≤ p=o(1).

Citations

• Maximum induced trees and forests of bounded degree in random graphs
• Two-Point Concentration of the Domination Number of Random Graphs
• The maximum size of an induced forest in the binomial random graph
• Two-Point Concentration of the Independence Number of the Random Graph
• The largest hole in sparse random graphs
• Note on induced paths in sparse random graphs
• Maximum induced forests in random graphs
• Large induced matchings in random graphs
• Large induced trees in dense random graphs
• Maximum sparse induced subgraphs of the binomial random graph with given\n number of edges
• On the sizes of large subgraphs of the binomial random graph

Related

• Maximum sparse induced subgraphs of the binomial random graph with given\n number of edges
• On the sizes of large subgraphs of the binomial random graph
• Maximum induced forests in random graphs
• Maximum induced trees and forests of bounded degree in random graphs
• The maximum size of an induced forest in the binomial random graph