The Irredundance-related Ramsey Numbers $s(3,8)=21$ and $w(3,8)=21$

If, however, the same initialisation process is followed in the context of an $r(3,4,9)$ colouring, as shown in Figure 6(c), Algorithm 1 returns the boolean value False as a result of not being able to compute an $r(3,4,9)$ colouring, because $r(3,4)=9$. Although a conceptually simple algorithm, the ranges of possible values of the smallest unknown Ramsey numbers are currently so large that direct application of Algorithm 1 to determine these Ramsey numbers is not technologically possible. The rapid growth in the number of branches and associated computing times required to determine the Ramsey numbers $r(3,n)$ for $n\in \{3,4,5,6\}$ via Algorithm 1 is, for example, illustrated in Table 3.

There is, however, a better way of initialising the input sets $\mathcal{R}$ and $\mathcal{B}$ to Algorithm 1 than the initialisations shown in Figure 6 (a) and (c). Knowledge about smaller avoidance colourings may be utilised in the initialisations. The subgraph induced in any eventual $r(3,4,9)$ colouring by the vertex subset $\{5,6,7,8,9\}$ in Figure 6(c), for example, is necessarily an $r(3,3,5)$ colouring, for if this were not the case, then the subgraph induced in the $r(3,4,9)$ colouring by the vertex subset $\{1,5,6,7,8,9\}$ would contain either a red triangle or a clique of order $4$ as subgraph, a contradiction. Similarly, the subgraph induced in any eventual $r(3,4,9)$ colouring by the vertex subset $\{2,3,4\}$ in Figure 6(c) is necessarily an $r(2,4,3)$ colouring, for otherwise the subgraph induced in the $r(3,4,9)$ colouring by the vertex subset $\{1,2,3,4\}$ would contain a red triangle as subgraph, again a contradiction. The input sets $\mathcal{R}$ and $\mathcal{B}$ to Algorithm 1 may therefore be initialised, without loss of generality, as shown in Figure 6(d), because there is only one $r(2,4,3)$ colouring (a blue triangle) and only one $r(3,3,5)$ colouring (consisting of a red five-cycle embedded within a blue five-cycle, as shown in Figure 1(d)).

When initialising the input sets $\mathcal{R}$ and $\mathcal{B}$ to Algorithm 1 as shown in Figure 6(d), the branching process illustrated in Figure 7 results, which shows that $r(3,4)\le 9$. In the figure, branching nodes are denoted by circles (containing the edges that are branched upon in coordinate form), while bounding nodes are denoted by rectangles (containing the reasons for contradictions preventing further growth of the tree in the form $i$,$j$!xy which means that the edge $ij$ can be coloured neither red because of reason x in Table 2 nor blue because of reason y in Table 2). Square brackets are used to present lists of edges whose colours are fixed by a branching decision, where a string of the form $i$,$j$Rx means that the edge $ij$ is necessarily red so as to avoid contradicting property x in Table 2, and similarly for blue edges. Angular brackets are used at the top of the tree to present a list of edge colours corresponding to the initialisation of the input sets $\mathcal{R}$ and $\mathcal{B}$ to Algorithm 1, where $i$,$j$B means that edge $ij$ is coloured blue, and similarly for red edges.

Note that because of the extended initialisation in Figure 6(d), the tree in Figure 7 has merely eight branches instead of the $234$ branches that result according to Table 3 when the sparser initialisation in Figure 6(c) is used. But even with the denser initialisation procedure described above, which utilises information about smaller avoidance colourings, the rapid growth in the number of branches and associated computing times required by Algorithm 1 places the computation of most Ramsey numbers of the form $r(3,n)$ for $n>6$ out of the current reach of computing technology. It is, nevertheless, possible to apply the algorithm judiciously in order to determine some of these Ramsey number values, as we show in the next sections.

4. Enumeration of $t(3,8,21)$ colourings

