Monochromatic triangle packings in red-blue graphs

2020/08/12 by Gruslys, Vytautas, Letzter, Shoham
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2008.05311

Abstract

We prove that in every 2-edge-colouring of K_n there is a collection of n²/12 + o(n²) edge-disjoint monochromatic triangles, thus confirming a conjecture of Erdős. We also prove a corresponding stability result, showing that 2-colourings that are close to attaining the aforementioned bound have a colour class which is close to bipartite. As part of our proof, we confirm a recent conjecture of Tyomkyn about the fractional version of this problem.

Related

• The Erdős-Hajnal conjecture for three colors and multiple forbidden patterns
• A framework for the generalised Erdős-Rothschild problem and a resolution of the dichromatic triangle case
• On 2-colored graphs and partitions of boxes
• Monochromatic triangles in three-coloured graphs
• Monochromatic partitions in 2-edge-coloured bipartite graphs