# Study of Exoo’s lower bound for Ramsey number $R(5,5)$

Lachlan Ge, Yasiru Jayasooriya, Alex Qiu, Michael Sun, Victor Yuan

(Date: November 2022)

###### Abstract.

We review Exoo’s 1989 paper, which demonstrates that a lower bound for the
Ramsey number $R(5,5)$ is $43$. We provide an efficient way to verify the
claims in the paper, adding detailed proofs. In particular, we replace the
reference to computer verification by concise arguments. Using our
understanding of the insight behind these proofs, we are also able to analyse
variations of the graph constructions to obtain, for example, colourings of
$K_{43}$ which have very few monochromatic $K_{5}$.

## Introduction

What is the smallest number of people that there can be in a group which
guarantees that there will always be three people who all know each other or
three people who all don’t know each other? This is a well-known puzzle whose
answer is six.

However, if we consider a slightly larger variation and ask “What is the
minimum number of people for which we can guarantee that there exists five
people who all know each other or five people who all don’t know each other?”
then we have a problem whose answer is currently unknown! The answer to this
question is denoted by $R(5,5)$, the Ramsey number $(5,5)$, and determining
its value is an open problem.

There is an amusing quote from Paul Erdős regarding this problem:

> Imagine an alien force, vastly more powerful than us landing on Earth and
> demanding the value of $R(5,5)$ or they will destroy our planet. In that
> case, we should marshal all our computers and all our mathematicians and
> attempt to find the value. But suppose, instead, that they asked for
> $R(6,6)$, we should attempt to destroy the aliens.

It is currently known that $R(5,5)$ is between $43$ (Geoffrey Exoo 1989) and
$48$ (Vigleik Angeltveit and Brendan D. McKay 2017) inclusive and there is
evidence that leads to the following conjecture [2]:

######  Conjecture 0.1 (McKay–Radsizowski).

$R(5,5)=43.$

In 1989 Exoo [1] published a construction which showed:

######  Theorem 0.1 (Exoo).

$R(5,5)\geq 43.$

Exoo’s paper will be the focus of our study. The problem is represented using
a _graph_ , where the vertices represent the people and the edges represent
the relationship between pairs of people. For concreteness, we use a _complete
graph_ , which is a graph where every pair of vertices is joined by an edge.
We then colour every edge in this complete graph one of two colours (either
red or blue) to represent whether each pair of people knows or does not know
each other.

We use the usual notation of $K_{n}$ for a complete graph with $n$ vertices.
In the following sections, we will define a red $K_{5}$ to be a complete graph
with $5$ vertices where all of its edges are red and define a blue $K_{5}$
similarly for blue edges. Also, we will denote an edge in the graph between
vertices $u,v$ by $\operatorname{e}(u,v)$.

In the first section we recall the definition of Exoo’s graph from Exoo’s
original paper. In the other sections, we provide explicit proofs for the
claims whose proofs were omitted in the original paper, making everything self
contained. The highlight of this is showing in Section 5 that no blue
$K_{5}$’s exist in Exoo’s graph, which was left to computer verification in
the original paper.

Section 1: Definition of Exoo’s graph: We recall the contents of Exoo’s paper
and organise them into statements and add some diagrams.

Section 2: Helpful observations: We state and explain some general principles
that have helped to save significant time and effort in calculations and
casework.

Section 3: Red checking: We write a complete proof that there are no red
$K_{5}$’s in Exoo’s graph by reducing it to 3 cases.

Sections 4 and 5: We write a complete proof that there are no blue $K_{5}$’s
in Exoo’s graph.

###  0.1. Acknowledgements

Special thanks to Professors McKay, Radsizowski and Exoo for their helpful
comments and encouragement.

Contributions from Rhianna Kho, Callum Kho, George Chen, Minh Lam, Martin Li,
Nathan Wong, Charlotte Sun, Stefan Lu, Finn McDonald, Ryan Zhang, Leon Zhou,
Andy Shan, Daniel Seo and Liam Celinski.

Comment from MS: The value of this sort of work should not be underestimated.
It is often the case that a result is obtained in research mathematics before
it is fully understood conceptually. This article represents one small but
crucial step in the direction of understanding this result. I would even say
that reaching a complete understanding of why $43$ is the lower bound is
equivalent to resolving the conjecture. There are already so many new and
interesting possibilities from this vantage point that did not exist before.

From an educational perspective, the advantage of having an article like this
is clear: it means that Exoo’s result can now be taught to students in a
meaningful way, which could not have been done before. The nature of the
problem makes it particularly appealing to young students.

##  1\. Definition of Exoo’s graph

First, we define an edge colouring on $K_{43}$. Then, we remove one vertex and
finally change the colour of some edges.

###  1.1. Definition of the colouring for $K_{43}$

Exoo first defined a colouring of $K_{43}$:

######  Definition 1.1 (Cyclic(43)).

Arrange $43$ points equally spaced around a circle and label them from $0$ to
$42$ in clockwise order and in modulo $43$ (so that for all integers $a$, the
vertex $a$ is the same as vertex $a+43$). For any two distinct vertices $a,b$
we define the distance (denoted by $\operatorname{d}(a,b)$) between them as
the length of the minor arc between the vertices (where we define the minor
arc length between adjacent vertices to be $1$).

Note that $\operatorname{d}(a,b)$ can also be defined as the unique integer
${m\in\\{1,\ldots,21\\}}$ such that either ${a-b\equiv m\;(\bmod\;43)}$ or
${b-a\equiv m\;(\bmod\;43)}$.

We will also define the length of an edge to be the distance between the two
vertices that form the edge. Observe that all edge lengths will be between $1$
and $21$ inclusive. The edges will be coloured depending on their lengths, as
shown in the following table, where each length from $1$ to $21$ corresponds
to either the colour red or blue.

Red | 1 | 2 | 7 | 10 | 12 | 13 | 14 | 16 | 18 | 20 | 21
---|---|---|---|---|---|---|---|---|---|---|---
Blue | 3 | 4 | 5 | 6 | 8 | 9 | 11 | 15 | 17 | 19 |

Denote an edge length as a red-length or a blue-length if it corresponds to
the colour red or blue respectively in the table above.

Since this colouring is defined solely using the lengths of each edge, then
this colouring is cyclic over all vertices, so we will denote the graph as
$\operatorname{Cyclic}(43)$.

For illustration purposes, the following diagram shows the colours of the
edges of length $1,7,11$ of $\operatorname{Cyclic}(43)$.

The following proposition and its converse appears in Exoo’s paper [1]. We
prove the converse in Section 3 that the only red $K_{5}$’s in
$\operatorname{Cyclic}(43)$ are the ones listed below. The proof of the
proposition was omitted in the paper because it was trivial but we include it
here for completeness.

######  Proposition 1.1.

For all integers $i$ such that $0\leq i\leq 42$, the $5$-tuple of vertices
${(i,i+1,i+2,i+22,i+23)}$ forms a red $K_{5}$ in $\operatorname{Cyclic}(43)$.
This yields $43$ distinct red $K_{5}$’s.

###### Proof.

We will check for all $0\leq i\leq 42$ that the lengths of the edges between
all ten pairs of vertices in each of the $K_{5}$’s are red-lengths. Below are
the edge lengths in the $i=0$ case.

$\displaystyle\operatorname{d}(0,1)=1.$
$\displaystyle\operatorname{d}(0,2)=2.$
$\displaystyle\operatorname{d}(0,22)=21.$
$\displaystyle\operatorname{d}(0,23)=20.$
$\displaystyle\operatorname{d}(1,2)=1.$
$\displaystyle\operatorname{d}(1,22)=21.$
$\displaystyle\operatorname{d}(1,23)=21.$
$\displaystyle\operatorname{d}(2,22)=20.$
$\displaystyle\operatorname{d}(2,23)=21.$
$\displaystyle\operatorname{d}(22,23)=1.$

Since all the edge lengths are either $1,2,20$ or $21$ (which are all red-
lengths), then this subgraph is a red $K_{5}$. By symmetry, the edge lengths
of the pairs of vertices will be the same for the $K_{5}$’s for all other
values of $i$, so we obtain a red $K_{5}$ for every value of $i$.

For each value of $i$, since vertex $i+1$ is the only vertex in the
corresponding $K_{5}$ whose adjacent vertices are also in the $K_{5}$, then
this shows that the $K_{5}$’s for each value of $i$ are unique. Hence, we have
$43$ distinct $K_{5}$’s.

∎

It is also stated in Exoo’s paper that there are no blue $K_{5}$’s in
$\operatorname{Cyclic}(43)$. We provide a proof in Section 4.

###  1.2. Using $\operatorname{Cyclic}(43)$ to colour $K_{42}$

Here, we recall the definition of Exoo’s graph and introduce some notation.

######  Definition 1.2 ($\operatorname{Exoo}(42)$).

Start with $\operatorname{Cyclic}(43)$, delete the vertex $0$ (which in turn
removes all edges connected to it) and change the colours of the following
sixteen edges.

$\operatorname{e}(4,5)\qquad\operatorname{e}(13,14)\qquad\operatorname{e}(23,24)\qquad\operatorname{e}(39,40)$
$\operatorname{e}(5,6)\qquad\operatorname{e}(14,15)\qquad\operatorname{e}(24,25)\qquad\operatorname{e}(40,41)$
$\operatorname{e}(6,7)\qquad\operatorname{e}(15,16)\qquad\operatorname{e}(30,31)\qquad\operatorname{e}(41,42)$
$\operatorname{e}(7,8)\qquad\operatorname{e}(16,17)\qquad\operatorname{e}(33,34)\qquad\operatorname{e}(11,32)$

We will denote the resulting graph by $\operatorname{Exoo}(42)$.

Note that the colour changes are all from red to blue because they involve
fifteen edges of the red-length $1$ and one edge of the red-length $21$.

The following Lemma is proved in Exoo’s paper.

######  Lemma 1.1.

(LC, VY) The 43 red $K_{5}$’s of Proposition 1.1 are no longer red $K_{5}$’s
in $\operatorname{Exoo}(42)$ due to the colour changes and the removed vertex
$0$.

###### Proof.

From Proposition 1.1 we see that each vertex in $\operatorname{Cyclic}(43)$ is
part of five of the $43$ red $K_{5}$’s. Thus, only $38$ of these red $K_{5}$’s
will remain after deleting vertex $0$.

