Published August 2022 | Version public
Journal Article

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 Information

The first author [Conlon] is supported by NSF Award DMS-2054452. The second author [Fox] is supported by a Packard Fellowship and by NSF Award DMS-1855635. The third author [Sudakov] is supported by SNSF grant 200021_196965. The last author [Wei] is supported by NSF Award DMS-1953958.

Additional details

Identifiers

Eprint ID
117741
Resolver ID
CaltechAUTHORS:20221107-997760900.3

Funding

NSF
DMS-2054452
NSF
DMS-1855635
Swiss National Science Foundation (SNSF)
200021_196965
NSF
DMS-1953958

Dates

Created
2022-11-17
Created from EPrint's datestamp field
Updated
2022-11-17
Created from EPrint's last_modified field