Turán number conjecture for Cartesian products of trees

From papers

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

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

The product TST\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.

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).

Solutions 0

No solutions have been posted yet.