Strongly common graphs with odd girth are cycles

Abstract

A graph $H$ is called strongly common if for every coloring $\varphi$ of $K_n$ with two colors, the number of monochromatic copies of $H$ is at least the number of monochromatic copies of $H$ in a random coloring of $K_n$ with the same density of color classes as $\varphi$. In this note we prove that if a graph has odd girth but is not a cycle, then it is not strongly common. This answers a question of Chen and Ma.

3 pages