Campus Units

Mathematics

Document Type

Article

Publication Version

Submitted Manuscript

Publication Date

9-30-2019

Journal or Book Title

arxiv

Abstract

The Erdos–Simonovits stability theorem states that for all epsilon > 0 there exists alpha > 0 such that if G is a Kr+1-free graph on n vertices with e(G) > ex(n, Kr+1) − alpha n2, then one can remove epsilon n2 edges from G to obtain an r-partite graph. Furedi gave a short proof that one can choose alpha = epsilon. We give a bound for the relationship of alpha and epsilon which is asymptotically sharp as epsilon right arrow 0.

Comments

This pre-print is made available through arixiv: https://arxiv.org/abs/1910.00028.

Copyright Owner

The Authors

Language

en

File Format

application/pdf

Share

COinS