Recall that the $38$ red $K_{5}$’s consist of the vertices
$\\{i,i+1,i+2,i+22,i+23\\}$ for all integers $i$ where $0\leq i\leq 42$, but
excluding the values of ${i=0,20,21,41,42}$ because vertex $0$ has been
deleted. We now show that the colour changes cause all $38$ of the red
$K_{5}$’s to have an edge turn from red to blue.

  * •

For all $i\in\\{4,5,6,7,13,14,15,16,23,24,30,33,39,40\\}$, the edge
$\operatorname{e}(i,i+1)$ changes colour.

  * •

For all $i\in\\{3,12,22,29,32,38\\}$, the edge $\operatorname{e}(i+1,i+2)$
changes colour.

  * •

For all $i\in\\{1,2,8,11,17,18,19,25,26,27,28,34,35,36,37\\}$, the edge
${\operatorname{e}(i+22,i+23)}$ changes colour.

  * •

For $i=9$, the edge $\operatorname{e}(i+2,i+23)$ (i.e.
$\operatorname{e}(11,32)$) changes colour.

  * •

For $i=10$, the edge $\operatorname{e}(i+1,i+22)$ (i.e.
$\operatorname{e}(11,32)$) changes colour.

  * •

For $i=31$, the edge $\operatorname{e}(i+1,i+23)$ (i.e.
$\operatorname{e}(11,32)$) changes colour.

Hence, the colour changes and the removed vertex $0$ disrupt all $43$ of the
red $K_{5}$’s from Proposition 1.1.

∎

If we combine the above Lemma with a proof that there are no other red
$K_{5}$’s in $\operatorname{Cyclic}(43)$ apart from the $43$ previously listed
ones, then we can conclude there are no red $K_{5}$’s in
$\operatorname{Exoo}(42)$. This is done in Section 3.

##  2\. Helpful observations

######  Lemma 2.1.

In $\operatorname{Cyclic}(43)$ and $\operatorname{Exoo}(42)$, the edge joining
vertices $a$ and $b$ is blue if the difference $|a-b|$ is one of the
following:

$3,4,5,6,8,9,11,15,17,19,24,26,28,32,34,35,37,38,39,40.$

In $\operatorname{Cyclic}(43)$, all other edges are red. In
$\operatorname{Exoo}(42)$, all other edges are red unless the difference is
$1,21,22$ or $42$ in which case the specific edge needs to be checked against
the colour change table.

###### Proof.

The first ten differences are equal to all the blue-lengths. Also, observe
that when the latter ten differences are subtracted from $43$, we obtain all
the blue-lengths, so these differences (which are distances between pairs of
vertices along the major arc) also correspond to blue edges.

By definition, all other edges of $\operatorname{Cyclic}(43)$ are red. In
$\operatorname{Exoo}(42)$, colour changes only occur for certain edges of
length $1$ or $21$. This corresponds to the difference $|a-b|$ being either
$1,21,22$ or $42$ (considering distances along the minor or major arc).

∎

######  Definition 2.1.

Consider a fixed edge $\operatorname{e}(a,b)$ in $\operatorname{Cyclic}(43)$,
We say that two vertices $u,v$ are symmetric with respect to
$\operatorname{e}(a,b)$ if

$a-u\equiv v-b\;(\bmod\;43)$

