Keevash–Saks–Sudakov–Verstraëte rainbow Turán conjecture for critical graphs

Let r3r\ge 3 and let HH be an rr-critical graph with hh edges. For a multiset of kk graphs on the common vertex set [n][n], write exk(n,H)\operatorname{ex}_k(n,H) for the maximum total number of edges among rainbow HH-free systems. Let Tr1(n)T_{r-1}(n) be the Turán graph and tr1(n)=Tr1(n)t_{r-1}(n)=|T_{r-1}(n)|. Also, tKnt\mathcal{K}_n and tKnt\overline{\mathcal{K}}_n denote multisets consisting of tt copies of KnK_n and Kn\overline{K}_n, respectively, while tTr1(n)t\mathcal{T}_{r-1}(n) denotes tt copies of Tr1(n)T_{r-1}(n).

Keevash–Saks–Sudakov–Verstraëte conjecture. Suppose khk\ge h and nn is sufficiently large. Then

exk(n,H)=max{ktr1(n),(h1)(n2)}.\operatorname{ex}_k(n,H)=\max\left\{k\,t_{r-1}(n),(h-1)\binom{n}{2}\right\}.

Moreover, (h1)Kn(kh+1)Kn (h-1)\mathcal{K}_n\cup(k-h+1)\overline{\mathcal{K}}_n and kTr1(n)k\mathcal{T}_{r-1}(n) are the only extremal structures when nn is sufficiently large.

The conjecture has been confirmed when r=3r=3 and when H=KrH=K_r, but remains open for general rr-critical graphs.

Sources & referencesView supporting material

Primary source

Yue Ma and Xinmin Hou, “Graphs without rainbow cliques of orders four and five”, arXiv:2306.12222 (2023).

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.