Exact stability for Turán’s Theorem
- Mathematical Institute
- University of Oxford
- ORCID iD: 0000-0002-3975-0787
- Mathematical Institute
- University of Oxford
- Mathematical Institute
- University of Oxford
Editorial introduction
Mantel’s Theorem and Turán’s Theorem are among the most classical results in extremal graph theory. Mantel’s Theorem, proven in 1907 and so perhaps the oldest result in extremal graph theory, asserts that the maximum number of edges of an n-vertex graph that does not contain the complete graph of order three is at most ⌊n2/4⌋. This bound is the best possible as witnessed by the complete bipartite graph with parts consisting of ⌊n/2⌋ and ⌈n/2⌉ vertices. In 1941, Turán generalized this statement to graphs not containing the complete graph of order r+1: the maximum number of edges of an n-vertex graph that does not contain Kr+1 is attained by the complete r-partite graph with parts whose sizes differ by at most one, and this graph is the unique n-vertex graph with this number of edges that does not contain Kr+1. For general graphs G, the maximum number of edges of an n-vertex graph not containing G is (χ(G)−2χ(G)−1+o(1))(n2), as shown by Erdős and Stone, and Erdős and Simonovits.
Let tr(n) be the maximum number of edges of an n-vertex graph that does not contain Kr+1. As the complete r-partite n-vertex graph with parts whose sizes differ by at most one is the unique n-vertex graph with tr(n) edges not containing Kr+1, it is natural to ask about the structure of n-vertex graphs not containing Kr+1 with the number of edges close to tr(n): do such graphs need to be r-partite, and if not, how close must they be to an r-partite graph? An exact answer to the first part of the question is known from the early 1980s: every n-vertex graph that does not contain Kr+1 and has at least tr(n)−⌊n/r⌋+2 edges is r-partite. In the case of r=2, Erdős, Győri and Simonovits showed in the early 1990s that among all n-vertex graphs with m≥t2(n)−n2/20 edges that do not contain K3, the graph farthest from being bipartite (in terms of maximizing the number of edges needed to be removed to make it bipartite) is a suitable blow up of the cycle of length five. This paper generalizes this result to all values of r: there exists δr>0 such that among all n-vertex graphs with m≥tr(n)−δrn2 edges that do not contain Kr+1, the graph farthest from being r-partite can be obtained by replacing two parts of the complete r-partite graph with a blow up of the cycle of length five.