Bounds for two multicolor Ramsey numbers concerning quadrilaterals

Xuemei Zhang, Yaojun Chen, T. C.Edwin Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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.

Original languageEnglish
Article number101999
JournalFinite Fields and Their Applications
Volume79
DOIs
Publication statusPublished - Mar 2022

Keywords

  • Galois field
  • Multicolor Ramsey number
  • Quadrilateral
  • Random graph
  • Singer difference set
  • Star
  • Wheel

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Algebra and Number Theory
  • Engineering(all)
  • Applied Mathematics

Cite this