Graphs containing triangles are not 3-common

2011-01-01T00:00:00Z (GMT) by James Cummings Michael Young
<p>A finite graph G is {\em k-common} if the minimum (over all k-colourings of the edges of K<sub>n</sub>) of the number of monochromatic labelled copies of G is asymptotically equal, as n tends to infinity, to the expected number of such copies in a random k-colouring of the edges of K<sub>n</sub>. Jagger, \u{S}\u{t}oví\u{c}ek and Thomason showed that graphs which contain K<sub>4</sub> are not 2-common. We prove that graphs which contain K<sub>3</sub> are not 3-common.</p>