Erdős–Sós extremal coloring conjecture for rainbow triangles
Erdős–Sós extremal coloring conjecture for rainbow triangles
Let be the complete graph on vertices with its edges colored using three colors. Let be the number of rainbow triangles in a coloring , and let
A coloring is attained via Construction when it is obtained by fixing the unique, up to isomorphism, three-edge-coloring of in which every triangle is rainbow, blowing up its four vertices into classes of sizes , inheriting the interclass edge colors, and placing extremal colorings inside the four classes. Erdős–Sós extremal coloring conjecture. For every , all three-edge-colorings of attaining 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 and as equal as possible. The paper proves that this recurrence holds for sufficiently large and for , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.