The Turán number of the grid

DOI10.1112/BLMS.12721MaRDI QIDQ6176592zbMATH OpenFDO

Authors Domagoj Bradač, Oliver Janzer, Benny Sudakov, István Tomon

Publication date 23 August 2023

Published in Bulletin of the London Mathematical Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2203.05485

zbMATH Keywords

\(r\)-degenerate graphstensor power trick

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Extremal problems in graph theory (05C35)

Abstract: For a positive integer $t$, let $F_t$ denote the graph of the $timest$ grid. Motivated by a 50-year-old conjecture of ErdH{o}s about Tur'{a}n numbers of $r$-degenerate graphs, we prove that there exists a constant $C=C(t)$ such that $mathrmex(n,F_t)leqC{n}^{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.

Recommendations

• The Turán number of blow-ups of trees
• Extensions of extremal graph theory to grids
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Disproof of a Conjecture of Erdős and Simonovits on the Turán Number of Graphs with Minimum Degree 3
• On two Turán Numbers

Cites work

• A Holder Type Inequality for Symmetric Matrices with Nonnegative Entries
• Constructing dense grid-free linear 3-graphs
• scientific article; zbMATH DE number 3285073 (Why is no real title available?)
• scientific article; zbMATH DE number 3298603 (Why is no real title available?)
• scientific article; zbMATH DE number 3333193 (Why is no real title available?)
• Non-averaging subsets and non-vanishing transversals
• On a problem of K. Zarankiewicz
• On a Turán type problem of Erdős
• On the size-Ramsey number of grid graphs
• On the structure of linear graphs
• The history of degenerate (bipartite) extremal graph problems
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions
• Turán numbers of subdivided graphs
• Two approaches to Sidorenko's conjecture
• Uniform hypergraphs containing no grids

Cited in

(7)

• Extensions of extremal graph theory to grids
• The Rank-Width of the Square Grid
• Extremal graphs for the odd prism
• Bipartite Turán problems via graph gluing
• Spectral extremal problem for the odd prism
• Extremal number of graphs from geometric shapes
• Extremal number of graphs from geometric shapes (extended abstract)

This page was built for publication: The Turán number of the grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6176592)