A note on multicolor Ramsey number of small odd cycles versus a large clique

2021/10/19 by Zixiang Xu, Gennian Ge, Xu, Zixiang +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2110.09799

openalex publication_date 2021/10/19 · openalex created_date 2021/10/25 · openalex updated_date 2026/07/28

Abstract

Let R_k(H;K_m) be the smallest number N such that every coloring of the edges of K_N with k+1 colors has either a monochromatic H in color i for some 1\leqslant i\leqslant k, or a monochromatic K_m in color k+1. In this short note, we study the lower bound for R_k(H;K_m) when H is C₅ or C₇, respectively. We show that R_k(C₅;K_m)=Ω(m^(3k)/(8)+1/(logm)^(3k)/(8)+1), and R_k(C₇;K_m)=Ω(m^(2k)/(9)+1/(logm)^(2k)/(9)+1), for fixed positive integer k and m→∞. These slightly improve the previously known lower bound R_k(C_2ℓ+1;K_m)=Ω(m^{(k)/(2ℓ-1)+1}/(log m)^{k+(2k)/(2ℓ-1)}) obtained by Alon and Rödl. The proof is based on random block constructions and random blowups argument.

Related

• Multicolor Size-Ramsey Number of Cycles
• New bounds for some small multicolor Ramsey numbers
• Improved bounds on the multicolor Ramsey numbers of paths and even cycles
• Multicolour Ramsey Numbers of Odd Cycles
• New upper bound for multicolor Ramsey number of odd cycles