(or equivalently $a-v\equiv u-b\;(\bmod\;43)$. We say that two sets of
vertices $U,V$ of equal size are symmetric about $\operatorname{e}(a,b)$ if
all the vertices in $U$ can be paired with all the vertices in $V$ such that
the vertices in each pair are symmetric with respect to
$\operatorname{e}(a,b)$.

######  Proposition 2.1 (Symmetry in Colourings).

In $\operatorname{Cyclic}(43)$, suppose that we are given a pair of vertices
($a,b$) and another pair of vertices ($x,y$) satisfying

$x-b\equiv a-y\;(\bmod\;43)$

(or in other words vertices $x,y$ are symmetric with respect to
$\operatorname{e}(a,b)$). Then the edge $\operatorname{e}(x,a)$ has the same
colour as $\operatorname{e}(y,b)$ and the edge $\operatorname{e}(x,b)$ has the
same colour as $\operatorname{e}(y,a)$. In particular, if both
$\operatorname{e}(x,a)$ and $\operatorname{e}(x,b)$ edges are red (resp.
blue), then so are the edges $\operatorname{e}(y,a)$ and
$\operatorname{e}(y,b)$ and vice versa.

###### Proof.

It suffices to show the differences between $x$ and $a,b$ are the same as the
differences between $y$ and $b,a$ respectively (in modulo $43$) since equal
differences imply that the edge lengths are equal and hence have the same
colour.

We are already given that ${x-b\equiv a-y\;(\bmod\;43)}$. By rearranging this,
we obtain ${x-a\equiv b-y\;(\bmod\;43)}$, so we have both of the required
equalities in differences. ∎

This proposition can be applied to a set of vertices $X$ symmetric to a set of
vertices $Y$ about a fixed edge $\operatorname{e}(a,b)$. A practical
consequence of this symmetry is that it reduces the effort required to
determine colours of edges. For example, if the colour of the edge
$\operatorname{e}(x,a)$ is known for some $x\in X$, then if $y\in Y$ is the
symmetric counterpart of $x$, the colour of $\operatorname{e}(y,b)$ can
immediately be deduced to be the same colour as $\operatorname{e}(x,a)$.

In the rest of this article, we will use diagrams like the one below. Here, we
explain some of our conventions.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
      o  xxxx xx x   x x x    x x x   x xx xxxx
         EE E  E       E      E E     E  E EE

The first two rows in the diagram represent the $43$ vertices with the tens
digit on the first row and the units digit on the second row.

Given a fixed colour (blue or red depending on the context), the ‘o’
represents the vertex in question and the x’s represent all the vertices in
$\operatorname{Cyclic}(43)$ which form an edge of the given colour with the
vertex corresponding to ‘o’,

In the example diagram above, the fixed colour is blue. The third row shows
that the vertices which form blue edges with vertex $1$ in
$\operatorname{Cyclic}(43)$ are vertices

${\\{4,5,6,7,9,10,12,16,18,20,25,27,29,33,35,36,38,39,40,41\\}}.$

The fourth row shows that the vertices in $\operatorname{Cyclic}(43)$ which
form blue edges with vertex $3$ are vertices

${\\{6,7,8,9,11,12,14,18,20,22,27,29,31,35,37,38,40,41,42,43\\}}.$

The E’s in the fifth row show overlaps in the x’s in the third and fourth
rows.

One helpful observation is that because we have a cyclic colouring in
$\operatorname{Cyclic}(43)$, the relative positions of the x’s and ‘o’ are
always fixed and we simply have to translate a row cyclically to obtain the
rows corresponding to different vertices labelled with ‘o’. Also, the E’s give
us the information that the vertices that form blue edges with vertices $1$
and $4$ are

${\\{6,7,9,12,18,20,27,29,35,38,40,41\\}}.$

Notice that we can apply our symmetry properties from earlier to see that the
first six of these vertices are symmetric with the last six vertices about
$\operatorname{e}(1,3)$.

We also see in the rows of the diagram that for the blue edges marked by x’s,
there are two blocks of four consecutive vertices and two blocks of pairs of
consecutive vertices. This leads to the following observation.

######  Lemma 2.2.

Let $a$ be an integer such that $0\leq a\leq 42$. There are exactly eight
vertices which form blue edges with both vertex $a$ and $a+1$ in
$\operatorname{Cyclic}(43)$. Moreover, four of these vertices are symmetric
with the other four over edge $\operatorname{e}(a,a+1)$. These eight vertices
have the form

$a+4,a+5,a+6,a+9,a-8,a-5,a-4,a-3\ (\bmod\;43).$

###### Proof.

Without loss of generality, we can assume by cyclic symmetry that $a=1$. In
the below diagram, the fixed colour is set to blue.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
     o  xxxx xx x   x x x    x x x   x xx xxxx
        EEE  E                         E  EEE

The diagram above shows that the vertices that form blue edges with both
vertex $1$ and $2$ are ${\\{5,6,7,10,36,39,40,41\\}}$. These eight vertices
are in the form listed in the lemma.

To check the symmetry, we observe that the positions of vertices
${a+4,a+5,a+6,a+9}$ relative to vertex $a+1$ are $3,4,5,8$ steps clockwise
respectively and the positions of vertices ${a-3,a-4,a-5,a-8}$ relative to
vertex $a$ are $3,4,5,8$ steps anticlockwise respectively.

∎

##  3\. Checking red $K_{5}$’s

We first prove that the only red $K_{5}$’s in $\operatorname{Cyclic}(43)$ are
the $43$ ones claimed by Exoo. By cyclic symmetry, without loss of generality
we only have to consider the red $K_{5}$’s that include vertex $1$. Note that
the distances between successive vertices in a red $K_{5}$ (going clockwise
around the circle) add up to $43$ and there are five such distances. Hence, by
the pigeonhole principle, at least one of the edge lengths in the red $K_{5}$
must be at most $8$.

Hence, we will also assume without loss of generality that there is a vertex
$a$ clockwise of $1$ in the subgraph such that $\operatorname{d}(a,1)\leq 8$
and that $\operatorname{d}(a,1)$ is the smallest distance between any pair of
vertices in the subgraph. Call a red $K_{5}$ standard if it satisfies all
these aforementioned conditions.

######  Lemma 3.1.

(VY, CK) Suppose that vertices $1$ and $2$ belong to a standard red $K_{5}$ in
$\operatorname{Cyclic}(43)$. Then the subgraph must be formed from one of the
three $5$-tuples of vertices ${(1,2,3,23,24)}$, ${(0,1,2,22,23)}$, or
${(22,23,24,1,2)}$. These subgraphs correspond to $i=1,0,22$ respectively in
Proposition 1.1.

###### Proof.

In the following diagrams for this proof, the fixed colour is set to red.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xoxx    x  x xxx x x xxxx x x xxx x  x    x
      E          EE      EEE      EE          E

The diagram shows that the other three vertices that can be in the standard
red $K_{5}$ must be within

${S=\\{0,3,14,15,22,23,24,31,32\\}}$

(noting that vertex $0$ and $43$ are the same).

Case 1 (RK): Vertex $3$ is in the subgraph.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xoxx    x  x xxx x x xxxx x x xxx x  x    x
    xxoxx    x  x xxx x x xxxx x x xxx x  x
                  E       EE       E

The above diagram shows that the remaining vertices in the subgraph must be
within ${\\{15,23,24,32\\}}$. The tuple ${(1,2,3,23,24)}$ forms a possible
subgraph (and is listed in the lemma).

The distances from vertex $23$ to vertices ${15,24,32}$ are $8,1,9$
respectively, of which only $1$ is a red-length. Thus, if vertex $23$ is in
the subgraph, then so must $24$, which gives the tuple mentioned previously.

The distances from vertex $24$ to vertices ${15,23,32}$ are $9,1,8$
respectively. Similarly to before, if vertex $24$ is in the subgraph, then so
must $23$, again giving the same tuple.

The only remaining choice is to include vertices $15,23$ in the subgraph, but
this fails because the edge between them has a blue-length of $8$.

Case 2 (ML): Vertex $14$ is in the subgraph.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xoxx    x  x xxx x x xxxx x x xxx x  x    x
    xx x  x    xxoxx    x  x xxx x x xxxx x x x
                  E        E       E          E

The diagram above shows that the remaining vertices in the subgraph must be
within ${\\{0,15,24,32\\}}$. Observe that the edge lengths for the pairs of
vertices in $\\{0,15,24\\}$ are the blue-lengths ${15,9,19}$. Thus, at most
one of these three vertices can be used and also vertex $32$ must be used.

However, the distances from vertex $32$ to vertices ${0,15,24}$ are
${11,17,8}$ respectively, which are all blue-lengths. Hence, there are no
standard red $K_{5}$’s in this case.

Case 3 (MLam): Vertex $15$ is in the subgraph.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xoxx    x  x xxx x x xxxx x x xxx x  x    x
    xxx x  x    xxoxx    x  x xxx x x xxxx x x
      E          E       E        E

The diagram above shows that the remaining vertices in the subgraph must be
within ${\\{3,14,22,31\\}}$. However, the distances between each pair of these
four vertices are ${11,19,15,8,17,9}$ which all all blue-lengths. Hence, there
are no standard red $K_{5}$’s in this case.

Case 4 (MS): Vertex $22$ is in the subgraph.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xoxx    x  x xxx x x xxxx x x xxx x  x    x
    xx x x xxx x  x    xxoxx    x  x xxx x x xx
                  E       EE       E          E

The diagram above shows that the remaining vertices in the subgraph must be
within ${\\{0,15,23,24,32\\}}$. The distances from vertex $0$ to vertices
${15,23,24,32}$ are ${15,20,19,11}$ respectively, of which only $20$ is a red-
length, so if vertex $0$ is included, then the subgraph must be formed by the
tuple ${(0,1,2,22,23)}$ (which is mentioned in the lemma).

Now assume that vertex $0$ is not included. The distances from vertex $23$ to
vertices ${15,24,32}$ are ${8,1,9}$ respectively, of which only $1$ is a red-
length, so if vertex $23$ is included, then the subgraph must be formed by the
tuple ${(22,23,24,1,2)}$ (which is mentioned in the lemma).

Now assume that vertices $0,23$ are not included. Then we must choose two
vertices from ${\\{15,24,32\\}}$. Since the distances between the pairs of
these three vertices are ${9,17,8}$ which are blue-lengths, then there are no
standard red $K_{5}$’s in this case.

Case 5: Vertex $23$ is in the subgraph.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xoxx    x  x xxx x x xxxx x x xxx x  x    x
    xxx x x xxx x  x    xxoxx    x  x xxx x x x
      E                  E E                  E

The diagram above shows that the remaining vertices in the subgraph must be
within ${\\{0,3,22,24\\}}$. Note that we have already covered the possibility
of vertices $3$ or $22$ being included earlier, so then we only have to
consider the possibility of the remaining two vertices being $0$ and $24$,
which fails because the distance between them is $19$, which is a blue-length.

Case 6: At least one of the vertices $0,24,31,32$ are in the subgraph. Note
that the vertices $0,24,31,32$ are symmetric to the vertices $3,22,15,14$
respectively about $\operatorname{e}(1,2)$. Thus, by symmetry the arguments
used in Cases 1, 2, 3 and 4 can be applied.

In these cases the only valid standard $K_{5}$’s found were those formed from
the tuples ${(1,2,3,23,24)}$, ${(0,1,2,22,23)}$ and ${(22,23,24,1,2)}$.
Therefore, the only standard red $K_{5}$’s in Case 6 must be formed by
considering the symmetrical subgraphs of these three tuples about
$\operatorname{e}(1,2)$, which gives us the tuples ${(0,1,2,22,23)}$,
${(1,2,3,23,24)}$ and ${(22,23,24,1,2)}$ respectively, so we do not obtain any
more new standard red $K_{5}$’s.

Hence, we have covered all cases, where we showed that the only standard red
$K_{5}$’s are formed by the three tuples listed in the lemma. ∎

######  Lemma 3.2.

(AQ,GC) There are no standard red $K_{5}$’s in $\operatorname{Cyclic}(43)$
that contain vertices $1$ and $3$ but not $2$.

###### Proof by AQ.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    xxoxx    x  x xxx x x xxxx x x xxx x  x
     E          E E E E E EE E E E E E

Suppose for the sake of contradiction that there exists a standard red $K_{5}$
that satisfies the conditions. The above diagram (with fixed colour set to
red) shows that apart from the vertex $2$, the vertices that are connected to
both $1$ and $3$ by red edges are

${S=\\{13,15,17,19,21,23,24,26,28,30,32,34\\}}.$

We will partition $S$ into the two sets

$\displaystyle T$ $\displaystyle=\\{13,15,17,19,21,23\\}.$ $\displaystyle U$
$\displaystyle=\\{24,26,28,30,32,34\\}.$

Let $V,W$ be the sets of distances between pairs of vertices in $T$ and $U$
respectively. We obtain

$V=W=\\{2,4,6,8,10\\}.$

Note that the only red-lengths in $V,W$ are $2$ and $10$. Suppose that the
subgraph contains three vertices ${a,b,c\in T}$ such that ${a<b<c}$. Then
$b-a$ and $c-b$ must be either $2$ or $10$, but then the edge length

$\operatorname{d}(a,c)=c-a=(c-b)+(b-a)$

would have be either $4,12$ or $20$, which is a contradiction. Hence, the
subgraph must contain at most two vertices from $T$ and using a similar
argument, the same must be true for $U$. This forces one of $T,U$ to contain
exactly two vertices of the subgraph and the other to contain exactly one
vertex.

Also, observe that $T,U$ are symmetrical about $\operatorname{e}(1,3)$, so we
can assume without loss of generality that $T$ contains exactly two vertices
$a,b$ where $a<b$ and $U$ contains exactly one vertex $c$ from the subgraph.

From earlier, we know that $b-a$ must be either $2$ or $10$. Also, note that

$1\leq c-b<c-a\leq 34-13=21.$

Hence, $\operatorname{d}(c,a)=c-a$ and $\operatorname{d}(c,b)=c-b$. We
therefore obtain

$\operatorname{d}(c,a)-\operatorname{d}(c,b)=(c-a)-(c-b)=b-a=\operatorname{d}(a,b)=2\text{
or }10.$

By observing the values in $T$ and $U$, notice that $\operatorname{d}(c,a)$
and $\operatorname{d}(c,b)$ must both be odd. However, the colour table for
$\operatorname{Cyclic}(43)$ shows that there are no two odd red-lengths that
differ by $2$ or $10$, contradiction.

∎

######  Lemma 3.3.

There are standard no red $K_{5}$’s in $\operatorname{Cyclic}(43)$ that
contain vertices $1$ and $8$ and not the vertices $2$ or $3$.

###### Proof.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    oxx    x  x xxx x x xxxx x x xxx x  x    xx
    x    xxoxx    x  x xxx x x xxxx x x xxx x
                  E     EE E E E EE     E

Suppose for the sake of contradiction that there exists a subgraph that
satisfies the given conditions. The only vertices between $2$ and $7$
inclusive that form red edges with vertex $1$ in $\operatorname{Cyclic}(43)$
are $2,3$. But these vertices cannot be included in this subgraph. From the
“standard” property of the subgraph, the minimum distance between any pair of
vertices in the subgraph must be $7$.

The diagram above (with fixed colour set to red) shows that the remaining
vertices in the subgraph must be within

$S=\\{15,21,22,24,26,28,30,31,37\\}.$

Suppose that vertex $26$ is in the subgraph. Then the minimum distance
criteria gives us that the vertices ${\\{21,22,24,28,30,31\\}}$ cannot be in
the subgraph. But then the only vertices left are $15$ and $37$, so there are
not enough vertices to form the subgraph, contradiction. Hence, the subgraph
cannot contain the vertex $26$.

We can partition the elements of $S$ apart from $26$ into the sets

$\displaystyle T$ $\displaystyle=\\{15,21,22,24\\}.$ $\displaystyle U$
$\displaystyle=\\{28,30,31,37\\}.$

Notice that $T,U$ are symmetrical about $\operatorname{e}(1,8)$, so we can can
assume without loss of generality that the subgraph contains at least two
vertices $a,b$ from $T$ where $a<b$. The minimum distance criteria means that
at most one of vertices $21,22,24$ can be in the subgraph, meaning that we
must have $a=15$. Out of the vertices ${21,22,24}$, the vertex $15$ only forms
a red edge with $22$, so we must have $b=22$.

However, $b$ does not form any red edges with vertices in $U$ because its
distances from these vertices are ${6,8,9,15}$ respectively, which are blue-
lengths. We have reached a contradiction.

∎

######  Lemma 3.4.

The only standard red $K_{5}$’s are formed from the tuples of vertices
${(1,2,3,23,24)}$, ${(0,1,2,22,23)}$, or ${(22,23,24,1,2)}$. These subgraphs
correspond to $i=1,0,22$ respectively in Proposition 1.1.

###### Proof.

By definition, a standard red $K_{5}$ must contain the vertex $1$ and at least
one of the vertices between $2$ and $9$ inclusive. However, the only vertices
in this range that form red edges with vertex $1$ are vertices $2,3,8$.

These cases are all covered in Lemmas 3.1, 3.2 and 3.3, and we only obtain the
three standard red $K_{5}$’s listed above. ∎

######  Lemma 3.5.

There are exactly $43$ red $K_{5}$’s in $\operatorname{Cyclic}(43)$. These are
of the form given in Proposition 1.1.

###### Proof.

Let $A$ be the set of the $43$ red $K_{5}$’s of the form given in Proposition
1.1. From Lemma 3.4 we know that there are exactly three standard red
$K_{5}$’s and these are all in $A$. Hence, all red $K_{5}$’s must be
symmetries of these three subgraphs. It suffices to show $A$ are closed under
all possible rotations or reflections of the vertices in
$\operatorname{Cyclic}(43)$ arranged around the circle.

Closure under rotations is clear from the way the $A$ is defined. For closure
under reflections it suffices to show that the red $K_{5}$ with vertices
${(0,1,2,22,23)}$, when reflected about the axis through vertex $0$ and the
centre of the circle, creates a red $K_{5}$ that is still in $A$. This is
sufficient because we can use additional rotations to show closure of all
elements of $A$ under all possible reflections.

The subgraph that results from this reflection is the red $K_{5}$ with
vertices ${(20,21,41,42,0)}$, which is in $A$ because it corresponds to $i=41$
in Proposition 1.1.

Hence, we obtain that there are no red $K_{5}$’s that are outside of $A$, so
this completes the proof. ∎

######  Theorem 3.1.

There are no red $K_{5}$’s in $\operatorname{Exoo}(42)$.

###### Proof.

This follows from Lemmas 1.1 and 3.5.

∎

##  4\. Checking blue $K_{5}$’s in $\operatorname{Cyclic}(43)$

In this section we prove that there are no blue $K_{5}$’s in
$\operatorname{Cyclic}(43)$. In all the following diagrams, the fixed colour
is set to be blue.

Suppose that for the sake of contradiction there exists a blue $K_{5}$ in
$\operatorname{Cyclic}(43)$ and assume without loss of generality that the
vertex $1$ is part of the blue $K_{5}$.

Using the same pigeonhole principle argument as earlier (for the red
$K_{5}$’s), we can assume that there is a vertex $a$ clockwise of $1$ in the
subgraph such that $\operatorname{d}(a,1)\leq 8$ and $\operatorname{d}(a,1)$
is the smallest distance between any pair of vertices in the subgraph. In a
similar way as earlier, a blue $K_{5}$ standard if it satisfies these
aforementioned conditions.

Using the table of red and blue-lengths, the other four vertices in the graph
(in order to form blue edges with vertex $1$), must come from the set

$S=\\{4,5,6,7,9,10,12,16,18,20,25,27,29,33,35,36,38,39,40,41\\}.$

By symmetry, it suffices to prove that there are no standard blue $K_{5}$’s in
$\operatorname{Cyclic}(43)$. Suppose for the sake of contradiction that a
standard blue $K_{5}$ exists.

By the minimum distance condition, the subgraph must contain a vertex between
$2$ and $9$ inclusive. Of these vertices, the only ones that form blue edges
with vertex $1$ are vertices ${4,5,6,7,9}$.

Case 1: The standard blue $K_{5}$ contains vertex $4$.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
    x  o  xxxx xx x   x x x    x x x   x xx xxx
    xxxx  o  xxxx xx x   x x x    x x x   x xx
    x xxxx  o  xxxx xx x   x x x    x x x   x x
    xx xxxx  o  xxxx xx x   x x x    x x x   x

The overlaps in the third and fourth rows of the diagram above show that the
vertices that form blue edges with vertices $1$ and $4$ are

$K=\\{7,9,10,12,36,38,39,41\\}.$

We can partition $K$ into the sets

$\displaystyle L$ $\displaystyle=\\{7,9,10,12\\}.$ $\displaystyle M$
$\displaystyle=\\{36,38,39,41\\}.$

Notice that $L,M$ are symmetrical about $\operatorname{e}(1,4)$ so we can
assume without loss of generality that the subgraph contains at least two
vertices from $L$.

Suppose that vertex $7$ is chosen. Then the overlaps in the third, fourth and
fifth rows in the diagram show that the only vertices that form blue edges
with vertices ${1,4,7}$ are vertices ${10,12,39,41}$.

Since the distances between pairs of these four vertices are the red-lengths
${\\{2,12,14,16\\}}$, then this shows that vertex $7$ cannot be chosen.

Suppose that vertex $9$ is chosen but not $7$. Then the overlaps in the third,
fourth and sixth rows in the diagram show that the only vertices which form
blue edges with vertices ${1,4,7}$ are vertices $12$ and $41$. Both of these
must be included in order for the subgraph to have five vertices. However the
distance between them is the red-length $14$, so this case also fails.

Thus, the only way for at least two vertices in the subgraph to be from $L$ is
to include vertices $10,12$. However, the distance between them is the red-
length $2$, so this entire case fails.

Case 2: The standard blue $K_{5}$ contains vertex $5$ but not $4$.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
    xx  o  xxxx xx x   x x x    x x x   x xx xx
            EE     E   E        E   E     EE

The above diagram shows that the vertices that form blue edges with vertices
$1$ and $5$ are

$K=\\{9,10,16,20,29,33,39,40\\}.$

We can partition $K$ into the sets

$\displaystyle L$ $\displaystyle=\\{9,10,16,20\\}.$ $\displaystyle M$
$\displaystyle=\\{29,33,39,40\\}.$

Notice that $L,M$ are symmetrical about $\operatorname{e}(1,5)$ so we can
assume without loss of generality that the subgraph contains at least two
vertices from $L$. The only pairs of vertices in $L$ that have blue edges
between them are ${(9,20),(10,16),(16,20)}$. This also means that we cannot
use three vertices from $L$ in the subgraph, so there must be exactly two
vertices from $L$ and exactly one vertex from $M$.

Suppose that vertices $10,16$ are used. Then the distances from vertex $10$ to
the vertices in $M$ are ${19,20,14,13}$ respectively, of which only $19$ is a
blue-length. Thus, the vertex $29$ from $L$ must also be used. However, the
distance between vertex $16$ and $29$ is the red-length $13$, so this case
fails.

Suppose that vertices $9,20$ are used. Then the distances from vertex $9$ to
the vertices in $M$ are ${20,19,13,12}$ respectively, of which only $19$ is a
blue-length. Thus, the vertex $33$ from $L$ must also be used. However, the
distance between vertex $20$ and $33$ is the red-length $13$, so this case
fails.

Suppose that vertices $16,20$ are used. Then the distances from vertex $16$ to
the vertices in $M$ are ${13,17,20,19}$ respectively, of which only $17,19$
are blue-lengths. Thus, either the vertex $33$ or $40$ from $L$ must be used.
However, the distances from vertex $20$ to vertices $33,40$ are the red-
lengths $13,20$, so this case fails.

Hence, there are no standard blue $K_{5}$’s in this case.

Case 3: The standard blue $K_{5}$ contains vertex $6$ but not $5$ or $4$.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
    xxx  o  xxxx xx x   x x x    x x x   x xx x
            EE E            E            E EE

The above diagram shows that the vertices that form blue edges with vertices
$1$ and $6$ are

$K=\\{9,10,12,25,38,40,41\\}.$

In order for the subgraph to satisfy the “standard” criterion, there can be no
vertex of distance less than $5$ to vertex $1$ or $6$ (since vertices $4,5$
are not used). Thus, the vertices ${9,10,40,41}$ cannot be used, so we are
left with vertices ${12,25,38}$, where all three of these must be used.
However, the distance between vertices $12$ and $25$ is the red-length $13$,
so this case fails.

Case 4: The standard blue $K_{5}$ contains vertex $7$ but not $6,5,4$.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
    xxxx  o  xxxx xx x   x x x    x x x   x xx
       E     E E   E E              E E   E E

The above diagram shows that the vertices that form blue edges with vertices
$1$ and $7$ are

$K=\\{4,10,12,16,18,33,35,39,41\\}.$

In order for the subgraph to satisfy the “standard” criterion, there can be no
vertex of distance less than $6$ to vertex $1$ or $7$ (since vertices $4,5,6$
are not used). Thus, the vertices ${4,10,12,39,41}$ cannot be used, so we are
left with vertices ${16,18,33,35}$, where three of them must be used. However,
since the pairs of vertices $(16,18)$ and $(33,35)$ have edges of the red-
length $2$ between them, then at least two of the four vertices cannot be
used, so this case fails.

Case 5: The standard blue $K_{5}$ contains vertex $9$ but not $7,6,5,4$.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    o  xxxx xx x   x x x    x x x   x xx xxxx
    x xxxx  o  xxxx xx x   x x x    x x x   x x
       EEE     E     E E            E E     E

The above diagram shows that the vertices that form blue edges with vertices
$1$ and $9$ are

$K=\\{4,5,6,12,18,20,33,35,41\\}.$

In order for the subgraph to satisfy the “standard” criterion, there can be no
vertex of distance less than $8$ to vertex $1$ or $9$ (since vertices
$4,5,6,7$ are not used). Thus, the vertices ${4,5,6,12,41}$ cannot be used, so
we are left with vertices ${18,20,33,35}$, where three of them must be used.
However, since the pairs of vertices $(18,20)$ and $(33,35)$ have edges of the
red-length $2$ between them, then at least two of the four vertices cannot be
used, so this case fails.

Hence, by exhausting all cases, we have proven that there are no standard blue
$K_{5}$’s in $\operatorname{Cyclic}(43)$, which is sufficient to prove that
there are no blue $K_{5}$’s in $\operatorname{Cyclic}(43)$.

##  5\. Checking blue $K_{5}$’s in $\operatorname{Exoo}(42)$

Since we have proven in the previous section that there are no blue $K_{5}$’s
in $\operatorname{Cyclic}(43)$, in order to prove the same for
$\operatorname{Exoo}(42)$, it suffices to only consider $K_{5}$’s that contain
at least one of the edges involved in the colour changes. We use a general
argument when considering $K_{5}$’s that contain at least one of the fifteen
edges between consecutive vertices that are involved in colour changes and
then afterwards consider the edge $\operatorname{e}(11,32)$.

We first give one example of our general argument for the fifteen blue colour-
changed edges involving consecutive vertices.

######  Example 5.1.

The blue edge $\operatorname{e}(4,5)$ is not part of a blue $K_{5}$ in
$\operatorname{Exoo}(42)$.

###### Proof.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
    x  oX xxxx xx x   x x x    x x x   x xx xxx
    xx XoX xxxx xx x   x x x    x x x   x xx xx
    E      EEE  E                         E  EE

Suppose for the sake of contradiction that there exists a blue $K_{5}$ that
includes $\operatorname{e}(4,5)$. In the above diagram (where the fixed colour
is blue and we include vertex $0$), the uppercase ‘X’ represents the edge
$\operatorname{e}(4,5)$ that underwent a colour change. We see that the
vertices that form blue edges with vertices $4$ and $5$ are

$K=\\{8,9,10,13,39,42,0,1\\}.$

No pair of these vertices are involved in colour changes. We can partition $K$
into the sets

$\displaystyle L$ $\displaystyle=\\{8,9,10,13\\}.$ $\displaystyle M$
$\displaystyle=\\{39,42,0,1\\}.$

Notice that $L,M$ are symmetrical about $\operatorname{e}(4,5)$ so we can
assume without loss of generality that the subgraph contains at least two
vertices from $L$ (there are no colour changes here that affect this
assumption). Since the distances $1$ and $2$ are red-lengths, then at most one
vertex from each of $\\{8,9,10\\}$ and $\\{42,0,1\\}$ can be used. This forces
exactly two vertices from $L$ and exactly one vertex from $M$ to be in the
subgraph.

Also, vertex $13$ from $L$ must be used. The distances from vertex $13$ to
each vertex in $M$ are ${17,14,13,12}$ respectively, of which only $17$ is a
blue-length. Therefore, only vertex $39$ can be used from $M$. However, a
similar argument using symmetry shows that the only vertex from $L$ that can
be used together with $39$ is vertex $13$, so then we cannot pick a fifth
vertex in the subgraph, contradiction.

∎

To generalise the idea in the previous proof, we will show that given any of
the fifteen colour-changed edges between adjacent vertices $a,a+1$ in
$\operatorname{Exoo}(42)$, there are always exactly eight vertices (when
vertex $0$ is included) that form blue edges with $a$ and $a+1$ where four of
the vertices are symmetrical with the other four about
$\operatorname{e}(a,a+1)$.

We also note here that had, say $\operatorname{e}(0,1)$ underwent a colour
change but vertex $0$ had not been deleted, there would be the following blue
$K_{5}$’s formed by vertices ${(0,1,4,5,39)}$ and ${(0,1,4,5,9)}$.

######  Lemma 5.1.

For all $a\in\\{4,5,6,7,13,14,15,16,23,24,30,33,39,40,41\\}$, there are
exactly eight vertices $b$ in $\operatorname{Exoo}(42)$ (when we allow vertex
$0$ to be included) such that edges $\operatorname{e}(a,b)$ and
$\operatorname{e}(a+1,b)$ are both blue (note that edge
$\operatorname{e}(a,a+1)$ is also blue due to the colour changes). These
vertices have the form

$a+4,a+5,a+6,a+9,(a-8),(a-5),(a-4),(a-3)\ (\bmod\;43).$

No pair of these eight vertices belongs to a colour change and the first four
vertices listed are symmetric to the last four about
$\operatorname{e}(a,a+1)$.

###### Proof.

First, note that edges $\operatorname{e}(a,a+2)$ and
$\operatorname{e}(a-1,a+1)$ must be red since their edge lengths are both the
red-length $2$ and also the edges are not involved in colour changes. Thus,
the vertices $a-1$ and $a+2$ cannot be included in our list above. Also, since
neither $a$ nor $a+1$ can be $11$ or $32$, this means that we can apply Lemma
2.2 here because the colour changes do not give us any extra vertices $b$ that
form blue edges with vertices $a$ and $a+1$ apart from the eight ones listed
in that lemma.

It now suffices to check that no pair of these eight vertices are involved in
a colour change. Since no distance between a pair of vertices is large enough
to correspond to edge $\operatorname{e}(11,32)$, it suffices to check the
edges between consecutive vertices. We check these values of $a$ in blocks.

Case 1 (MS, RK, LZ):  $a\in\\{4,5,6,7\\}$. For the vertices $a+4,a+5,a+6$, we
have that they range from $8$ and $13$ inclusive, which fits in the gap
between $\operatorname{e}(7,8)$ and $\operatorname{e}(13,14)$ on the colour
change table. For the vertices $a-5,a-4,a-3$ we have that they can only take
on the values $42,0,1,2,3,4$, which fits in the gap between
$\operatorname{e}(41,42)$ and $\operatorname{e}(4,5)$ on the colour change
table.

Case 2 (YJ, VY):  $a\in\\{13,14,15,16\\}$. For the vertices $a+4,a+5,a+6$, we
have that they range from $17$ and $22$ inclusive, which fits in the gap
between $\operatorname{e}(16,17)$ to $\operatorname{e}(23,24)$ on the colour
change table. For the vertices $a-5,a-4,a-3$ we have that they range from $8$
to $13$ inclusive, which fits in the gap between $\operatorname{e}(7,8)$ and
$\operatorname{e}(13,14)$ on the colour change table.

Case 3 (DS):  $a\in\\{23,24\\}$. For the vertices $a+4,a+5,a+6$ we have that
they range from $27$ to $30$ inclusive, which fits in the gap between
$\operatorname{e}(24,25)$ and $\operatorname{e}(30,31)$ in the colour change
table. For the vertices $a-5,a-4,a-3$ we have that they range from $18$ to
$21$ inclusive, which fits in the gap between $\operatorname{e}(16,17)$ and
$\operatorname{e}(23,24)$ in the colour change table.

Case 4 (LC, CK):  $a\in\\{30,33\\}$. For the vertices $a+4,a+5,a+6$ we have
that they range from $34$ to $39$ inclusive, which fits in the gap between
$\operatorname{e}(33,34)$ and $\operatorname{e}(39,40)$ in the colour change
table. For the vertices $a-5,a-4,a-3$ we have that they range from $25$ to
$30$ inclusive, which fits in the gap between $\operatorname{e}(24,25)$ and
$\operatorname{e}(30,31)$ in the colour change table.

Case 5 (RZ, LG):  $a\in\\{39,40,41\\}$. For the vertices $a+4,a+5,a+6$ we have
that they range from $0$ to $4$ inclusive, which fits in the gap between
$\operatorname{e}(41,42)$ and $\operatorname{e}(4,5)$ in the colour change
table. For the vertices $a-5,a-4,a-3$, we have that they range from $34$ to
$38$ inclusive, which fits in the gap between $\operatorname{e}(33,34)$ and
$\operatorname{e}(39,40)$ in the colour change table.

Hence, there are no colour changes involving consecutive pairs of these eight
vertices.

∎

We also note that the absence of colour changes does not depend on the
deletion of vertex $0$ and only on the colour change table.

######  Theorem 5.1.

The fifteen blue edges of the form $\operatorname{e}(a,a+1)$ in
$\operatorname{Exoo}(42)$ that are involved in colour changes, are not part of
any blue $K_{5}$’s.

###### Proof.

Suppose for the sake of contradiction that such an edge is part of a blue
$K_{5}$. By Lemma 5.1, there are exactly eight vertices that form blue edges
both vertex $a$ and $a+1$. We know that no pair of these eight vertices are
involved in colour changes.

Out of the first four vertices listed in Lemma 5.1, the vertices
${a+4,a+5,a+6}$ are consecutive. In the absence of colour changes, since the
distances of $1,2$ are red-lengths, then at most one of these three vertices
can be in the subgraph.

Since the distance from vertex $a+9$ to the last four vertices are
${17,14,13,12}$ respectively, of which only $17$ is a blue-length, then vertex
$a+9$ only forms a blue edge with $a-8$ out of the last four vertices.

By symmetry, the vertex $a-8$ only forms a blue edge with $a+9$ out of the
first four vertices. Thus, if either vertex $a+9$ or $a-8$ is part of the
subgraph, then both must be present because otherwise we would not have enough
vertices in the subgraph. If neither are in the subgraph, then we again have
insufficient vertices because we can only use one vertex from each of the two
blocks of three consecutive vertices.

Hence, we have reached a contradiction.

∎

######  Proposition 5.1.

The blue edge $\operatorname{e}(11,32)$ is not part of any blue $K_{5}$ in
$\operatorname{Exoo}(42)$.

###### Proof by AQ.

    0        1         2         3         4
    1234567890123456789012345678901234567890123
     xx xxxx  o  xxxx xx x   x x x X  x x x   x 11
       x x x  X x x x   x xx xxxx  o  xxxx xx x 32
         E E      E E        E E      E E     E

Suppose for the sake of contradiction that there exists a blue $K_{5}$ that
includes $\operatorname{e}(11,32)$. In the above diagram (where the fixed
colour is blue), the uppercase ‘X’ represents the edge
$\operatorname{e}(11,32)$ that underwent a colour change. We see that the
vertices that form blue edges with vertices $11$ and $32$ (apart from the
removed vertex $0$) are

$K=\\{6,8,15,17,26,28,35,37\\}.$

We can partition $K$ into the sets

$\displaystyle L$ $\displaystyle=\\{6,8,15,17\\}.$ $\displaystyle M$
$\displaystyle=\\{26,28,35,37\\}.$

Notice that $L,M$ are symmetrical about $\operatorname{e}(11,32)$ so we can
assume without loss of generality that the subgraph contains at least two
vertices from $L$ (there are no colour changes here that affect this
assumption).

Since ${\operatorname{d}(6,8)=\operatorname{d}(15,17)=2}$, which is a red-
length, then at most one of the vertices in each of $(6,8)$ and $(15,17)$ can
be used. Therefore, exactly two vertices in each of $L$ and exactly one from
$M$ must be in the subgraph.

If vertex $6$ is used, observe that the distances from it to each vertex in
$M$ are ${20,21,14,12}$ respectively, which are all red-lengths. Thus, we
cannot select any vertex from $M$, so this case fails.

If vertex $8$ is used, observe that the distances from it to each vertex in
$M$ are ${18,20,16,14}$ respectively, which are all red-lengths. Thus, we
cannot select any vertex from $M$, so this case fails.

Hence, at most one vertex from $L$ can be selected for the subgraph,
contradiction.

∎

This concludes the proof that there are no blue $K_{5}$’s in
$\operatorname{Exoo}(42)$.

##  6\. Further investigations

One benefit of the proofs given in this article is that we can gain a greater
understanding for the reasons for why Exoo’s construction works. Also, the
following questions are now readily accessible:

  1. (1)

If vertex $0$ was not deleted from $\operatorname{Cyclic}(43)$ but the same
colour changes were made, how many red and blue $K_{5}$’s are there?

  2. (2)

Is there a colouring of $K_{43}$ with at most ten monochromatic $K_{5}$’s?

######  Example 6.1.

Define a colouring on $K_{43}$ the same as $\operatorname{Cyclic}(43)$ and
make the same colour changes as in $\operatorname{Exoo}(42)$ but without
deleting vertex $0$. This colouring has exactly four red $K_{5}$’s represented
by the tuples

$(0,1,2,22,23),(0,1,21,22,42),(0,1,21,22,23),(0,20,21,22,42)$

and nine blue $K_{5}$’s represented by the tuples

$\displaystyle(0,6,11,15,32),(0,6,11,17,32),(0,8,11,17,32),$
$\displaystyle(0,11,28,32,37),(0,11,26,32,37),(0,11,26,32,35),$
$\displaystyle(0,11,15,26,32),(0,11,17,26,32),(0,11,17,28,32).$

###### Proof.

The $5$-tuples of vertices $(i,i+1,i+2,i+22,i+23)$ for
${i\in\\{20,21,41,42,0\\}}$ form the five red $K_{5}$’s in
$\operatorname{Cyclic}(43)$ that use vertex $0$. Only the subgraph
corresponding to $i=41$ is no longer a red $K_{5}$ after the colour changes
(specifically, the colour change of $\operatorname{e}(41,42)$).

    0        1         2         3         4
    1234567890123456789012345678901234567890123
     xx xxxx  o  xxxx xx x   x x x X  x x x   x 11
       x x x  X x x x   x xx xxxx  o  xxxx xx x 32
      xxxx xx x   x x x    x x x   x xx xxxx  o
         E E      E E        E E      E E

For the blue $K_{5}$’s, observe that our proof of Theorem 5.1 did not rely on
vertex $0$ being removed, so we only have to search for blue $K_{5}$’s which
include vertex $0$ and edge $\operatorname{e}(11,32)$.

Using the diagram above and our work and notation used in the proof of
Proposition 5.1, note that all the vertices in

$K=\\{6,8,15,17,26,28,35,37\\}$

form blue edges with vertex $0$. Hence, we just have to find two additional
vertices $K$ that have a blue edge between them.

From our earlier work, if vertex $6$ is chosen, then we cannot choose any
vertices from $M$, so we must either choose vertex $15$ or $17$ from $M$. This
gives us the first two tuples listed, since $\operatorname{e}(6,15)$ and
$\operatorname{e}(6,17)$ have lengths $9,11$ respectively, which are blue-
lengths.

If vertex $8$ is chosen, we similarly cannot choose any vertices from $M$, so
we must either choose vertex $15$ or $17$ from $M$. This gives us the third
tuple listed, since $\operatorname{e}(8,15)$ and $\operatorname{e}(8,17)$ have
lengths $7,9$ respectively, where only $9$ is a blue-length.

If vertex $37$ is used, since it is symmetrical with vertex $6$ about
$\operatorname{e}(11,32)$, we obtain the fourth and fifth tuples listed (which
are symmetrical with the first two tuples respectively).

If vertex $35$ is used, since it is symmetrical with vertex $8$ about
$\operatorname{e}(11,32)$, we obtain the sixth tuple listed (which is
symmetrical with the third tuple).

If none of these four vertices are used, note that the distances between pairs
of vertices in $\\{15,17,26,28\\}$ are one of ${2,9,11,13}$, where only $9$
and $11$ are blue-lengths, which corresponds to the pairs of vertices
$(15,26)$, $(17,26)$, $(17,28)$. These give us the seventh, eighth and ninth
tuples listed respectively.

∎

######  Example 6.2.

Define a colouring on $K_{43}$ the same as $\operatorname{Cyclic}(43)$ and
make the same colour changes in $\operatorname{Exoo}(42)$ but without deleting
vertex $0$ but also change the colour of $\operatorname{e}(21,22)$ to blue.
The resulting graph has one red $K_{5}$ and eight blue $K_{5}$’s.

This leads naturally to the following questions:

Questions:

  1. (1)

If vertex $0$ was not deleted from $\operatorname{Cyclic}(43)$ but you are
free to make colour changes from red to blue, what is the minimum number of
monochromatic $K_{5}$’s you can achieve?

  2. (2)

What is the fewest number of monochromatic $K_{5}$’s possible for a colouring
of $K_{43}$?

If the answer to the last question listed is non-zero then the conjecture is
true, otherwise the conjecture is false.

If the conjecture is true, then this number would be what is known as the
Ramsey multiplicity of $K_{5}$. See for example [3], where the Ramsey
multiplicity of $K_{4}$ is shown to be $9$.

It has been remarked by Exoo in unpublished work that he has come across an
example with only two monochromatic $K_{5}$’s.

## References

  * [1] G. Exoo A Lower Bound for $R(5,5)$. Journal of Graph Theory. 13 (1989), No.1, 97-98.
  * [2] B. D. McKay and S. P. Radziszowski, Subgraph counting identities and Ramsey numbers, J. Combinatorial Theory, Ser. B, 69 (1997) 193–209.
  * [3] K. Piwakowski and S. P. Radziszowski, The Ramsey multiplicity of $K_{4}$, Ars Combinatoria, 60 (2001) 131–135.

Dr Michael Sun’s School of Maths, Sydney, Australia


# MFO Report: The dry ten Martini problem for Sturmian dynamical systems

Ram Band, Siegfried Beckus, Raphael Loewy  Department of Mathematics
Technion - Israel Institute of Technology
Haifa, Israel<EMAIL_ADDRESS>Institute of Mathematics
University of Potsdam
Potsdam, Germany<EMAIL_ADDRESS>Department of Mathematics
Technion - Israel Institute of Technology
Haifa, Israel<EMAIL_ADDRESS>
###### Abstract.

This extended Oberwolfach report (to appear in [BCDS]) announces the full
solution to the Dry Ten Martini Problem for Sturmian Hamiltonians [BBL23].
Specifically, we show that all spectral gaps of Sturmian Hamiltonians (as
predicted by the gap labeling theorem) are open for all nonzero couplings and
all irrational rotations. We present here the proof strategy.

Are all possible spectral gaps, predicted by the gap labeling theorem, open
for a given Schrödinger operator? This is the so called Dry Ten Martini
problem (Dry TMP) motivated by the Ten Martini Problem (TMP). The name TMP was
coined by Simon [Sim82] after Kac offered in 1981 ten Martinis to anyone who
solves it. Originally, the TMP was proposed for the Almost Mathieu operator
conjecturing Cantor spectrum for all couplings and all irrational frequencies.
The TMP for the Almost Mathieu operator was solved by Avila and Jitomirskaya
[AJ09]. Recently, Avila, You and Zhou [AYZ23] also solved the Dry Ten Martini
Problem in the non-critical case for the Almost-Mathieu operator.

Sturmian dynamical systems are closely related dynamical systems while
reflecting the aperiodicity coming from a solid and not from a magnetic field.
These systems are used to define a one-dimensional Schrödinger operator
$H_{\alpha,V}:\ell^{2}({\mathbb{Z}})\to\ell^{2}({\mathbb{Z}})$,

$(H_{\alpha,V}\psi)(n)=\psi(n-1)+\psi(n+1)+V\chi_{[1-\alpha,1)}(\\{n\alpha\\})\psi(n),\qquad\psi\in\ell^{2}({\mathbb{Z}}),\,n\in{\mathbb{Z}},$

where $\\{n\alpha\\}:=n\alpha-\lfloor n\alpha\rfloor$ is the fractional part
of $n\alpha$. The potential above is characterized in terms of two parameters:
a frequency parameter $\alpha\in[0,1]$ and the potential strength, also known
as the coupling constant $V\in{\mathbb{R}}$. Since $H_{\alpha,V}$ is a linear,
self-adjoint and bounded operator, its spectrum $\sigma(H_{\alpha,V})$ is a
compact subset of ${\mathbb{R}}$. The family of Schrödinger operators
$H_{\alpha,V}$ for $\alpha\in[0,1]\setminus{\mathbb{Q}}$ and $V\neq 0$ is
called Sturmian Hamiltonians or Kohmoto model. The so-called Kohmoto butterfly
is the corresponding plot of the spectra of $H_{\alpha,V}$ as it varies with
$\alpha$, see Figure 1.

Figure 1. Kohmoto butterfly for $V=2$: The vertical axis represents the
frequency values $\alpha$. For each $\alpha$ the spectrum of $H_{\alpha,V}$ is
plotted horizontally. A few spectra $H_{\frac{p}{q},V}$ are colored for
$\frac{p}{q}\in\big{\\{}\frac{0}{1},\frac{1}{1},\frac{1}{2},\frac{2}{3},\frac{3}{5},\frac{5}{8}\big{\\}}$
representing the first periodic approximations of the Fibonacci Hamiltonian.
According to Definition 3, $A$-type bands ($B$-type bands) are colored blue
(red).

The integrated density of states (IDS) $N_{\alpha,V}:{\mathbb{R}}\to[0,1]$ is
defined by

$N_{\alpha,V}(E):=\lim_{n\to\infty}\frac{\sharp\big{\\{}\lambda\in\sigma\big{(}H_{\alpha,V}|_{[1,n]}\big{)}\,\big{|}\,\lambda\leq
E\big{\\}}}{n},\qquad E\in{\mathbb{R}},$

where $H_{\alpha,V}|_{[1,n]}$ is the $n\times n$ matrix obtained by
restricting $H_{\alpha,V}$ to $\ell^{2}(1,\ldots,n)$, see e.g. [BBG92, DF22]
for more details. In particular, the IDS for Sturmian Hamiltonians satisfies
the following properties:

  1. (IDS1)

$N_{\alpha,V}:{\mathbb{R}}\to[0,1]$ is monotone increasing and continuous,

  2. (IDS2)

$E\in{\mathbb{R}}\setminus\sigma(H_{\alpha,V})$ if and only if there exists an
$\varepsilon>0$ such that the restriction
$N_{\alpha,V}|_{(E-\varepsilon,E+\varepsilon)}$ is constant.

A connected component $g:=(a,b)$ in
${\mathbb{R}}\setminus\sigma(H_{\alpha,V})$ is called a spectral gap, i.e.
$a,b\in\sigma(H_{\alpha,V})$ and $(a,b)\cap\sigma(H_{\alpha,V})=\emptyset$. By
(IDS1) and (IDS2), we have $N_{\alpha,V}(E)=N_{\alpha,V}(E^{\prime})$ for all
$E,E^{\prime}\in[a,b]$. The value $N_{\alpha,V}(E)$ for some (any) $E\in g$ is
called the gap label of $g$. The gap labeling theorem [BBG92] prescribes all
the possible labels that the spectral gaps of $H_{\alpha,V}$ may have.
Specifically, for Sturmian Hamiltonians, we have

$\\{N_{\alpha,V}(E)\,|\,E\in{\mathbb{R}}\setminus\sigma(H_{\alpha,V})\\}\subseteq\big{\\{}\\{n\alpha\\}\,|\,n\in{\mathbb{Z}}\big{\\}}\cup\\{1\\},$

where $\\{n\alpha\\}$ is the fractional part of $n\alpha$ as above. One may
ask whether the latter inclusion is an equality - this is the Dry Ten Martini
Problem for Sturmian dynamical systems. A complete solution of this problem
appears in [BBL23] (see also [MWL] for the first announcement).

######  Theorem 1 (Sturmian Dry TMP).

For all $\alpha\in[0,1]\setminus{\mathbb{Q}}$ and all $V\neq 0$, all possible
spectral gaps of $H_{\alpha,V}$ are open, i.e.

$\\{N_{\alpha,V}(E)\,|\,E\in{\mathbb{R}}\setminus\sigma(H_{\alpha,V})\\}=\big{\\{}\\{n\alpha\\}\,|\,n\in{\mathbb{Z}}\big{\\}}\cup\\{1\\}.$

Let us shortly discuss the progress that has been done so far towards a
resolution of the Sturmian Dry TMP. For large couplings, $V>4$, the previous
theorem was proven by Raymond [Ray97] (see also [BBBT23] for a review). For
the Fibonacci Hamiltonian ($\alpha$ equals to the golden mean
$\varphi:=\frac{\sqrt{5}-1}{2}$), Damanik and Gorodetski proved that all gaps
are open for sufficiently small values of the coupling constant $V$, see
[DG11, Theorem 1.5]. This (small coupling result) was extended by Mei in
[Mei14, Theorem 1.5] to all $\alpha\in[0,1]\setminus{\mathbb{Q}}$ with
eventually periodic continued fraction expansion. Later, Damanik, Gorodetski
and Yessen provided a complete solution for the Fibonacci Hamiltonian in
[DGY16, Theorem 1.3]. One might extend this result to all irrational
$\alpha$’s with eventually periodic continued fraction expansion, confer
[DGY16, Section 7]. In the latter work it was also conjectured that the
Sturmian Dry TMP is true for all irrational $\alpha\in[0,1]$ and couplings
$V\neq 0$.

The rest of the note presents the main strategy of the proof of Theorem 1 in
five steps.

## Step I: Spectra of periodic approximations

Let $\alpha\in[0,1]\setminus{\mathbb{Q}}$. Then the continued fraction
expansion of $\alpha$ is given by the unique sequence $a_{k}\in{\mathbb{N}}$
for $k\geq 0$ satisfying

$\alpha=a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{\ddots}}}=:[a_{0},a_{1},a_{2},\ldots].$

