Threshold Ramsey multiplicity for odd cycles

Abstract

The Ramsey number r(H) of a graph H is the minimum n such that any two-coloring of the edges of the complete graph Kₙ contains a monochromatic copy of H. The threshold Ramsey multiplicity m(H) is then the minimum number of monochromatic copies of H taken over all two-edge-colorings of K_(r(H)). The study of this concept was first proposed by Harary and Prins almost fifty years ago. In a companion paper, the authors have shown that there is a positive constant c such that the threshold Ramsey multiplicity for a path or even cycle with k vertices is at least (ck)ᵏ, which is tight up to the value of c. Here, using different methods, we show that the same result also holds for odd cycles with k vertices.

Additional details