Combinatorics · Symmetry · Optimisation

Exploring
Ramsey numbers.

What is a Ramsey number? R(m,n) is the smallest number of vertices such that every red–blue colouring of the edges of a complete graph contains either a blue clique on m vertices or a red clique on n vertices.

A clique is a set of vertices with every pair joined. A monochromatic clique has all those edges in the same colour.

The first example

R(4,4) = 18. With eighteen vertices, a blue or red clique on four vertices is unavoidable. With seventeen, a colouring can avoid both, as the graph shows.

First proved by Greenwood and Gleason (1955); see Radziszowski, Small Ramsey Numbers, §2.1(b).

Our research searches for colourings that avoid both forbidden cliques.
Each verified construction proves a lower bound on a Ramsey number.

A closer look at a constructionK17
17vertices
FIG. 01No blue clique on 4 vertices.
No red clique on 4 vertices.
R(4,4) > 17

Neither colour contains a clique on four vertices. This graph is a counterexample to the claim that 17 vertices always force one, so R(4,4) > 17, equivalently R(4,4) ≥ 18. Finding such counterexamples on more vertices is how we prove stronger lower bounds.

01 / Searching in graph families

Give the search some structure.

There are enormously many ways to colour a complete graph. We can search within a family with a compact description, such as circulant graphs. Every valid counterexample we find still proves a lower bound for the ordinary Ramsey number.

The restriction makes the search smaller. A failed search within this family does not rule out counterexamples in other families.

02 / Build a circulant graph

Many edges.
Just a few choices.

Arrange the vertices on a circle. Choose circular distances and join every pair at those distances. Rotating the vertices preserves the graph.

The circular distance is the shorter number of steps around the circle. There are ⌊t/2⌋ possible distances on t vertices. Selecting a distance adds its entire class of edges.

Move the slider, then choose which distances belong to the graph.

Include these distances

This graph becomes the blue colour class. Its missing edges become red in the next step.

03 / Turn the graph into a colouring

One graph. Its complement.
A possible counterexample.

Colour the selected edges blue and every missing edge red. Instead of choosing colours for all t(t−1)/2 edges, you now have just ⌊t/2⌋ distance colours.

Avoid a blue clique on m vertices and a red clique on n vertices. If both conditions hold on t vertices, the colouring proves R(m,n) ≥ t+1. Change a distance below and see whether the counterexample survives.

Now change a construction

In these small examples, every edit is checked exactly in your browser.

Try a prediction exercise

Start with a valid construction, such as the 5-vertex R(3,3) example or the 17-vertex R(4,4) example.

1. Predict. Choose a distance before changing it. Which colour could gain a forbidden clique? Will one appear, and which vertices might form it?

2. Change. Switch that distance’s colour, then compare the blue and red clique counts with your prediction.

3. Inspect. If a forbidden clique appears, select Show a clique and examine its vertices and edges. Otherwise, explain why the colouring still avoids both forbidden sizes. Use Reset to try another prediction.

Hint: Only the colour gaining edges can acquire new cliques; the other colour loses edges. The question is whether those new edges actually complete a forbidden clique.

Distance coloursclick to switch

You can also click an edge in the graph. Solid red and dashed blue distinguish the two classes.

0blue K4 cliques
0red K4 cliques

This demo checks the displayed small graphs exactly. The research solver is available in the repository.

Interactive check
Both colours are checked.
Red Blue
What does a valid colouring prove?

A colouring on t vertices with no blue clique of order m and no red clique of order n proves R(m,n) ≥ t+1. Establishing the exact value also requires a matching upper bound.

The 17-vertex construction is a classical example for R(4,4), rather than a new result of this project. The examples on 5 and 6 vertices illustrate R(3,3) = 6. Edits in this demo explore circulant colourings only.

Known numbers

Exact values and open questions.

Read the classical values in Radziszowski’s survey, then the circulant numbers computed in our study.

Explore known numbers ↗
Graph gallery

See both colour classes.

Explore 11 constructions with their blue and red graphs side by side, and see which lower bound each one proves.

Explore the gallery ↗
Results from the paper

Follow the evidence.

Browse the 25 reported lower bounds and download the graph certificates behind them.

Explore the results ↗

Behind the constructions

How does the search work?

Read the mathematical formulation, search algorithm and verification procedure in the dedicated explanation of the paper’s method.

Explore the method

The project / From research to code

A project to read,
check and build on.

This website accompanies the paper An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs.

The repository brings together code, instructions, certificates and visualisations. The solver combines integer programming with clique search; a second engine explores circulant colourings without a linear programming model.

Explore the repository
Practical details for running the code

The branch-and-cut solver requires a local IBM ILOG CPLEX installation. The currently distributed package uses precompiled objects incorporating COPT. The checker does not require CPLEX. See the repository for requirements and instructions.

The interactions on this page demonstrate small graphs; they do not run the research solver. The certificates and results come from repository snapshot 38e59da.