Asymptotic extremal conjecture for powers of graphs with bounded matching number

Let GG be a graph with chromatic number kk, let GrG^r denote its rr-uniform power, and let m(G)m'(G) be the number of edges between a specified pair of color classes of a (k1)(k-1)-coloring of the graph obtained after deleting an independent set UU. Assume that deleting UU yields a graph G0G_0 of chromatic number k1k-1. Asymptotic extremal conjecture. If k>rk>r, there is an independent set UU of GG such that G0=GUG_0=G-U has chromatic number k1k-1, two color classes of G0G_0 have m(G)m'(G) edges between them, and ss is sufficiently large, then

ex(n,{Gr,Ms+1r})=(m(G)1)(nr1)+(sm(G)+1)(k2r1)(nk2)r1+o(nr1).\operatorname{ex}(n,\{G^r,M^r_{s+1}\})=(m'(G)-1)\binom{n}{r-1}+(s-m'(G)+1)\binom{k-2}{r-1}\left(\frac{n}{k-2}\right)^{r-1}+o(n^{r-1}).

The conjecture asserts that the construction described in the source gives the asymptotically correct extremal value when the matching bound is sufficiently large; the source presents this as a belief and does not provide a resolution.

Sources & referencesView supporting material

Primary source

Dániel Gerbner, Casey Tompkins and Junpeng Zhou, “On hypergraph Turán problems with bounded matching number”, arXiv:2410.07455 (2024).

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.