TY - JOUR
T1 - Bounds for two multicolor Ramsey numbers concerning quadrilaterals
AU - Zhang, Xuemei
AU - Chen, Yaojun
AU - Cheng, T. C.Edwin
N1 - Funding Information:
Zhang was supported by NSFC under grant numbers 11801520 and 12171436 , Chen was supported by NSFC under grant numbers 11671198 , 11931006 and 12161141003 .
Publisher Copyright:
© 2022 Elsevier Inc.
PY - 2022/3
Y1 - 2022/3
N2 - For k given graphs H1,…,Hk, k≥2, the k-color Ramsey number, denoted by R(H1,…,Hk), is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of Hi colored with i, for some 1≤i≤k. Let Cm be a cycle of length m, K1,n a star of order n+1 and Wn a wheel of order n+1. In this paper, by using algebraic and probabilistic methods, we first give two lower bounds for (k+1)-color Ramsey number R(C4,…,C4,K1,n) for some special n, which shows the upper bound due to Zhang et al. (2019) is tight in some sense, and then establish a general lower bound for R(C4,…,C4,K1,n) in terms of n and k, which extends the classical result of Burr et al. (1989). Moreover, we show that R(C4,…,C4,K1,n)=R(C4,…,C4,Wn) for sufficiently large n.
AB - For k given graphs H1,…,Hk, k≥2, the k-color Ramsey number, denoted by R(H1,…,Hk), is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of Hi colored with i, for some 1≤i≤k. Let Cm be a cycle of length m, K1,n a star of order n+1 and Wn a wheel of order n+1. In this paper, by using algebraic and probabilistic methods, we first give two lower bounds for (k+1)-color Ramsey number R(C4,…,C4,K1,n) for some special n, which shows the upper bound due to Zhang et al. (2019) is tight in some sense, and then establish a general lower bound for R(C4,…,C4,K1,n) in terms of n and k, which extends the classical result of Burr et al. (1989). Moreover, we show that R(C4,…,C4,K1,n)=R(C4,…,C4,Wn) for sufficiently large n.
KW - Galois field
KW - Multicolor Ramsey number
KW - Quadrilateral
KW - Random graph
KW - Singer difference set
KW - Star
KW - Wheel
UR - http://www.scopus.com/inward/record.url?scp=85123806102&partnerID=8YFLogxK
U2 - 10.1016/j.ffa.2022.101999
DO - 10.1016/j.ffa.2022.101999
M3 - Journal article
AN - SCOPUS:85123806102
SN - 1071-5797
VL - 79
JO - Finite Fields and Their Applications
JF - Finite Fields and Their Applications
M1 - 101999
ER -