Making Kr+1-free graphs r-partite. (10th July 2021)

• Record Type: Journal Article
• Authors: Balogh, József; Clemen, Felix Christian; Lavrov, Mikhail; Lidický, Bernard; Pfender, Florian
• Is Part Of: Combinatorics, probability and computing. Volume 30:Number 4(2021)
• Page Start: 609
• Page End: 618
• Publication Date: 2021-07-10
• Subjects: 05C35; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548320000590
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract: The Erdős–Simonovits stability theorem states that for all ε > 0 there exists α > 0 such that if G is a K r+ 1 -free graph on n vertices with e ( G ) > ex( n, K r +1 )– α n 2, then one can remove εn 2 edges from G to obtain an r -partite graph. Füredi gave a short proof that one can choose α = ε . We give a bound for the relationship of α and ε which is asymptotically sharp as ε → 0.