Seminar Details

One of the classical results in extremal graph theory, Goodman's theorem, states that whenever the edges of a complete n-vertex graph are colored red or blue, there will be at least (1-o(1))n^2/24 monochromatic triangles. In other words, about a quarter of all possible triangles are guaranteed to be monochromatic. Erdos asked a similar question about the smallest number of *edge-disjoint* monochromatic triangles in every such coloring. He conjectured that the answer should be (1-o(1))n^2/12, which is achieved by one color class being the disjoint union of two cliques of order n/2. I will present a recent proof of this fact in the class of colorings where one of the color classes is triangle-free. Put differently, we show that the complement of any triangle-free n-vertex graph contains at least (1-o(1))n^2/12 edge-disjoint triangles.