For $k\geq 0$, we also consider the Diophantine approximations
$\alpha_{k}:=[0,a_{1},\ldots,a_{k}]=\frac{p_{k}}{q_{k}}$ (where
$p_{k},q_{k}\in{\mathbb{N}}$ are coprime). We refer to these as finite
continued fraction expansions.

Since $\alpha_{k}\in{\mathbb{Q}}$, the operator $H_{\alpha_{k},V}$ is
periodic. Thus, the spectrum $\sigma(H_{\alpha_{k},V})$ is a finite union of
exactly $q_{k}$ intervals by the Floquet-Bloch theory. These intervals of
$\sigma(H_{\alpha_{k},V})$ are called spectral bands. Moreover, we have the
following result [BIST89, BIT91, Ray97].

######  Proposition 2 (Spectral approximations).

Let $V>0$, $\alpha\in[0,1]\setminus{\mathbb{Q}}$ and
$\alpha_{k}=[0,a_{1},\ldots,a_{k}]$ for $k\in{\mathbb{N}}$. Define the compact
sets

$\Sigma_{k,V}:=\sigma(H_{\alpha_{k},V})\cup\sigma(H_{\alpha_{k+1},V})\subseteq{\mathbb{R}},\qquad
k\in{\mathbb{N}}.$

Then $\Sigma_{k+1,V}\subseteq\Sigma_{k,V}$ and

