Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2023 | public
Journal Article

Threshold Ramsey multiplicity for paths and even cycles

Abstract

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.

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.

Additional details

Created:
August 22, 2023
Modified:
October 24, 2023