Threshold Ramsey multiplicity for odd cycles
DOI:
https://doi.org/10.33044/revuma.2874Abstract
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.
Downloads
References
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, https://arxiv.org/abs/2108.00991 [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, https://infoscience.epfl.ch/record/175667, 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, https://arxiv.org/abs/1107.1153 [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, https://arxiv.org/abs/2005.09251 [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, https://arxiv.org/abs/1406.6738 [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.
Downloads
Published
Issue
Section
License
Copyright (c) 2022 David Conlon, Jacob Fox, Benjamin Sudakov, Fan Wei
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. The Journal may retract the paper after publication if clear evidence is found that the findings are unreliable as a result of misconduct or honest error.
