Erdős–Sós extremal coloring conjecture for rainbow triangles

Let KnK_n be the complete graph on nn vertices with its edges colored using three colors. Let F(G)F(G) be the number of rainbow triangles in a coloring GG, and let

F(n)=maxG:3-edge-colored KnF(G).F(n)=\max_{G:\,\text{$3$-edge-colored }K_n}F(G).

A coloring is attained via Construction when it is obtained by fixing the unique, up to isomorphism, three-edge-coloring of K4K_4 in which every triangle is rainbow, blowing up its four vertices into classes of sizes a,b,c,da,b,c,d, inheriting the interclass edge colors, and placing extremal colorings inside the four classes. Erdős–Sós extremal coloring conjecture. For every nn, all three-edge-colorings of KnK_n attaining F(n)F(n) are attained via this construction.

The construction gives the recursive formula conjectured by Erdős and Sós for the extremal number of rainbow triangles, with a+b+c+d=na+b+c+d=n and a,b,c,da,b,c,d as equal as possible. The paper proves that this recurrence holds for sufficiently large nn and for n=4kn=4^k, but the stronger assertion that every extremal coloring arises from the construction is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Jozsef Balogh, Ping Hu, Bernard Lidicky, Florian Pfender, Jan Volec and Michael Young, “Rainbow triangles in three-colored graphs”, arXiv:1408.5296 (2014).

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.