The Turán number of the grid

2022/03/10 by Bradač, Domagoj, Janzer, Oliver, Sudakov, Benny +1 · 2 citations
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2203.05485

Abstract

For a positive integer t, let F_t denote the graph of the t× 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. One of the interesting ingredients of our proof is a novel way of using the tensor power trick.

Cited by

• Ramsey numbers of digraphs with local edge structure
• Spectral extremal problem for the odd prism

Related

• The Turán number of the Cartesian product of graphs
• Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3
• Regular Turán numbers
• Many Turan exponents via subdivisions
• A construction for bipatite Turán numbers