Доклад Иштвана Томона «Turan number of bipartite graphs with no complete bipartite graph»

27 ноября, 2019
Долгопрудный
МФТИ

Иштван Томон "Turán number of bipartite graphs with no $K_{t,t}$"

27 ноября Иштван Томон выступил на конференции «Дни комбинаторики и геометрии I» с докладом Turán number of bipartite graphs with no $K_{t,t}$. Предлагаем вашему вниманию видеозапись доклада.

Аннотация:

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.