Turán bound conjecture for higher-dimensional grids

About 7 years old · traced to

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))≤Cn2−1/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.

References

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.

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.