Exact values of multicolor Ramsey numbers \(R_l(C_{\le l+1})\) (Q2175811)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Exact values of multicolor Ramsey numbers \(R_l(C_{\le l+1})\) |
scientific article |
Statements
Exact values of multicolor Ramsey numbers \(R_l(C_{\le l+1})\) (English)
0 references
30 April 2020
0 references
Let \(R_i(C_{\leq m})\) be the least \(n\) such that if the edges of \(K_n\) are \(i\)-colored, there will be a monochromatic cycle of order at most \(m\); thus if \(n < R_i(C_{\leq m})\), there will be an \(i\)-coloring of \(K_n\) such that every monochromatic subgraph of \(K_n\) is of girth at least \(m + 1\). The primary result of this article is that \[ R_i(C_{\leq l+1}) = \left\{\begin{array}{lr}2l + 4 & \mbox{if \(l \in \{ 4, 6 \}\)},\\ 2l + 3 & \mbox{if \(l\) even \(8 \leq l \leq 12\), or \(l\) odd \(3 \leq l\)},\end{array}\right\} \] and it concludes with a conjecture that \(R_i(C_{\leq l+1}) = 2l + 3\) for even \(l \geq 14\). This article is relatively elementary, but intricate, with occasional leaps, and uses values of \(ex(n, C_{\leq m})\), the maximum size of a graph of order \(n\) and girth at least \(m + 1\).
0 references
girth
0 references
extremal graph
0 references
cycle
0 references
Hamilton cycle
0 references
Ramsey number
0 references