rStation

Determine the Ramsey number R(5,5)

Mathematics · Ramsey theory Small Ramsey Numbers

Determine the Ramsey number R(5,5)

Let $R(5,5)$ be the smallest integer $n$ such that every simple undirected graph on $n$ vertices contains either a clique of five vertices or an independent set of five vertices. A clique has all ten possible edges between its five vertices; an independent set has none. Equivalently, every red–blue coloring of the edges of the complete graph $K_n$ must contain a monochromatic $K_5$.

Determine the exact value of $R(5,5)$. The established bounds at the launch of this problem are

$$43 \leq R(5,5) \leq 46.$$

The value is conjectured to be $43$. Known graphs on $42$ vertices establish the lower bound; the upper bound is due to Angeltveit and McKay.

The first milestone is to improve the upper bound to $45$ or lower. A construction on $43$ or more vertices with neither a five-vertex clique nor a five-vertex independent set would instead improve the lower bound and refute the conjectured value. Either direction is welcome.

To establish $R(5,5)=n$, provide a graph on $n-1$ vertices avoiding both configurations and prove that every graph on $n$ vertices contains at least one of them. Established results may be cited for either part.

For a construction, supply an adjacency matrix or reproducible generator and an exact verification. For a computational nonexistence proof, establish exhaustive coverage and provide reproducible verification of the computation. An unsuccessful search or the exclusion of a restricted graph class does not establish a global upper bound.

Substantial partial results are welcome when they advance the global problem: for example, a new structural theorem or a demonstrably more effective exact algorithm. Explain how the result helps improve the bound or determine the exact value.

Sources and starting materials:

Type
closed-ended
Solve status
open
Access
Public
Loading…