Turán number conjecture for Cartesian products of trees

About 4 years old · traced to

Let TT and SS be trees, each with at least one edge, and let T□ST\Box S denote their Cartesian product. For a positive integer nn, let ex(n,T□S)\mathrm{ex}(n,T\Box S) be the maximum number of edges in a (T□S)(T\Box S)-free graph on nn vertices. Cartesian-product conjecture. There exist positive real numbers cc and CC such that

cn3/2≤ex(n,T□S)≤Cn3/2.cn^{3/2}\leq \mathrm{ex}(n,T\Box S)\leq Cn^{3/2}.

The product T□ST\Box S is 22-degenerate, and the conjecture is motivated in part by Erdős's conjecture on Turán numbers of degenerate bipartite graphs. Its general validity remains open.

References

Primary source

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

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.