An exact computer-assisted certificate for R(5,6)≤84

Article and explanatory supplements

Status and accompanying verification files

The complete verification archive is available at https://github.com/apongracz86/Ramsey56/releases/tag/v1.0-review. The three parts reproduce the article, the worked explanation, and the detailed mathematical specification. The archive verification.tar.xz preserves the verification files and their directory structure. Its SHA-256 digest is

88ded8db2254dec75be80e476d684334a685654e3c5a4108cf9c10422bdd3d67

File names cited in the three parts refer to that distribution. Its README and the specification give the reproduction recipes. The article states the external mathematical inputs. The specification explains the calculations performed by each verification program.

I The article

Graphs, counts, and the statement

All graphs in this paper are finite, undirected, and simple: there are no loops or multiple edges. For a graph $X$, write $V(X)$ for its vertex set, $E(X)$ for its edge set, and $n = |V(X)|$ for its order. For a vertex $v \in V(X)$, its neighborhood $N_X(v)$ is the set of vertices adjacent to $v$, and $d_v = d_X(v) = |N_X(v)|$ is its degree. For $S \subseteq V(X)$, $X[S]$ denotes the induced subgraph: its vertices are $S$ and its edges are all the edges of $X$ with both ends in $S$. The complement $\overline{X}$ has the same vertices and exactly the pairs which are not edges of $X$.

A clique is a vertex set whose distinct vertices are pairwise adjacent; an independent set is a vertex set containing no edge. Define

We also call a member of this family an $(s,r)$-graph of order $n$. The Ramsey number $R(s,r)$ is the least $n$ for which $\mathcal{R}(s,r,n)$ is empty.

We use the following statistics of a graph:

• $e(X) = |E(X)|$, the number of edges;

• $t(X)$, the number of unordered three-element vertex sets inducing a triangle;

• $w(X) = \sum_{v\in V(X)} \binom{d_v}{2}$, the number of choices of a vertex and an unordered pair of its neighbors;

• $q(X) = w(X) - t(X)$.

The pair of neighbors counted by $w(X)$ may itself be adjacent. Thus a triangle contributes three to $w(X)$, while an induced three-vertex path contributes one. Consequently

For a triangle, $(e,t,q) = (3,1,2)$; for a three-vertex path, $(e,t,q) = (2,0,1)$. All these counts are integers. When the graph is specified, we abbreviate them to $e,t,w,q$.

For every vertex $v$ of the graph under discussion, put

These are the induced subgraphs on the neighbors and on the nonneighbors of $v$, respectively; neither contains $v$. Their orders are $d_v$ and $n-1-d_v$. The same definitions apply when $X$ is a smaller graph considered in an intermediate calculation.

The small Ramsey bounds and catalogue completeness are established in the cited sources. The verification programs check the inequalities derived from these inputs and the final contradiction by exact arithmetic.

The route through the proof

Suppose that a counterexample $X \in R(5,6,84)$ exists. We first determine its possible vertex degrees. We then obtain restrictions on the counts $e$, $t$, $q$ in each $A_v$ and $B_v$. The word local refers to these neighborhoods or to smaller specified subsets of $V(X)$.

We write equations that every possible graph $X$ and each of its neighborhoods would have to satisfy. We allow additional solutions that may not come from graphs. This larger system is called a relaxation. An inconsistency in the larger system rules out the existence of graphs as well.

The final system describes the proportions of the different graphs induced by seven-element subsets of $V(X)$. Its contradiction is a weighted sum of valid inequalities. The weights are supplied in the electronic supplement. Understanding why an inequality is valid and checking the arithmetic of its saved weights are separate tasks; the reader’s instructions in Section I.10 explain both.

Degrees and the first counting identity

Let $X \in R(5,6,84)$. For a $v \in V(X)$, a four-clique in $A_v$, together with $v$, would be a five-clique in $X$. An independent six-set in $A_v$ would already be one in $X$. Hence $A_v \in R(4,6,d_v)$. Similarly, an independent five-set in $B_v$, together with $v$, would be an independent six-set in $X$, so $B_v \in R(5,5,83-d_v)$.

The bounds $R(4,6) \le40$ and $R(5,5) \le46$ (see [I.1, Table Ib, p. 7] and [I.2, Theorem 1.1]) now give $d_v \le39$ and $83-d_v \le45$. Thus every vertex has degree 38 or 39. The four possible local families are precisely

If $x$ vertices have degree 39, the sum of the degrees is $38(84-x)+39x=3192+x=2e(X)$. Therefore $x$ is even and $e(X)=1596+x/2$.

The first relation between the two kinds of neighborhoods is

