Diagonal Ramsey numbers

Connect every pair of six dots and color each line red or blue. No matter how you choose, three dots have all three connecting lines the same color. Five dots can avoid that: make the edges of a five-sided cycle red and the remaining connections blue. The open question asks how fast the number of dots needed grows when the forced same-color group must be larger than three.[2]

Red and blue labels on all pairwise connections may look disorderly. How large must the set of points be before a same-color complete group is inevitable, and how does that threshold grow with the group's size? Define $R(k,k)$ as the least $n$ for which every two-coloring of the complete graph on $n$ vertices contains a monochromatic $k$-clique: $k$ vertices with all their connecting edges one color.

For six vertices, select one. At least three of its five edges share a color, say red. A red edge among those three neighbors completes a red triangle; if none is red, their three edges form a blue triangle. The five-cycle coloring avoids either triangle, so $R(3,3)=6$. The general asymptotic growth is the remaining target.[1] [2]

A finite threshold is known to exist for every requested group size. The problem is its sharp growth as that size increases. A coloring that avoids the group sets a lower bound; a proof that every coloring contains it sets an upper bound. Those estimates still leave a substantial gap.[1] [2]

For all sufficiently large $k$, the reviewed paper recalls an exponential lower estimate $R(k,k)\geq2^{k/2}$ and proves an upper estimate $R(k,k)\leq(4-\varepsilon)^k$ for some fixed $\varepsilon>0$. These are selected established bounds, not a claim of current best constants.

Exponential growth means raising a fixed base to the growing group size; bases that remain apart leave a gap that grows exponentially. An improvement on one side is valuable without settling the sharp rate. This page does not assume that $R(k,k)^{1/k}$ has a limit.[1] [2]

Arbitrary pairwise choices eventually force a completely uniform group. Equivalently, a sufficiently large network must have either many vertices all joined to each other or many with no joins between them. The threshold measures how long both kinds of order can be avoided.[2]

Treat red edges as connections in an ordinary graph and blue edges as absent connections. A monochromatic clique then gives either a completely connected group or a group with no internal connections. Ramsey growth quantifies how large both kinds of homogeneous group can be kept absent.

For a lower bound, take $k\geq2$ and color edges independently with equal probabilities. A fixed $k$-vertex group is monochromatic with probability $2^{1-\binom{k}{2}}$. The expected number of these groups among $n$ vertices is $\binom nk2^{1-\binom{k}{2}}$. If this is below one, some coloring has none. This gives an existence argument; it is different from proving that every coloring must contain a group.[2]