Threshold Ramsey multiplicity for paths and even cycles

David Conlon, Jacob Fox, Benny Sudakov, Fan Wei

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


The Ramsey number r(H) of a graph H is the minimum integer n such that any two-coloring of the edges of the complete graph Kn contains a monochromatic copy of H. While this definition only asks for a single monochromatic copy of H, it is often the case that every two-edge-coloring of the complete graph on r(H) vertices contains many monochromatic copies of H. The minimum number of such copies over all two-colorings of Kr(H) will be referred to as the threshold Ramsey multiplicity of H. Addressing a problem of Harary and Prins, who were the first to systematically study this quantity, we show that there is a positive constant c such that the threshold Ramsey multiplicity of a path or an even cycle on k vertices is at least (ck)k. This bound is tight up to the constant c. We prove a similar result for odd cycles in a companion paper.

Original languageEnglish (US)
Article number103612
JournalEuropean Journal of Combinatorics
StatePublished - Jan 2023

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Threshold Ramsey multiplicity for paths and even cycles'. Together they form a unique fingerprint.

Cite this