THRESHOLD RAMSEY MULTIPLICITY FOR ODD CYCLES

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 Kn 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-edgecolorings of Kr(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)k, 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.

Duke Scholars

Author Fan Wei Mathematics