Turán bound conjecture for higher-dimensional grids

From papers

For positive integers dd and tt, let Ft(d)F_t^{(d)} be the dd-dimensional grid with vertex set [t]d[t]^d, where two vertices are adjacent when they differ by exactly one in exactly one coordinate. For a positive integer nn, let ex(n,Ft(d))\mathrm{ex}(n,F_t^{(d)}) denote the maximum number of edges in an Ft(d)F_t^{(d)}-free graph on nn vertices. Higher-dimensional grid conjecture. There is a constant CC such that

ex(n,Ft(d))Cn21/d.\mathrm{ex}(n,F_t^{(d)})\leq Cn^{2-1/d}.

This is suggested by the fact that Ft(d)F_t^{(d)} is dd-degenerate and would extend the paper's two-dimensional grid result. The conjecture remains open in general.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Domagoj Bradač, Oliver Janzer, Benny Sudakov and István Tomon, “The Turán number of the grid”, arXiv:2203.05485 (2022).

Additional references

3 papers in this index state this conjecture (2019–2022). The statement above is taken from the most recent of them; the others are arXiv:2112.13119, arXiv:1905.01685.

Solutions 0

No solutions have been posted yet.