Threshold Ramsey multiplicity for odd cycles


  • David Conlon Department of Mathematics, Caltech, Pasadena, CA 91125, USA
  • Jacob Fox Department of Mathematics, Stanford University, Stanford, CA 94305, USA
  • Benjamin Sudakov Department of Mathematics, ETH, 8092 Z¨urich, Switzerland
  • Fan Wei Department of Mathematics, Princeton University, Princeton, NJ 08540, USA



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_n$ 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)^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.


Download data is not yet available.


S. A. Burr and V. Rosta, On the Ramsey multiplicities of graphs—problems and recent results, J. Graph Theory 4 (1980), no. 4, 347–361. MR 0595601.

D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of Math. (2) 170 (2009), no. 2, 941–960. MR 2552114.

D. Conlon, J. Fox and B. Sudakov, An approximate version of Sidorenko's conjecture, Geom. Funct. Anal. 20 (2010), no. 6, 1354–1366. MR 2738996.

D. Conlon, J. Fox and B. Sudakov, Recent developments in graph Ramsey theory, in Surveys in Combinatorics 2015, 49–118, London Math. Soc. Lecture Note Ser., 424, Cambridge Univ. Press, Cambridge, 2015. MR 3497267.

D. Conlon, J. Fox, B. Sudakov, and F. Wei, Threshold Ramsey multiplicity for paths and even cycles, [math.CO], 2021.

D. Conlon, J. H. Kim, C. Lee, and J. Lee, Some advances on Sidorenko's conjecture, J. Lond. Math. Soc. (2) 98 (2018), no. 3, 593–608. MR 3893193.

D. Conlon and J. Lee, Sidorenko's conjecture for blow-ups, Discrete Anal. 2021, Paper No. 2, 13 pp. MR 4237083.

P. Erdős, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 459–464. MR 0151956.

R. J. Faudree and R. H. Schelp, All Ramsey numbers for cycles in graphs, Discrete Math. 8 (1974), 313–329. MR 0345866.

L. Gerencsér and A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967), 167–170. MR 0239997.

F. Harary, A survey of generalized Ramsey theory, in Graphs and Combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), 10–17, Lecture Notes in Math., 406, Springer, Berlin, 1974. MR 0360333.

F. Harary and G. Prins, Generalized Ramsey theory for graphs. IV. The Ramsey multiplicity of a graph, Networks 4 (1974), 163–173. MR 0340080.

H. Hatami, J. Hladký, D. Král, S. Norine, and A. Razborov, Non-three-colourable common graphs exist, Combin. Probab. Comput. 21 (2012), no. 5, 734–742. MR 2959863.

C. Jagger, P. Šťovíček, and A. Thomason, Multiplicities of subgraphs, Combinatorica 16 (1996), no. 1, 123–141. MR 1394515.

G. Károlyi and V. Rosta, On the Ramsey multiplicity of the odd cycles,, 2010.

J. H. Kim, C. Lee, and J. Lee, Two approaches to Sidorenko's conjecture, Trans. Amer. Math. Soc. 368 (2016), no. 7, 5057–5074. MR 3456171.

J. Komlós and M. Simonovits, Szemerédi's regularity lemma and its applications in graph theory, in Combinatorics, Paul Erdős is Eighty, Vol. 2 (Keszthely, 1993), 295–352, Bolyai Soc. Math. Stud., 2, János Bolyai Math. Soc., Budapest, 1996. MR 1395865.

J. L. X. Li and B. Szegedy, On the logarithmic calculus and Sidorenko's conjecture, [math.CO], 2011.

V. Nikiforov and R. H. Schelp, Cycles and stability, J. Combin. Theory Ser. B 98 (2008), no. 1, 69–84. MR 2368024.

K. Piwakowski and S. P. Radziszowski, The Ramsey multiplicity of $K_4$, Ars Combin. 60 (2001), 131–135. MR 1849472.

V. Rosta, On a Ramsey-type problem of J. A. Bondy and P. Erdős. I, II, J. Combin. Theory Ser. B 15 (1973), 94–104; ibid. 15 (1973), 105–120. MR 0332567.

V. Rosta and L. Surányi, A note on the Ramsey-multiplicity of the circuit, Period. Math. Hungar. 7 (1976), no. 3-4, 223–227. MR 0460167.

A. Sah, Diagonal Ramsey via effective quasirandomness, [math.CO], 2020.

A. F. Sidorenko, Cycles in graphs and functional inequalities, Math. Notes 46 (1989), no. 5-6, 877–882. MR 1033422.

A. Sidorenko, An analytic approach to extremal problems for graphs and hypergraphs, in Extremal Problems for Finite Sets (Visegrád, 1991), 423–455, Bolyai Soc. Math. Stud., 3, János Bolyai Math. Soc., Budapest, 1994. MR 1319175.

A. Sidorenko, A correlation inequality for bipartite graphs, Graphs Combin. 9 (1993), no. 2, 201–204. MR 1225933.

M. Simonovits, Extremal graph problems, degenerate extremal problems, and supersaturated graphs, in Progress in Graph Theory (Waterloo, Ont., 1982), 419–437, Academic Press, Toronto, 1984. MR 0776819.

J. Spencer, Ramsey's theorem—a new lower bound, J. Combin. Theory Ser. A 18 (1975), 108–115. MR 0366726.

B. Szegedy, An information theoretic approach to Sidorenko's conjecture, [math.CO], 2015.

A. Thomason, A disproof of a conjecture of Erdős in Ramsey theory, J. London Math. Soc. (2) 39 (1989), no. 2, 246–255. MR 0991659.