Weighted rainbow clique conjecture

Let r3r\ge 3, k(r2)k\ge\binom{r}{2}, and let G0KnG_0\cong K_n be a complete graph on [n][n]. A kk-weighted graph is a pair G=(G0,f)\mathcal{G}=(G_0,f) with an edge-weighting ff. A weight sequence bound (1,2,,(r2))(1,2,\ldots,\binom{r}{2}) means that every KrK_r has its nondecreasing edge-weight sequence lexicographically at least this sequence. Define

k2=((r2)1)(n2)tr1(n),k1=k21.k_2=\left\lceil\frac{\left(\binom{r}{2}-1\right)\binom{n}{2}}{t_{r-1}(n)}\right\rceil,\qquad k_1=k_2-1.

Weighted rainbow clique conjecture. If nrn\ge r, G0G_0 contains no KrK_r with weight sequence bound (1,2,,(r2))(1,2,\ldots,\binom{r}{2}), then: (i) if k=k1k=k_1, f(G0)((r2)1)(n2)f(G_0)\le(\binom{r}{2}-1)\binom{n}{2}; and (ii) if k=k2k=k_2, f(G0)ktr1(n)f(G_0)\le k\,t_{r-1}(n).

This weighted statement is introduced as a conjectural reformulation implying the rainbow Turán clique bound. The source proves it for r=4,5r=4,5; the general case remains open.

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.