Stability of the independence number of G(n, r, 1) graphs

2025/10/21 by M.M. Koshelev, М.А. Koshelev, Koshelev, M.
Mathematics · Computer Science · #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2510.18850

Abstract

In this paper we obtain the stability theorem for the independence number of G(n, r, 1) graphs. This result was previously stated in the paper of M. Pyaderkin but the proof there was incorrect. We introduce the correct proof of the key lemma and thus finally complete the proof of this theorem.

Citations

• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

Related

• A sharp upper bound for the independence number
• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree
• On the stability of some Erdős--Ko--Rado type results
• Sharp lower bounds and extremal graphs for the generalized k-independence number
• The Critical Independence Number and an Independence Decomposition