Speaker: Felix Christian Clemen
Title: On stability of triangle-free graphs
Abstract:
In the first part of this talk we take a look at the structure of K_{r+1}-free graphs with number of edges slightly below the Turán number ex(n,K_{r+1}). The Erdős-Simonovits stability theorem states that for all epsilon>0 there exists alpha>0 such that if G is a K_{r+1}-free graph on n vertices with e(G) > ex(n,K_{r+1}) - alpha n^2, then one can remove epsilon n^2 edges from G to obtain an r-partite graph. Füredi 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 goes to 0. This is joint work with József Balogh, Mikhail Lavrov, Bernard Lidický and Florian Pfender.
> In the second part of the talk we study graphs with number of edges slightly above the Turán number ex(n,K_{r+1}). What is the minimum number of cliques of such graphs? Lovász and Simonovits' proved that an n-vertex graph with e(G) > ex(n,K_3) + t contains at least t n/2 triangles. Katona and Xiao considered the same problem under the additional condition that there are no s vertices covering all triangles. They settled the case t=1 and s=2. Solving their conjecture, we determine the minimum number of triangles for general s and t. Additionally, solving another conjecture of Katona and Xiao, we extend the theory for considering cliques instead of triangles. This is joint work with József Balogh.