Frankl–Győri–He–Lv–Salia–Tompkins–Varga–Zhu conjecture for Gallai 3-colouring templates

From papers

Let h:[0,1]Rh:[0,1]\to\mathbb{R} be defined by

h(x)=(x2+(1x)2)x2(1x2),h(x)=\left(x^2+(1-x)^2\right)x^2\left(1-x^2\right),

and let υ[0,1]\upsilon\in[0,1] maximise hh. Let G=(G1,G2,G3)\mathbf{G}=(G_1,G_2,G_3) be a Gallai 33-colouring template on nn vertices, meaning that its three colour classes partition the pairs of vertices and contain no rainbow triangle.

Frankl–Győri–He–Lv–Salia–Tompkins–Varga–Zhu conjecture. As nn tends to infinity,

(E(G1)E(G2)E(G3))13(h(υ)+o(1))13(n2).\Bigl(\lvert E(G_1)\rvert\cdot\lvert E(G_2)\rvert\cdot\lvert E(G_3)\rvert\Bigr)^{\frac13}\leq\left(h(\upsilon)+o(1)\right)^{\frac13}\binom{n}{2}.

The conjecture asserts that the construction H(υn,nυn,0)\mathbf{H}(\lceil\upsilon n\rceil,n-\lceil\upsilon n\rceil,0) is asymptotically optimal. It was proposed after that construction disproved Frankl's earlier upper bound; the supplied text gives no resolution of this conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Victor Falgas-Ravry, Klas Markström and Eero Räty, “Rainbow variations on a theme by Mantel: extremal problems for Gallai colouring templates”, arXiv:2212.07180 (2024).

Solutions 0

No solutions have been posted yet.