Asymptotic extremal conjecture for powers of graphs with bounded matching number

About 2 years old · traced to

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 (k−1)(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 k−1k-1. Asymptotic extremal conjecture. If k>rk>r, there is an independent set UU of GG such that G0=G−UG_0=G-U has chromatic number k−1k-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)(nr−1)+(s−m′(G)+1)(k−2r−1)(nk−2)r−1+o(nr−1).\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.

References

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.