Download as iCal file

Discrete Math

The Turán number of the grid

Domogoj Brada? (ETH Zurich)

Location:  Hill Center 705
Date & time: Monday, 06 February 2023 at 2:00PM - 3:00PM

Abstract: For a positive integer t, let F_t denote the graph of the t by t grid. Motivated by a 50-year-old conjecture of Erd?s about Turán numbers of r-degenerate graphs, we prove that there exists a constant C=C(t) such that ex(n,F_t) < Cn^{3/2}. This bound is tight up to the value of C. Our original proof of this result relied on an intricate argument using the tensor power trick. In this talk I will present a simplified version of the proof. Based on joint work with Oliver Janzer, Benny Sudakov and István Tomon.