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

November 27, 2019
Dolgoprudny
MIPT

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

At the invitation of the Laboratory of Combinatorial and Geometric Structures and the PhysTech School of Applied Mathematics and Computer Science, István Tomon gave a talk on the conference "Combinatorics and Geometry Days I".

Abstract:

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.