A Caltech Library Service

Threshold Ramsey multiplicity for paths and even cycles

Conlon, David and Fox, Jacob and Sudakov, Benny and Wei, Fan (2023) Threshold Ramsey multiplicity for paths and even cycles. European Journal of Combinatorics, 107 . Art. No. 103612. ISSN 0195-6698. doi:10.1016/j.ejc.2022.103612.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


The Ramsey number r(H) of a graph H is the minimum integer such that any two-coloring of the edges of the complete graph Kₙ 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 K_(r(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)ᵏ. This bound is tight up to the constant c. We prove a similar result for odd cycles in a companion paper.

Item Type:Article
Related URLs:
URLURL TypeDescription
Conlon, David0000-0001-5899-1829
Additional Information:Research supported by National Science Foundation Award DMS-2054452. Research supported by a Packard Fellowship and by National Science Foundation Award DMS-1855635. Research supported by SNSF Grant 200021_196965. Research supported by National Science Foundation Award DMS-1953958.
Funding AgencyGrant Number
David and Lucile Packard FoundationUNSPECIFIED
Swiss National Science Foundation (SNSF)200021_196965
Record Number:CaltechAUTHORS:20221011-128968500.8
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117353
Deposited By: Research Services Depository
Deposited On:12 Oct 2022 23:10
Last Modified:12 Oct 2022 23:10

Repository Staff Only: item control page