For given graphs G1,…, Gk, the size-Ramsey number $\hat R({G_1}, \ldots ,{G_k})$ is the smallest integer m for which there exists a graph H on m edges such that in every k-edge colouring of H with colours 1,…,k, H contains a monochromatic copy of Gi of colour i for some 1 ≤ i ≤ k. We denote $\hat R({G_1}, \ldots ,{G_k})$ by ${\hat R_k}(G)$ when G1 = ⋯ = Gk = G.

Haxell, Kohayakawa and Łuczak showed that the size-Ramsey number of a cycle Cn is linear in n, ${\hat R_k}({C_n}) \le {c_k}n$ for some constant ck. Their proof, however, is based on Szemerédi’s regularity lemma so no specific constant ck is known.

In this paper, we give various upper bounds for the size-Ramsey numbers of cycles. We provide an alternative proof of ${\hat R_k}({C_n}) \le {c_k}n$ , avoiding use of the regularity lemma, where ck is exponential and doubly exponential in k, when n is even and odd, respectively. In particular, we show that for sufficiently large n we have ${\hat R_2}({C_n}) \le {10^5} \times cn$ , where c = 6.5 if n is even and c = 1989 otherwise.

A set of points in d-dimensional Euclidean space is almost equidistant if, among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in ℝd has cardinality O(d4/3).

The 3-uniform tight cycle Cs3 has vertex set ${\mathbb Z}_s$ and edge set {{i, i + 1, i + 2}: i ∈ ${\mathbb Z}_s$}. We prove that for every s ≢ 0 (mod 3) with s ⩾ 16 or s ∈ {8, 11, 14} there is a cs > 0 such that the 3-uniform hypergraph Ramsey number r(Cs3, Kn3) satisfies

$$\begin{equation*} r(C_s^3, K_n^3)< 2^{c_s n \log n}.\ \end{equation*}$$

$2^{n^{1+\epsilon_s}}$

In this paper we give a short proof of the Random Ramsey Theorem of Rödl and Ruciński: for any graph F which contains a cycle and r ≥ 2, there exist constants c, C > 0 such that

$$ \begin{equation*} \Pr[G_{n,p} \rightarrow (F)_r^e] = \begin{cases} 1-o(1) &p\ge Cn^{-1/m_2(F)},\\ o(1) &p\le cn^{-1/m_2(F)}, \end{cases} \end{equation*} $$

$$ \begin{equation*} m_2(F) = \max_{J\subseteq F, v_J\ge 2} \frac{e_J-1}{v_J-2}. \end{equation*} $$

We call a graph H Ramsey-unsaturated if there is an edge in the complement of H such that the Ramsey number r(H) of H does not change upon adding it to H. This notion was introduced by Balister, Lehel and Schelp in [J. Graph Theory51 (2006), pp. 22–32], where it is shown that cycles (except for C4) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle Cn, unless n is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger statement. If a graph H is obtained by adding a linear number of chords to a cycle Cn, then r(H)=r(Cn), as long as the maximum degree of H is bounded, H is either bipartite (for even n) or almost bipartite (for odd n), and n is large.

This motivates us to call cycles strongly Ramsey-unsaturated. Our proof uses the regularity method.