Logo
All Random Solved Random Open
SOLVED
Is it true that in any $2$-colouring of the edges of $K_n$ there must exist at least \[(1+o(1))\frac{n^2}{12}\] many edge-disjoint monochromatic triangles?
Conjectured by Erdős, Faudreee, and Ordman. This would be best possible, as witnessed by dividing the vertices of $K_n$ into two equal parts and colouring all edges between the parts red and all edges inside the parts blue.

The answer is yes, proved by Gruslys and Letzter [GrLe20].

In [Er97d] Erdős also asks for a lower bound for the count of edge-disjoint monochromatic triangles in single colour (the colour chosen to maximise this quantity), and speculates that the answer is $\geq cn^2$ for some constant $c?1/24$.

Additional thanks to: Tuan Tran