Journal of Combinatorics

Volume 2 (2011)

Number 1

Graphs containing triangles are not 3-common

Pages: 1 – 14

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n1.a1

Authors

James Cummings (Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh Penn., U.S.A.)

Michael Young (Department of Mathematics, Iowa State University, Ames, Iowa, U.S.A.)

Abstract

A finite graph $G$ is {\em $k$-common} if the minimum (over all $k$-colourings of the edges of $K_n$) 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_n$. Jagger, \u{S}\u{t}oví\u{c}ek and Thomason showed that graphs which contain $K_4$ are not $2$-common. We prove that graphs which contain $K_3$ are not $3$-common.

Full Text (PDF format)