Two-Point Concentration of the Independence Number of the Random Graph

2022/07/30 by Tom Bohman, Bohman, Tom, Jakob Hofstad +1 · 1 citation
Computer Science · Mathematics · #05C80 #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2208.00117

openalex publication_date 2022/07/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that the independence number of G_n,p is concentrated on two values if n^{-2/3+ ε} < p ≤ 1. This result is roughly best possible as an argument of Sah and Sawhney shows that the independence number is not, in general, concentrated on 2 values for p = o ( (log(n)/n)^2/3 ). The extent of concentration of the independence number of G_n,p for ω(1/n)

Cited by

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

Related

• A note on Two-Point Concentration of the Independence Number of G_n,m
• Two-Point Concentration of the Domination Number of Random Graphs
• On the Concentration of the Domination Number of the Random Graph
• The maximum size of an induced forest in the binomial random graph
• Concentration of the maximum size of an induced subtree in moderately sparse random graphs