A note on Two-Point Concentration of the Independence Number of G_n,m

2024/10/07 by Tom Bohman, Bohman, Tom, Jakob Hofstad +1
Mathematics · #05C80 #60C05 #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Approximation and Integration #Meromorphic and Entire Functions #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.2410.05420

openalex publication_date 2024/10/07 · openalex created_date 2024/10/12 · openalex updated_date 2026/07/28

Abstract

We show that the independence number of G_n,m is concentrated on two values for n^{5/4+ ε} < m ≤ \binomn2. This result establishes a distinction between G_n,m and G_n,p with p = m/ \binomn2 in the regime n^{5/4 + ε} < m< n^4/3. In this regime the independence number of G_n,m is concentrated on two values while the independence number of G_n,p is not; indeed, for p in this regime variations in α( G_n,p) are determined by variations in the number of edges in G_n,p.

Related

• Two-Point Concentration of the Independence Number of the Random Graph
• Two-Point Concentration of the Domination Number of Random Graphs
• 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
• On the Concentration of the Domination Number of the Random Graph