Talk by István Tomon “Turan number of bipartite graphs with no complete bipartite graph” video

November 27, 2019

István Tomon "Turán number of bipartite graphs with no $K_{t,t}$"

István Tomon gave a talk on the conference "Combinatorics and Geometry Days I".


The extremal number of a graph $H$, denoted by $\mbox{ex}(n,H)$, is the maximum number of edges in a graph on $n$ vertices that does not contain $H$. The well known Kővári-Sós-Turán theorem says that for a complete bipartite graph with parts of size $t\leq s$ the extremal number is $\mbox{ex}(K_{s,t})=O(n^{2-1/t})$. A celebrated generalization of this result, proved by Füredi and Alon-Krivelevich-Sudakov is that if $H$ is a bipartite graph such that every vertex in one part has degree at most $t$, then $\mbox{ex}(K_{s,t})=O(n^{2-1/t})$ as well. In this talk, I will show that this bound can be improved if we also assume that $H$ does not contain $K_{t,t}$, which settles a conjecture of Conlon, Lee and Janzer.

Find more talks by István Tomon on this page.