$\lim_{k\to\infty}\Sigma_{k,V}=\bigcap_{k\in{\mathbb{N}}}\Sigma_{k,V}=\sigma(H_{\alpha,V})$

where the limit is taken with respect to the Hausdorff metric on the compact
subsets of $\mathbb{R}$.

We refer the reader to Figure 1, which demonstrates the first few periodic
approximations of the Fibonacci Hamiltonian
($\alpha=\varphi=[0,1,1,1,1,\ldots]$).

######  Remark.

A more general result is proven in [Ray97]. Here, we provide a simplified
version, which is sufficient to present our proof strategy.

## Step II: Combinatorial structure of the spectral approximations

The monotone convergence in Proposition 2 allows to classify the spectral
bands into two types.

######  Definition 3.

A spectral band $I(V)$ in $\sigma(H_{\alpha_{k},V})$ is called

  * •

of type A if it is strictly contained in a spectral band of
$\sigma(H_{\alpha_{k-1},V})$;

  * •

of type B if it is not of type A and it is strictly contained in a spectral
band of $\sigma(H_{\alpha_{k-2},V})$;

######  Remark.

We note that the analogous notions of types $A$ and $B$ appearing in [BBBT23,
BBL23] are different than those in Definition 3, even though both are
equivalent. The different definition there is essential to prove the next
theorem.