We denote the subgraph of the blue [red, resp.] subgraph of a $t(m,n,p)$-colouring induced by some set $A\subseteq V(K_p)$ by $⟨A{⟩}_{\mathrm{b}\mathrm{l}\mathrm{u}\mathrm{e}}$ [$⟨A{⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$, resp.]. Let $D_i(v)$ [$D_{>i}(v)$ or $D_{\ge i}(v)$, resp.] be the set of vertices at distance $i\in \mathbb{N}$ [at a distance greater than $i$ or at a distance at least $i$, resp.] from some specified vertex $v$ in the red subgraph of a $t(3,n,p)$-colouring. Since we avoid an irredundant set of cardinality $3$ in the blue subgraph, we have the following useful result, adapted from [20].

The following generalisation of the result in Lemma 4(a) is useful.

It follows from [18, Figure 4.1] that $t(3,8,21)$ colourings exist. These colourings have, however, not yet been enumerated. Let $\mathrm{\Xi }$ and $\overline{\mathrm{\Xi }}$ be respectively the red and blue subgraphs of a $t(3,8,21)$ colouring, and denote the minimum and maximum degrees of $\mathrm{\Xi }$ by $\delta (\mathrm{\Xi })$ and $\mathrm{\Delta }(\mathrm{\Xi })$, respectively. Suppose $\xi$ is a vertex of red degree $\mathrm{\Delta }(\mathrm{\Xi })$ in this colouring. Then the colourings in Figures 2–5 are relevant in the context of the $t(3,8,21)$ colouring $(\mathrm{\Xi },\overline{\mathrm{\Xi }})$ as a result of the following observation.

The subgraph $\mathrm{\Xi }$ also has the following properties.

By Corollary 2, we therefore have the bounds $3\le \delta (\mathrm{\Xi })\le \mathrm{\Delta }(\mathrm{\Xi })\le 5$. Note, however, that $\mathrm{\Delta }(\mathrm{\Xi })\ne 3$, for otherwise we would have a cubic graph $\mathrm{\Xi }$ of odd order. Therefore, $$\begin{array}{}\text{(3)}& 4\le \mathrm{\Delta }(\mathrm{\Xi })\le 5.\end{array}$$ The subgraph $⟨D_2(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$ of $\mathrm{\Xi }$ is bipartite by Lemma 4(b). Suppose $⟨D_2(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$ contains $c$ components and denote the bipartitions of these components by $(X_i,Y_i)$ for all $i=1,\dots ,c$. We call a component of the form $(X_i,Y_i)$ an $(|X_i|,|Y_i|)$ component, and we assume, without loss of generality, that $|X_i|\ge |Y_i|$ for all $i=1,\dots ,c$. Define $X={\cup }_{i=1}^c{X}_i$ and $Y={\cup }_{i=1}^c{Y}_i$. Then $|X|\ge |Y|$.

4.1. Four-step enumeration process

Our approach toward enumerating $t(3,8,21)$ colourings consists of the following four steps:

Step 1. For each possible pair $(i,j)$ satisfying $0\le j\le i\le 6$, we determine all non-isomorphic $(i,j)$ components in $D_2(\xi )$. That is, connected, bipartite subgraphs with partite sets of cardinalities $i$ and $j$ satisfying the above inequality chain.

Step 2. We consider each combination of values for the triple $|X|,|Y|,\mathrm{\Delta }(\mathrm{\Xi })$ satisfying the inequalities in Lemma 5 and in (3). These combinations are listed as the eleven subcases in Table 4 where, of course, $\mathrm{\Delta }(\mathrm{\Xi })=|D_1(\xi )|$. In each subcase of the table, we insert red edges in $D_2(\xi )$ according to all permissable combinations of $(i,j)$ component combinations determined in Step 1.

Table 4 Subcases considered in Step 2 of our $t(3,8,21)$ colouring enumeration procedure.

Subcase	$|D_0(\xi )|$	$|D_1(\xi )|$	$|D_2(\xi )|$	$|X|$	$|Y|$	$|D_{>2}(\xi )|$	Reference
I	1	4	11	6	5	5	[21, Table 7]
IIa	1	4	10	6	4	6	[21, Table 8]
IIb	1	4	10	5	5	6	[21, Table 9]
IIIa	1	4	9	6	3	7	[21, Table 10]
IIIb	1	4	9	5	4	7	[21, Table 11]
IVa	1	4	8	6	2	8	[21, Table 12]
IVb	1	4	8	5	3	8	Table 7
IVc	1	4	8	4	4	8	[21, Table 14]
V	1	5	11	6	5	4	[21, Table 15]
VIa	1	5	10	6	4	5	[21, Table 16]
VIb	1	5	10	5	5	5	[21, Table 17]

Step 3. For each of the red subgraphs on $D_2(\xi )$ in Step 2 above, we consider all non-isomorphic ways in which to join vertices in $D_1(\xi )$ to vertices in $D_2(\xi )$ by means of red edges, satisfying the requirements of Corollary 3. The number of these non-isomorphic red-edge connections between $D_1(\xi )$ and $D_2(\xi )$ is given by a Stirling number of the second kind ¹. These cases are pruned by ensuring that the properties in Table 5 are satisfied.

Step 4. For each graph found in Step 3 above, and for each permissible avoidance graph on $D_3(\xi )$ (that is, for each $t(3,4,p)$ colouring in Figures 2–5 in the case where $\mathrm{\Delta }(\mathrm{\Xi })=4$, or for each $t(3,3,p)$ colouring in Figure 1 in the case where $\mathrm{\Delta }(\mathrm{\Xi })=5$), we employ our recursive branching algorithm of §3 to decide the colours of the remaining edges joining vertices in $D_1(\xi )$ to $D_2(\xi )$ as well as edges joining vertices in $D_2(\xi )$ to $D_3(\xi )$, as illustrated in Figure 9. For the branching process we use the bounding properties in Table 6.

It is possible to rule out certain types of components in $⟨D_2(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$. We start, however, by noting that in order to avoid a clique of order $8$ in $⟨\{\xi \}\cup X\cup D_{>3}(\xi ){⟩}_{\mathrm{b}\mathrm{l}\mathrm{u}\mathrm{e}}$, the following result holds.

We also have the following restriction on small components of $⟨D_2(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$.

We similarly have the following restriction on large components of $⟨D_2(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$.

4.2. Results for the case $\mathrm{\Delta }(\mathrm{\Xi })=4$

Suppose $\mathrm{\Delta }(\mathrm{\Xi })=4$. Then $|D_2(\xi )|\le 11$ and $|D_{>2}(\xi )|<t(3,4)=9$ by Lemma 5. Furthermore, $⟨D_{>1}(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$ does not contain a $(4,1)$ component (because of the red degree restriction on each vertex).

The results obtained when applying our four-step enumeration process described above to subcases I–IVc in Table 4 are presented in [21]. Table 7 is reproduced here as an example. In these tables, ${\mathrm{\Phi }}_{\le 2}$ and ${\mathrm{\Phi }}_{\ge 3}$ denote respectively the set of valid $t(3,8,21)$ subcolourings on the vertices in $\{\xi \}\cup D_1(\xi )\cup D_2(\xi )$ and the set of valid $t(3,8,21)$ subcolourings on the vertices in $D_{\ge 3}(\xi )$ found upon completion of Steps 1–3 in our four-step enumeration process of §4.1. Furthermore, $\mathrm{\Phi }$ denotes the set of valid $t(3,8,21)$ subcolourings involving only edges between vertices in $D_1(\xi )$ and $D_2(\xi )$, and between vertices in $D_2(\xi )$ and $D_{\ge 3}(\xi )$, as a result of applying our branching algorithm of §3 (i.e. Step 4 of our four-step enumeration process of §4.1). The times reported in the tables are measured in seconds and represent the times required to carry out the four-step enumeration process on the processor described in the caption of Table 3.

Consider, for example, Subcase IVb(viii) in Table 7. An example of a result obtained upon having applied the first three steps of our four-step enumeration process in this case (i.e. before the branching of Step 4 commences) is shown in Figure 10. Note that one of the two possible $t(3,4,8)$ colourings in Figure 5, namely $G_{36}$, appears as $⟨D_{\ge 3}(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$ in Figure 10. All non-red edges entirely within the sets $D_1(\xi )$, $D_2(\xi )$ and $D_3(\xi )$ are blue, and so are the edges between $\xi$ and $D_2(\xi )$, between $\xi$ and $D_3(\xi )$, and between $D_1(\xi )$ and $D_3(\xi )$. Branching occurs only on the remaining edges between $D_1(\xi )$ and $D_2(\xi )$ as well as on the edges between $D_2(\xi )$ and $D_3(\xi )$, eventually resulting in the $t(3,8,21)$ colouring $H_3$ shown in Figure 11.

4.3. Results for the case $\mathrm{\Delta }(\mathrm{\Xi })=5$

Suppose now $\mathrm{\Delta }(\mathrm{\Xi })=5$. Then $|D_2(\xi )|\le 11$ and $|D_{>2}(\xi )|<t(3,3)=6$ by Lemma 5. Furthermore, we have the following restriction on the number of small components in $⟨D_2(\xi ){⟩}_{\mathrm{r}\mathrm{e}\mathrm{d}}$.

The results obtained upon having applied our four-step enumeration process of §4.1 to subcases V–VIb in Table 4 are presented in [21, Tables 15-17].

4.4. Validation of results

It is known that there is only one $t(3,3,5)$ colouring, two $t(3,4,8)$ colourings, six $t(3,5,11)$ colourings and thirty four $t(3,6,14)$ colourings [6, Table 3]. We validated our computer implementation of the four-step enumeration process described in §4.1 by verifying these results independently. We also verified that the results obtained by this process are independent of the choice of the vertex $\xi$ in each case.

4.5. The sets of $t(3,7,17)$ colourings and $t(3,8,21)$ colourings

A total of 298 $t(3,7,17)$ colourings were uncovered during the enumeration process described in the previous sections. These colourings have not been enumerated before and are available online [22].

Furthermore, a total of six $t(3,8,21)$ colourings were similarly found, as summarised in [21]. Among these colourings there are, however, only three pairwise non-isomorphic colourings — all corresponding to the case where $\mathrm{\Delta }(\mathrm{\Xi })=4$. The red subgraphs of these colourings are shown in Figure 11.

5. The Ramsey numbers $s(3,8)$ and $w(3,8)$

Since the circulant graph $R$ in Figure 12(a) contains no irredundant set of cardinality $8$ and the circulant graph $B$ in Figure 12(b) contains no irredundant set of cardinality $3$, it follows that the pair $(R,B)$ in Figure 12 forms an $s(3,8,20)$ colouring.

It therefore follows by (2) and Table 1 that $$\begin{array}{}\text{(4)}& 21\le s(3,8)\le w(3,8)\le t(3,8)=22.\end{array}$$ Lemma 2 implies that sets of $s(3,8,21)$ and $w(3,8,21)$ colourings may be found from among the set of $t(3,8,21)$ colourings enumerated in §4. The graphs in Figure 11 each contains a minimal dominating (or maximal irredundant) set of cardinality $9$, so that none of these graphs represent $w(3,8,21)$ colourings, or $s(3,8,21)$ colourings, and hence we have the following result in view of (4).