Department of

March 2020 April 2020 May 2020 Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa Su Mo Tu We Th Fr Sa 1 2 3 4 5 6 7 1 2 3 4 1 2 8 9 10 11 12 13 14 5 6 7 8 9 10 11 3 4 5 6 7 8 9 15 16 17 18 19 20 21 12 13 14 15 16 17 18 10 11 12 13 14 15 16 22 23 24 25 26 27 28 19 20 21 22 23 24 25 17 18 19 20 21 22 23 29 30 31 26 27 28 29 30 24 25 26 27 28 29 30 31

Tuesday, April 14, 2020

**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 Turan number $\mathrm{ex}(n,K_{r+1})$. The Erdos-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) > \mathrm{ex}(n,K_{r+1}) - \alpha n^2$, then one can remove $\epsilon n^2$ 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$ goes to $0$. This is joint work with Jozsef Balogh, Mikhail Lavrov, Bernard Lidicky and Florian Pfender.

In the second part of the talk we study graphs with number of edges slightly above the Turan number $\mathrm{ex}(n,K_{r+1})$. What is the minimum number of cliques of such graphs? Lovasz and Simonovits proved that an n-vertex graph with $e(G) > \mathrm{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 Jozsef Balogh.

Please E-mail SEnglish@illinois.edu for the Zoom ID and password.