Sharp bounds for some multicolour Ramsey numbers

Given a sequence \(H_1, H_2, \dots, H_{k+1}\) of \(k+1\) finite, undirected, simple graphs, the (multicolored) Ramsey number \(r(H_1, H_2, \dots , H_{k+1})\) is the minimum integer \(r\) such that in every edge-coloring of the complete graph on \(r\) vertices by \(k+1\) colors, there is a monochromatic copy of \(H_i\) in color \(i\), for some \(1\leq i\leq k + 1\). The paper provides tight bounds for several multicolored Ramsey numbers when \(k\geq 2\) and \(H_{k+1}\) is the complete graph \(K_m\) on \(m\) vertices. In particular, the authors show that \(r(K_3, K_3, K_m)=\Theta(m^3\) {polylog} \(m)\); this proves a conjecture of Erdős and Sós raised in 1979. Among other results of particular interest are bounds \(r(C_4, C_4, K_m)=\Theta(m^2\) {polylog} \(m)\) and \(r(C_4, C_4, C_4, K_m)=\Theta(m^2/\log^2 m)\). The proofs employ, besides combinatorial and probabilistic arguments, spectral techniques and some estimates of character sums.

Recommendations

Cited in

(50)

This page was built for publication: Sharp bounds for some multicolour Ramsey numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2494438)