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

About 3 years old · traced to

Let r≥3r\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 ex⁡k(n,H)\operatorname{ex}_k(n,H) for the maximum total number of edges among rainbow HH-free systems. Let Tr−1(n)T_{r-1}(n) be the Turán graph and tr−1(n)=∣Tr−1(n)∣t_{r-1}(n)=|T_{r-1}(n)|. Also, tKnt\mathcal{K}_n and tK‾nt\overline{\mathcal{K}}_n denote multisets consisting of tt copies of KnK_n and K‾n\overline{K}_n, respectively, while tTr−1(n)t\mathcal{T}_{r-1}(n) denotes tt copies of Tr−1(n)T_{r-1}(n).

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

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

Moreover, (h−1)Kn∪(k−h+1)K‾n (h-1)\mathcal{K}_n\cup(k-h+1)\overline{\mathcal{K}}_n and kTr−1(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.

References

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.