To state the next result, we define an order relation on spectral bands.
Specifically, $[a,b]\prec[c,d]$ holds if $a<c$ and $b<d$. With this at hand,
we have the following (see Figure 2 (b)).

(a)(b)$\alpha_{1}$$B$$\alpha_{0}$$A$$-2$$2$root$\mathbb{R}$$\alpha_{k+2}$$B$$K^{(1)}$$B$$K^{(2)}$$B$$K^{(3)}$$B$$K^{(p)}$$B$$K^{(p+1)}$$\alpha_{k+1}$$A$$J^{(1)}$$A$$J^{(2)}$$A$$J^{(p)}$$\alpha_{k}$$A\
{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}/}\
{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}B}$$I(V)$
Figure 2. (a) The root of the tree $T$ and two adjacent vertices. (b) The
interval $I(V)$ of $\sigma(H_{\alpha_{k},V})$ and the spectral bands of
$\sigma(H_{\alpha_{k+1},V})$ and $\sigma(H_{\alpha_{k+2},V})$ that it
includes.

######  Theorem 4.

Let $V>0$, $\alpha\in[0,1]\setminus{\mathbb{Q}}$ and
$\alpha_{k}=[0,a_{1},\ldots,a_{k}]$ for $k\in{\mathbb{N}}$. Then the following
assertions hold.

  1. (a)