We give the double count, since it is also the first example of the identities used in the proof. In an arbitrary graph of order $n$, each triangle contributes one edge to each of three neighborhoods. Thus $\sum_v e(A_v)=3t(X)$. For an edge $uw$, write $c_{uw}=|N_X(u)\cap N_X(w)|$. The number of vertices adjacent to neither $u$ nor $w$ is $n-d_u-d_w+c_{uw}$. Counting an edge inside a nonneighborhood in this way gives

Here $d_v$ occurs once for each of the $d_v$ edges at $v$, and every triangle contributes one common neighbor to each of its three edges. Subtract $\sum_v e(A_v)$ and use $e(X) = \frac{1}{2}\sum_v d_v$. The result is

Putting $n=84$ proves (I.1). This is the simplified form of [I.3, Theorem 2.2, m = 2], also stated in [I.2, equation (1.2)]. The last term in (I.1) is 152 for degree 38 and 117 for degree 39.

To use this identity we need information about the possible edge and triangle counts inside $A_v$ and $B_v$. The next sections explain where that information comes from, before introducing its numerical bounds.

What the small graph catalogues supply

A complete catalogue for $\mathcal{R}(s,r,m)$ lists one representative of every graph in that family up to isomorphism. Two graphs are isomorphic if a bijection of their vertex sets preserves adjacency. Counts such as $e,t,q$ are unchanged by such a bijection, so one representative suffices for checking an inequality involving these counts. The catalogues used here are supplied on Brendan McKay’s Ramsey-graph page [I.4]. They cover the following families:

Family	Orders or edge classes used
$\mathcal{R}(3,5,m)$	$1 \le m \le13$
$\mathcal{R}(3,6,m)$	$13 \le m \le17$
$\mathcal{R}(4,4,m)$	$5 \le m \le17$
$\mathcal{R}(4,5,24)$	the complete order-24 family
$\mathcal{R}(4,5,m)$, $19 \le m \le23$	26 specified extreme-edge classes

An edge class fixes both the order $m$ and the exact edge count. The last line supplies complete catalogues only for those 26 classes, not for every $(4,5)$-graph on 19 through 23 vertices. The files from r45extreme.tar.gz identify each class by its order and edge count; the packaged distribution contains the extracted graph6 files. The other required edge classes are handled by proved outer bounds, described in Section I.6.

For example, r36_13.g6.gz encodes the complete 13-vertex $(3,6)$ catalogue in compressed graph6 format. Graph6 encodes graph adjacency. The file r36_13.g6.gz.profiles records the distinct tuples $(m,e(Y),t(Y),q(Y))$ extracted from those graphs. Several nonisomorphic graphs may have the same tuple. Once the profile has been computed, a linear inequality in these statistics can be checked on one copy of each distinct profile.

The published small Ramsey bounds used with these data are

and the two bounds used in Section I.2. The $R(4,6)\le40$ result is recorded in the survey [I.1], which attributes the computations to Angeltveit and McKay through personal communications from 2020 and 2024. A separate full publication of that computation is not supplied here. The bound $R(5,5)\le46$ is [I.2, Theorem 1.1].

We also use the edge-count intervals recorded in [I.2, Appendix A, Table 1]:

$m$	19	20	21	22	23	24
$e_{\min}$	57	68	77	88	101	116
$e_{\max}$	92	100	107	114	122	132

These are bounds on every graph in the corresponding $\mathcal{R}(4,5,m)$ family. Every integer edge count between the stated endpoints must be covered in the proof. Absence of a catalogue file is not evidence that an edge class is empty.

For the smaller common-neighborhood cells used later, we also need the established minimum-edge formula for $(3,6)$-graphs on at most 12 vertices, a specialization of [I.6, Theorem 2]. If $Y$ is such a graph of order $c$, the lower bounds are $e(Y) \ge0$ for $0 \le c \le5$, $e(Y) \ge c-5$ for $6 \le c \le10$, and $e(Y) \ge3c-25$ for $11 \le c \le12$. The specification states the additional elementary upper bounds and explains how these give outer profiles when the catalogue range $13 \le c \le17$ does not apply.

The catalogue files are inputs. Their mathematical completeness is accepted from the cited work. Our checks count the supplied records and check their derived profiles. The optional full verification also recomputes the profiles of every supplied graph. Neither operation reproves that the catalogue contains every possible graph.

From possible neighborhoods to a counting system

This section applies to an arbitrary ambient graph $X \in\mathcal{R}(s,r,n)$. It will be used, separately, for the four local families in Section I.2. The notation $A_v$, $B_v$, $d_v$ continues to refer to the neighborhoods and degrees in the currently specified graph $X$.

The construction has three steps. We retain a small number of statistics of each possible neighborhood. We introduce nonnegative variables to record how these possibilities occur around the vertices of $X$. We then impose equations that count the same configurations in two ways.

Profiles and containing polygons

For fixed parameters $s'$, $r'$, $m$ and an integer edge count $\eta$, define