Open research · Distance colourings

Ramsey colourings.
Along a line.

An open research direction. Linear-distance colourings are not covered in the paper. This page explores the idea interactively, starting from existing constructions.

The same Ramsey question. A larger family. 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.

Put the vertices at positions 0, 1, …, t−1. Give every edge of the same linear distance |i−j| the same colour. The blue graph is a Toeplitz graph; the red graph is its complement.

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.

The same counterexample, unfoldedK17
FIG. 01 / LINEARNo 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.

Blue arcs above, red arcs below. On a small screen, swipe across the drawing.

01 / Searching in graph families

Give the search some structure.

A linear-distance colouring needs only t−1 colour choices for t(t−1)/2 edges. Edges with equal differences share a colour. Every valid counterexample found in this family still proves a lower bound for the ordinary Ramsey number.

Every circulant colouring is also a linear-distance colouring: set the colours of d and t−d equal. Here you may change them independently. The familiar examples below start with that equality, and your edits can explore the larger family.

02 / Build a linear-distance graph

Many edges.
Just a few choices.

Arrange the vertices on a line. Select a difference d and join all pairs i, i+d. The arcs bend above the line so equal lengths are easy to follow.

The distance is d = |i−j|, with no wrap-around. There are t−1 possible distances. Distance d has exactly t−d edges: on 17 vertices, distance 1 has 16 edges and distance 16 has just one.

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−1 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

Click a distance or an arc to switch its whole class. Dashed blue arcs sit above the line; solid red arcs sit below. Vertices are numbered from 0.

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.

On a small screen, swipe across the drawing to see every vertex.

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. These presets are classical or paper circulant witnesses, embedded in the linear-distance family. Editing distance d does not change t−d. This page does not claim new distance-colouring results.

From circles to differences

More freedom. The same certificate.

Equal distance, equal colour.

The edges (0,3), (1,4) and (2,5) all have distance 3 and change together. The colour only depends on |i−j|. Blue arcs are drawn above the line and red arcs below; their curvature is just a visual aid.

A larger search space.

Circulant colourings require d and t−d to have the same colour. Linear-distance colourings drop that constraint: t−1 binary choices instead of ⌊t/2⌋. More freedom can help a search, but it does not guarantee a stronger bound.

What an exact check proves.

The demo counts blue Km and red Kn cliques separately, using the actual linear differences. If both counts are zero, the displayed t-vertex colouring proves R(m,n) ≥ t+1. A forbidden clique can be highlighted directly.

Linear-distance colourings are an open research direction, not covered in the paper. Read the linear-distance model documentation ↗ · Compare with the circulant explorer ↗

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.