← Back to the constructions

The method / Mathematical and computational ideas

From symmetry
to certificates.

We turn the search for a Ramsey colouring into an integer programming problem, use clique searches to expose forbidden structures, and keep the resulting graphs as explicit, verifiable evidence.

Based on the accompanying paperCirculant graphs · Branch-and-cut · Exact verification

01 / The mathematical question

A colouring is a witness.

With the convention used in this project, R(m,n) is the smallest number of vertices for which every red–blue edge colouring of the complete graph contains either a blue Km or a red Kn. The search asks for a colouring that avoids both.

No blue Km and no red Kn on t vertices
⇒ R(m,n) ≥ t + 1

This is a constructive lower bound: the colouring itself is the evidence. Establishing an exact Ramsey number also requires an upper bound that rules out every colouring at the corresponding threshold.

The distinction matters when reporting computational results. Failure to find a colouring is not a proof that none exists. Even an exact exclusion within a restricted graph class is not automatically an upper bound for the unrestricted Ramsey number.

02 / A smaller description

Colour distances, not individual edges.

Place the vertices at 0, 1, …, t−1 around a circle. In a circulant colouring, the colour of an edge depends only on its circular distance:

δ(i,j) = min(|i−j|, t−|i−j|).

All edges with the same circular distance receive the same colour. Rotating the vertices preserves the colouring. The whole graph can therefore be described by ⌊t/2⌋ binary decisions instead of t(t−1)/2.

The R(3,37) construction
271vertices
36,585edges to colour
135binary distance variables

This reduction describes a restricted search space. It does not assert that every unrestricted Ramsey colouring has a circulant representative.

The distance grid on the results page is exactly this representation: one cell per distance. The interactive examples change an entire distance class at a time.

03 / Integer programming

Describe the forbidden structures.

Write yd = 1 when distance d is blue and yd = 0 when it is red. For a vertex set S, let D(S) be the set of distinct circular distances occurring among its pairs of vertices.

If S has m vertices, preventing it from becoming a blue clique requires at least one of its distances to be red. If T has n vertices, preventing it from becoming a red clique requires at least one of its distances to be blue:

∑d ∈ D(S) yd ≤ |D(S)| − 1 for |S| = m
∑d ∈ D(T) yd ≥ 1 for |T| = n

These elementary inequalities explain the distance formulation. There are far too many candidate vertex sets to list every constraint in advance, so the algorithm generates violated constraints as they are needed.

The paper strengthens the formulation through coefficient reduction and inequalities exploiting clique structure. Distinct vertex sets can also produce the same distance pattern, which makes it useful to work directly with sets of distances. The full derivations and computational comparisons belong to the paper; the displayed equations introduce the basic mechanism.

04 / The search loop

Find a forbidden clique. Add a cut. Continue.

The branch-and-cut solver searches over the distance variables. For an integral candidate colouring, the separation routine builds its blue and red graphs and asks two target questions: is there a blue clique of size m, or a red clique of size n?

  1. Propose a candidate.The integer programming solver produces a candidate assignment of colours to distances.
  2. Search for a violation.Cheap bounds and greedy routines run first, followed by MNTS where enabled. An exact clique search resolves the questions that remain.
  3. Exclude the pattern.A forbidden clique gives a valid inequality. Adding it rules out the offending distance pattern and guides the next search.
  4. Keep a verified colouring.If both forbidden clique sizes are excluded, the integral colouring provides a constructive lower-bound witness.

Separation needs a target decision, not necessarily the maximum clique. Finding a valid target clique is enough to generate a cut. If the target is not found by a heuristic, an exact procedure is still needed to prove absence.

A timeout leaves the corresponding exact question unresolved. It must never be interpreted as evidence that the candidate avoids the forbidden clique.

05 / Using symmetry again

Look in a neighbourhood.

In a circulant graph, any clique can be rotated so that one of its vertices becomes a chosen anchor a. A search for a Kq can therefore be reduced to a search for a Kq−1 in the subgraph induced by the anchor’s neighbours:

Kq in G ⇔ Kq−1 in G[N(a)].

The anchor is added back to recover the full clique. This reduction relies on the graph’s structure: it is not sound at an arbitrary fixed vertex of a general graph, nor automatically in every induced subgraph of a circulant graph.

The later linear-distance extension has a related but different argument. Translation can move a clique to contain vertex 0 or t−1 while preserving all ordinary distances. Those endpoints are guaranteed anchors; an arbitrary interior vertex is not. This extension is documented separately from the paper’s circulant experiments.

06 / Evidence and interpretation

Separate the construction from its verification.

A published certificate lists the edges of the red graph in DIMACS format. Its blue graph is the complement. A separate checker tests that the blue graph contains no Km and that the red graph contains no Kn.

For unrestricted Ramsey numbers

A verified graph on t vertices proves R(m,n) ≥ t+1. A circulant construction is also an unrestricted construction, so this lower bound applies to the ordinary Ramsey number.

For the circulant-restricted question

An exact exclusion rules out colourings in the class and orders actually searched. The paper reports eight new circulant values, with constructive certificates and computational exclusions. Changing the graph order also changes the circular distance classes, so one must follow the order-range arguments given in the study.

The results page reports the paper’s results rather than maintaining a live survey of subsequent world records. Its certificates support the lower-bound side. The browser demo checks the small editable examples directly; it does not independently re-run the research checker on every large certificate.

07 / Beyond the main formulation

More than one way to search.

The repository includes an exhaustive circulant engine reimplementing the generation approach of Goedgebeur and Van Overberghe, credited in its documentation. It explores circular-distance choices without an integer programming master problem and provides a second way to investigate and cross-check circulant instances.

Post-paper additions also include a linear-distance model, where the colour depends on |i−j| without wrap-around, and a tabu search for finding candidate colourings. A heuristic can produce a valid construction when its output is verified; failure of a heuristic search cannot establish an exclusion.

These routes serve different purposes. Their settings and results should be identified explicitly rather than pooled as though they were the same computational experiment.

08 / Going further

Follow the code and the evidence.

The research paper is An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs, by Stefano Coniglio, Fabio Furini, Ivana Ljubić, Pablo San Segundo, Johannes Thürauf and Emiliano Traversi.

The branch-and-cut package requires IBM ILOG CPLEX; its currently distributed objects incorporate COPT clique routines. The independent checker does not require CPLEX. Refer to the repository for the actual supported installation and command-line workflow.

Back to the interactive constructions →