Department of

Mathematics


Seminar Calendar
for events the day of Tuesday, April 14, 2020.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
      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

2:00 pm in Zoom,Tuesday, April 14, 2020

On stability of triangle-free graphs

Felix Clemen (University of Illinois, Urbana-Champaign)

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.