Each spectral band $I(V)$ in $\sigma(H_{\alpha_{k},V})$ is either of type A or
of type B.

  2. (b)

Let $I(V)$ be a spectral band in $\sigma(H_{\alpha_{k},V})$ and

$p:=\begin{cases}a_{k+1}-1,\qquad&\text{if $I(V)$ is of type $A$},\\\
a_{k+1},\qquad&\text{if $I(V)$ is of type $B$}.\end{cases}$

Then there exist

     * •

$p$ spectral bands $J^{(1)},\ldots,J^{(p)}$ of type A in
$\sigma(H_{\alpha_{k+1},V})$, and

     * •

$p+1$ spectral bands $K^{(1)},\ldots,K^{(p+1)}$ of type B in
$\sigma(H_{\alpha_{k+2},V})$

that are all strictly contained in $I(V)$ and they interlace

$K^{(j)}\prec J^{(j)}\prec K^{(j+1)},\qquad 1\leq j\leq p.$

######  Remark.

We point out that in the interlacing property spectral bands may overlap (as
in Figure 2 (b)) for small couplings $V$, which is not the case in [Ray97].
These overlaps are the source of the difficulty in proving the statement for
small couplings. This issue is resolved in [BBL23] by combining trace maps
together with a new viewpoint – applying an interlacing theorem to matrix
eigenvalues of the periodic approximations. Another crucial ingredient is
changing the perspective from considering a single approximation
$(\alpha_{k})_{k\in\mathbb{N}}$ to the analysis over the whole space of all
finite continued fraction expansions simultaneously using a two-level
induction.

## Step III: The spectrum as the boundary of an infinite tree

Theorem 4 allows us to construct a (directed) tree $T$ whose vertices
represent the spectral bands. The rules that uniquely define $T$ in terms of
$[0,a_{1},a_{2},a_{3},\ldots]$ are sketched in Figure 2.

Specifically, each vertex has a type (A or B) according to the spectral band
it represents, which is well-defined by Theorem 4 (a). The root of this tree
and the two vertices to which the root is connected are sketched in Figure 2
(a). Then, for each vertex at level $k$ (which is a spectral band $I(V)$ of
$H_{\alpha_{k},V})$), we connect it with a directed edge to each of the
vertices (spectral bands) $J^{(1)},\ldots,J^{(p)}$ of type A and
$K^{(1)},\ldots,K^{(p+1)}$ of type B, see Theorem 4. We emphasize that the
combinatorial data in Theorem 4 – leading to the construction of the tree –
depends only on the infinite continued fraction expansion of $\alpha$ and is
independent of $V>0$. An example of such a tree is provided in Figure 3.

We denote by $\gamma:=(I_{-1},I_{0},I_{1},I_{2},I_{3},\ldots)$ an infinite
path that starts at the root $I_{-1}={\mathbb{R}}$, where $I_{m}$ are vertices
in $T$ satisfying $I_{m}\to I_{m+1}$ (meaning $I_{m+1}$ is strictly included
in $I_{m}$) for all $m\geq-1$. Then the boundary of the tree $\partial T$ is
the set of all such infinite paths. We have the following correspondence
between $\partial T$ and $\sigma(H_{\alpha,V})$.

######  Proposition 5.

Let $V>0$ and $\alpha\in[0,1]\setminus{\mathbb{Q}}$. Then there exists a
surjective map

$E_{V}:\partial T\to\sigma(H_{\alpha,V}),\quad\gamma\mapsto E_{V}(\gamma).$

Proof outline. We start by making the following observation. Even though the
combinatorial structure of the tree does not depend on $V>0$, each vertex $I$
in its own represents a particular spectral band $I(V)$ depending on $V$. We
now explicitly construct the map $E_{V}$.

Let $V>0$ and $\gamma=(I_{-1},I_{0},I_{1},I_{2},\ldots)\in\partial T$. Since
$\gamma$ is a path, we have $I_{m}\to I_{m+1}$ for all $m\geq-1$. By
definition of the tree $T$, this implies $I_{m+1}(V)\subseteq I_{m}(V)$ for
all $m\geq-1$. Thus, the intersection $\bigcap_{m\geq-1}I_{m}(V)$ is non-
empty. By Proposition 2, this intersection is contained in
$\sigma(H_{\alpha,V})$. Actually, this intersection contains exactly one
point: assume by contradiction that there are two different points $E_{1}\neq
E_{2}$ in $\bigcap_{m\geq-1}I_{m}(V)$. Since we have an intersection of
intervals, we conclude

$\text{Leb}\big{(}\sigma(H_{\alpha,V})\big{)}\geq|E_{1}-E_{2}|>0,$

where Leb denotes the Lebesgue measure. This contradicts
$\text{Leb}\big{(}\sigma(H_{\alpha,V})\big{)}=0$ proven in [BIST89]. Thus,
there is a unique $E_{V}(\gamma)\in\sigma(H_{\alpha,V})$ such that
$\cap_{m\geq-1}I_{m}(V)=\\{E_{V}(\gamma)\\}$. This defines our map $E_{V}$.

Finally, one can conclude the surjectivity of $E_{V}:\partial
T\to\sigma(H_{\alpha,V})$ by the monotone convergence of the spectra, see
Proposition 2. $\Box$

We note that classifying spectral bands into a few types and using a tree
encoding to identify open gaps was also used recently in [LQX22, Theorem 1.11]
for the period doubling Hamiltonian.

$\sigma(H_{\alpha,V})$$[0,1,2,4]$$A$$A$$A$$A$$B$$A$$A$$A$$B$$A$$A$$A$$B$$[0,1,2]$$B$$A$$A$$[0,1]$$B$$[0]$$A$root
Figure 3. An example of a tree for the continued fraction expansion
$[0,1,2,4,\ldots]$ is sketched. A specific infinite path starting at the root
and approaching a point in the spectrum is indicated in brown (see Proposition
5).

## Step IV: The IDS as a function of the tree boundary $\partial T$

We start by observing that in the definition of the IDS,

$N_{\alpha,V}(E):=\lim_{n\to\infty}\frac{\sharp\big{\\{}\lambda\in\sigma\big{(}H_{\alpha,V}|_{[1,n]}\big{)}\,\big{|}\,\lambda\leq
E\big{\\}}}{n},\qquad E\in{\mathbb{R}},$

the Dirichlet boundary conditions in $H_{\alpha,V}|_{[1,n]}$ can be replaced
by periodic boundary conditions. This change might modify the numerator, but
will not affect the limit. Thus, counting eigenvalues below $E$ may be
replaced with counting spectral bands of $H_{\alpha_{k},V}$ that lie to the
left of $E$. Together with some combinatorial information proven in [Ray97],
one concludes the following.

######  Proposition 6.

Let $V>0$, $\alpha\in[0,1]\setminus{\mathbb{Q}}$ and
$\alpha_{k}=[0,a_{1},\ldots,a_{k}]=\frac{p_{k}}{q_{k}}$. For each
$\gamma\in\partial T$, there are $\pi_{k}(\gamma)\in\\{0,\ldots,a_{k+1}\\}$
for $k\geq-1,$ such that

$N_{\alpha,V}\big{(}E_{V}(\gamma)\big{)}=-\alpha+\sum_{k=-1}^{\infty}(-1)^{k}\pi_{k}(\gamma)(q_{k}\alpha-
p_{k}).$

By the right hand side of the previous equation, it is apparent that the value
$N_{\alpha,V}\big{(}E_{V}(\gamma)\big{)}$ depends only on $\gamma$ and is
independent of $V>0$. Interestingly, the values $\pi_{k}(\gamma)$ for
$k\geq-1$ are explicitly described by local properties of $\gamma$ at level
$k$ of the tree, see [Ray97, BBBT23].

## Step V: Identifying a gap label within the tree

With Proposition 6 at hand and knowing $\pi_{k}(\gamma)$ explicitly, one can
inductively prove the following statement.

######  Proposition 7.

Let $V>0$, $\alpha\in[0,1]\setminus{\mathbb{Q}}$ and $n\in{\mathbb{Z}}$. Then
there exist two different paths $\gamma,\eta\in\partial T$ such that

$N_{\alpha,V}\big{(}E_{V}(\gamma)\big{)}=N_{\alpha,V}\big{(}E_{V}(\eta)\big{)}=\\{n\alpha\\}.$

Recall that the IDS is monotonically increasing, continuous and it is only
constant within spectral gaps, confer (IDS1) and (IDS2). Thus, if there are
two different $E_{1},E_{2}\in\sigma(H_{\alpha,V})$ satisfying

$N_{\alpha,V}\big{(}E_{1}\big{)}=N_{\alpha,V}\big{(}E_{2}\big{)}=\\{n\alpha\\},$

then $(E_{1},E_{2})$ is an open spectral gap of $\sigma(H_{\alpha,V})$ with
gap label $\\{n\alpha\\}$. In light of this, Theorem 1 follows from
Proposition 7, once we prove that $E_{V}:\partial T\to\sigma(H_{\alpha,V})$ is
injective.

######  Theorem 8.

For all $V>0$, the map $E_{V}:\partial T\to\sigma(H_{\alpha,V})$ is injective.

For $V>4$, Theorem 8 was proven by Raymond [Ray97]. The proof of the statement
for $V>0$ can be found in [BBL23]. The extra difficulty in extending the
result from $V>4$ to $V>0$ comes from possible overlaps of spectral bands,
which do not belong to the same path (see also remark after Theorem 4).
Nevertheless, it is possible to control these overlaps uniformly over the
whole space of all finite continued fraction expansions.

Proof of Theorem 1. As was already mentioned above Theorem 1 follows for $V>0$
by combining Proposition 7 and Theorem 8. In order to extend this result to
$V<0$, one observes that the spectrum $H_{\alpha_{k},V}$ is antisymmetric with
respect to $V\mapsto-V$. This yields now
$\sigma(H_{\alpha,-V})=-\sigma(H_{\alpha,V})$ and
$N_{\alpha,-V}(-E)=1-N_{\alpha,V}(E)$, which completes the proof of Theorem 1.
$\Box$

## References

  * [AJ09] A. Avila and S. Jitomirskaya, _The Ten Martini Problem_ , Ann. of Math. (2) 170 (2009), no. 1, 303–342. MR 2521117
  * [AYZ23] A. Avila, J. You, and Q. Zhou, _Dry Ten Martini Problem in the non-critical case_ , 2023, arXiv:2306.16254.
  * [BBBT23] R. Band, S. Beckus, B. Biber, and Y. Thomas, _Sturmian Hamiltonians for large couplings - a review of a work by L. Raymond_ , 2023+, In preparation.
  * [BBG92] J. Bellissard, A. Bovier, and J.-M. Ghez, _Gap labelling theorems for one-dimensional discrete Schrödinger operators_ , Rev. Math. Phys. 4 (1992), no. 1, 1–37. MR 1160136
  * [BBL23] R. Band, S. Beckus, and R. Loewy, _The Dry Ten Martini Problem for Sturmian Hamiltonians_ , 2023+, In preparation.
  * [BCDS] M. Baake, M. I. Cortez, D. Damanik, and N. Strungaru, Proceeding of the MFO Workshop 2335: Aspects of Aperiodic Order, 27 Aug. - 1 Sep. 2023.
  * [BIST89] J. Bellissard, B. Iochum, E. Scoppola, and D. Testard, _Spectral properties of one-dimensional quasi-crystals_ , Comm. Math. Phys. 125 (1989), no. 3, 527–543. MR 1022526 (90m:82043)
  * [BIT91] J. Bellissard, B. Iochum, and D. Testard, _Continuity properties of the electronic spectrum of $1$D quasicrystals_, Comm. Math. Phys. 141 (1991), no. 2, 353–380. MR 1133271 (92j:81037)
  * [DF22] D. Damanik and J. Fillman, _One-dimensional ergodic Schrödinger operators—I. General theory_ , Graduate Studies in Mathematics, vol. 221, American Mathematical Society, Providence, RI, [2022] ©2022. MR 4567742
  * [DG11] D. Damanik and A. Gorodetski, _Spectral and quantum dynamical properties of the weakly coupled Fibonacci Hamiltonian_ , Comm. Math. Phys. 305 (2011), no. 1, 221–277. MR 2802305 (2012g:81065)
  * [DGY16] D. Damanik, A. Gorodetski, and W. Yessen, _The Fibonacci Hamiltonian_ , Invent. Math. 206 (2016), no. 3, 629–692. MR 3573970
  * [LQX22] Q. Liu, Y. Qu, and Y. Xiao, _The spectrum of period-doubling Hamiltonian_ , 2022, pp. 1039–1100. MR 4470245
  * [Mei14] M. Mei, _Spectra of discrete Schrödinger operators with primitive invertible substitution potentials_ , J. Math. Phys. 55 (2014), no. 8, 082701, 22. MR 3390728
  * [MWL] _This result was first announced on 1st of February 2023 together with the main steps of the proof in the Maria-Weber lecture of Siegfried Beckus at the Potsdam university_ , https://www.math.uni-potsdam.de/institut/veranstaltungen/details-1/veranstaltungsdetails/dry-ten-martini-problem-for-sturmian-dynamical-systems.
  * [Ray97] L. Raymond, _A constructive gap labelling for the discrete Schrödinger operator on a quasiperiodic chain_ , 1997, Preprint.
  * [Sim82] B. Simon, _Almost periodic Schrödinger operators: a review_ , Adv. in Appl. Math. 3 (1982), no. 4, 463–490. MR 682631