# Qualitative representations of chromatic algebras

Badriah Al Juaid1<EMAIL_ADDRESS>,  Marcel Jackson2
<EMAIL_ADDRESS>,  James Koussas3<EMAIL_ADDRESS>and
Tomasz Kowalski4<EMAIL_ADDRESS>1,2,3 Department of Mathematical
and Physical Sciences, La Trobe University, Melbourne, VIC 3086, Australia  4
Jagiellonian University, Department of Logic, Grodzka 52, 31-044 Krakow,
Poland

###### Abstract.

Conventional Ramsey-theoretic investigations for edge-colourings of complete
graphs are framed around avoidance of certain configurations. Motivated by
considerations arising in the field of Qualitative Reasoning, we explore edge
colourings that in addition to forbidding certain triangle configurations also
require others to be present. These conditions have natural combinatorial
interest in their own right, but also correspond to _qualitative
representability_ of certain _nonassociative relation algebras_ , which we
will call _chromatic_.

##  1\. Introduction

In an edge $n$-colouring of a complete graph, each triangle of edges consists
of either one colour, two colours or three colours: monochromatic, dichromatic
or trichromatic. In this article we explore edge-colourings determined by
disallowed triangle colour combinations, but also requiring others. Thus,
disallowing monochromatic triangles restricts to edge-coloured complete graphs
within the Ramsey bound $R(3,3,\dots,3)$. But what if in addition to
disallowing monochromatic triangles, we also impose the dual constraint that
all remaining colour combinations (trichromatic and dichromatic) are present:
is it possible to find such a network? These are natural combinatorial
considerations in their own right, but there is an additional motivation by
way of the algebraic foundations of qualitative reasoning, which finds wide
application in AI settings around scheduling [1], navigation [18, 26] and
geospatial positioning amongst others [27]. The constraint language underlying
typical qualitative reasoning systems determines a kind of non-associative
relation algebra (in the sense of Maddux [21]), which is attracting
considerable attention from a theoretical computer science perspective; see
[9, 13, 14, 19, 30] for example. The inverse problem of deciding if a suitably
defined non-associative algebra arises from a concrete constraint network is
shown to be NP-complete in [13]. The present work focusses on a natural family
of combinatorially intriguing cases, that we find have nontrivial solution,
and provide some novel extensions of classically understood connections
between certain associative relation algebras and combinatorial geometries,
such as in Lyndon [20].

More formally, let $C^{+}=\\{1^{\prime},c_{1},\dots,c_{n}\\}$ be a finite set
of _colours_ , let $U$ be any set and let $\lambda\colon U\times U\to C^{+}$
be a surjective map such that $\lambda(x,y)=\lambda(y,x)$ and
$\lambda(x,y)=1^{\prime}$ iff $x=y$. Then,
$\\{\lambda^{-1}(1^{\prime}),\lambda^{-1}(c_{i}),\dots,\lambda^{-1}(c_{n})\\}$
is a partition of $U\times U$ with every $\lambda^{-1}(c_{i})$ symmetric and
$\lambda^{-1}(1^{\prime})$ the identity relation. We call $\lambda$ an _edge
$n$-colouring_ of the complete graph with the set of vertices $U$, informally
thinking of $1^{\prime}$ as an invisible colour. The set
$C=C^{+}\setminus\\{1^{\prime}\\}$ is the set of _proper colours_. We will
consider natural conditions on the colourings, forbidding certain triangles
and requiring others. To forbid the occurrence of monochromatic triangles for
example, we can impose the following condition

$\forall a,b,c\in
C\colon|\\{a,b,c\\}|=1\Rightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\cap\lambda^{-1}(c)=\varnothing$

where $\circ$ is the relational composition. We will see shortly that from the
point of view of the algebras, strengthening the condition above to an
equivalence

$\forall a,b,c\in
C\colon|\\{a,b,c\\}|=1\Leftrightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\cap\lambda^{-1}(c)=\varnothing$

is more natural. Here we have all monochromatic triangles forbidden, and
moreover all non-monochromatic triangles must occur. As noted earlier, it is
not immediately clear whether such colourings exist: the Ramsey Theorem gives
an upper bound on the size of the graphs, the occurrence of all non-
monochromatic triangles gives a lower bound – conceivably greater than the
upper bound.

In general, letting $F$ be any subset of $\\{1,2,3\\}$ we arrive at 8 natural
conditions of the form

$\forall a,b,c\in C\colon|\\{a,b,c\\}|\in
F\Leftrightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\cap\lambda^{-1}(c)=\varnothing$

and 8 corresponding existence questions; these are tied precisely to the
algebraic properties of interest in Lemma 3.2 below. We will also consider the
weaker conditions, with implication, but we will see that they do not
determine a unique algebraic object.

##  2\. Nonassociative relation algebras and their representations

In this section we recall basic constructions and ideas from the theory of
relation algebras, which we then tie to the combinatorial conditions discussed
informally at the start of the article. This culminates in Lemma 3.2 of the
next section, which shows that the basic hierarchy of strengths of
representability (strong implies qualitative implies feeble) in the algebraic
setting correspond precisely to three natural constraints around forbidden
colour combinations and required colour combinations. The reader wishing to
skip the algebraic connections can survive most of the remainder of the
article with only the notation presented in Definition 3.1 and by using Lemma
3.2 as a Rosetta stone to relate algebraic terminology to combinatorial
properties on edge-coloured complete graphs.

Nonassociative algebras were introduced and first studied in [21]. A
_nonassociative relation algebra_ or simply a _nonassociative algebra_ (NA) is
an algebra $\mathbf{A}=(A,\wedge,\vee,\mathbin{;},\breve{\
},\neg,0,1,1^{\prime})$ with the following properties.

  1. (1)

$(A,\vee,\wedge,\neg,0,1)$ is a Boolean algebra.

  2. (2)

$(A,\mathbin{;},\breve{\ },1^{\prime})$ is an involutive groupoid with unit.
That is, $\mathbin{;}$ is a binary operation, $\breve{\ }$ unary, $1^{\prime}$
nullary, and the following identities hold:

    1. (a)

$1^{\prime}\mathbin{;}x=x=x\mathbin{;}1^{\prime}$

    2. (b)

$x\breve{\ }\breve{\ }=x$.

  3. (3)

The non-Boolean operations are _operators_. That is, the following further
identities hold:

    1. (a)

$x\mathbin{;}(y\vee z)=(x\mathbin{;}y)\vee(x\mathbin{;}z)$ and $(x\vee
y)\mathbin{;}z=(x\mathbin{;}z)\vee(y\mathbin{;}z)$

    2. (b)

$x\mathbin{;}0=0=0\mathbin{;}x$

    3. (c)

$(x\vee y)\breve{\ }=x\breve{\ }\vee y\breve{\ }$

    4. (d)

$0\breve{\ }=0$.

  4. (4)

$(x\mathbin{;}y)\wedge z=0$ iff $(x\breve{\ }\mathbin{;}z)\wedge y=0$ iff
$(z\mathbin{;}y\breve{\ })\wedge x=0$.

The equivalences in (4) are known as the _triangle laws_ , or _Peircean laws_.
If the operation $\mathbin{;}$ is associative, then $\mathbf{A}$ is a
_relation algebra_ (RA), in the sense of Tarski [29]; see a monograph such as
Hirsch and Hodkinson [12] or Maddux [22]. For any set $U$ and an equivalence
relation $E\subseteq U\times U$, the powerset $\mathscr{P}(E)$ carries a
natural relation algebra structure. The Boolean operations are set-
theoretical, $\mathbin{;}$ is the relational composition, $\breve{\ }$ the
converse, and $1^{\prime}$ the identity relation. Denote this algebra by
$\mathfrak{Re}_{E}(U)$. If $E=U\times U$ we write $\mathfrak{Re}(U)$, so
$\mathfrak{Re}(U)$ is the algebra of all binary relations on $U$. A relation
algebra $\mathbf{A}$ is _representable_ if there is an injective homomorphism
$\phi\colon\mathbf{A}\to\mathfrak{Re}_{E}(U)$, for some $U$ (called the _base_
of the representation) and $E$. In particular we have

  1. (r1)

$0^{\phi}=\varnothing$, $1^{\phi}=E$, $(1^{\prime})^{\phi}=Id_{U}$,

  2. (r2)

$\phi$ is a homomorphism of Boolean algebras,

  3. (r3)

$(a\breve{\ })^{\phi}=(a^{\phi})\breve{\ }$,

  4. (r4)

$(a\mathbin{;}b)^{\phi}=a^{\phi}\circ b^{\phi}$.

If $E=U\times U$ the representation is called _square_. To avoid confusion
with ‘representation’ in a generic sense of ‘any kind of representation’, we
will refer to representations above as _strong representations_. Two
weakenings of this notion of representation, which apply to nonassociative
algebras, were defined in [13] and we now recall them. A set
$\mathcal{H}\subseteq\mathscr{P}(U\times U)$ for some set $U$, is called a
_herd_ if

  1. (H1)

$\mathcal{H}$ is a Boolean set algebra with top element $U\times U$,

  2. (H2)

$Id_{U}\in\mathcal{H}$,

  3. (H3)

$S\in\mathcal{H}$ implies $S\breve{\ }\in\mathcal{H}$.

In any herd $\mathcal{H}$, the smallest element $R$ containing $S\circ T$, if
it exists, is called the _weak composition_ of $S$ and $T$, and is often
denoted by $S\diamond T$. When $\mathcal{H}$ is finite (or more generally,
complete) as a Boolean algebra then $S\diamond T$ always exists as we may
simply intersect the elements of $\mathcal{H}$ that fully contain the relation
$S\circ T$.

A nonassociative algebra $\mathbf{A}$ is said to be _qualitatively
representable_ if there is a bijection $\phi$ from ${A}$ to a herd
$\mathcal{H}$ such that

  1. (q1)

$0^{\phi}=\varnothing$, $1^{\phi}=U\times U$, $(1^{\prime})^{\phi}=Id_{U}$,

  2. (q2)

$\phi$ is a homomorphism of Boolean algebras,

  3. (q3)

$(a\breve{\ })^{\phi}=(a^{\phi})\breve{\ }$,

  4. (q4)

$a^{\phi}\circ b^{\phi}\subseteq c^{\phi}\leftrightarrow a\mathbin{;}b\leq c$.

Note that (q4) states that $c^{\phi}$ is the smallest solution to
$c^{\phi}\supseteq a^{\phi}\circ b^{\phi}$, and so $c^{\phi}=a^{\phi}\diamond
b^{\phi}$. If (q4) is strengthened to (r4), then the qualitative
representation $\phi$ is a strong square representation.

On the other hand, if (q4) is weakened to
$\varphi(a\mathbin{;}b)\supseteq\varphi(a)\circ\varphi(b)$, we obtain a still
weaker notion of representation, called _feeble_ in [13]. The next lemma
combines well known facts on representations of relation algebras with parts
of Lemmas 12 and 18 of [13].

######  Lemma 2.1.

Let $\mathbf{A}$ be complete and atomic with the set of atoms $At(A)$, and let
$\varphi\colon\mathbf{A}\to\mathscr{P}(U\times U)$ satisfy (1)–(3) above. Then
(R1) is equivalent to (R2), (Q1) is equivalent to (Q2), and (F1) is equivalent
to (F2).

  * (R1)

$\phi$ is a strong square representation of $\mathbf{A}$.

  * (R2)

For all $a,b,c\in At(A)$ we have $(a\mathbin{;}b)\wedge c\neq 0$ iff for all
$x,y\in U$ such that $(x,y)\in c^{\phi}$, there exists $z\in U$ with $(x,z)\in
a^{\phi}$ and $(z,y)\in b^{\phi}$.

  * (Q1)

$\phi$ is a qualitative representation of $\mathbf{A}$.

  * (Q2)

For all $a,b,c\in At(A)$ we have $(a\mathbin{;}b)\wedge c\neq 0$ iff there
exist $x,y,z\in U$ such that $(x,z)\in a^{\phi}$, $(z,y)\in b^{\phi}$,
$(x,y)\in c^{\phi}$.

  * (F1)

$\phi$ is a feeble representation of $\mathbf{A}$.

  * (F2)

For all $a,b,c\in At(A)$ if there exist $x,y,z\in U$ such that $(x,z)\in
a^{\phi}$, $(z,y)\in b^{\phi}$, $(x,y)\in c^{\phi}$, then
$(a\mathbin{;}b)\wedge c\neq 0$.

Since $a,b,c$ are atoms, the equivalence $(a\mathbin{;}b)\wedge c\neq
0\Leftrightarrow a\mathbin{;}b\geq c$ holds in $\mathbf{A}$. Strong
representations must reflect this property by (R2), but qualitative and feeble
representations do not need to.

######  Definition 2.2.

Let $\mathbf{A}$ be a nonassociative algebra. The _atom structure_ of
$\mathbf{A}$ is the structure $At(\mathbf{A})=(At(A),\breve{\ },I,T)$, where
$At(A)$ is the set of atoms of $\mathbf{A}$, $\breve{\ }$ is the converse
operation of $\mathbf{A}$ restricted to atoms, $I=\\{x\in At(A)\mid x\leq
1^{\prime}\\}$ is the set of _subidentity_ atoms (other atoms are called
_diversity_ atoms), $T=\\{(x,y,z)\in At(A)^{3}\mid z\leq x\mathbin{;}y\\}$ is
the set of _consistent_ triples. Triples $(x,y,z)\notin T$ are called
_forbidden_.

Conversely, for a relational structure $\mathcal{X}=(X,\ \breve{\ },I,T)$
where $\ \breve{\ }$ is a unary function, $I\subseteq X$, and $T\subseteq
X^{3}$, the _complex algebra_ $\mathfrak{Cm}(\mathcal{X})$ of $\mathcal{X}$ is
the algebra $(\mathscr{P}(X),\cap,\cup,\mathbin{;},\neg,\ \breve{\
},\varnothing,X,I)$, where for $R,S\subseteq X$, we put $S\breve{\
}=\\{s\breve{\ }:s\in S\\}$, and $S\mathbin{;}R=\\{u\in X:(s,r,u)\in T,\text{
for some }s\in S,r\in R\\}$.

If $\mathbf{A}$ is an atomic nonassociative algebra, then the map
$x\mapsto\\{a\in At(A):a\leq x\\}$ is an embedding of $\mathbf{A}$ into
$\mathfrak{Cm}(At(\mathbf{A}))$. If $\mathbf{A}$ is moreover complete, then it
is an isomorphism. It is convenient and very common to present complete and
atomic nonassociative algebras in terms of their atom structures. The next
lemma, proved in [21], characterises structures that are atom structures of
nonassociative algebras.

######  Lemma 2.3.

Let $\mathcal{X}=(X,\ \breve{\ },I,T)$ be a structure such that $I$ is a
subset of $X$, $T$ is a subset of $X^{3}$, and $\ \breve{\ }$ is a function
satisfying $a\breve{\ }\breve{\ }=a$. The following are equivalent:

  * •

$\mathcal{X}$ is the atom structure of some nonassociative algebra.

  * •

For all $a,b,c\in X$ we have

    * –

$b=c$ iff there is some $e\in I$ such that $(e,b,c)\in T$

    * –

if $(a,b,c)\in T$ then $(c\breve{\ },a,b\breve{\ })\in T$ and $(b\breve{\
},a\breve{\ },c\breve{\ })\in T$.

The triples $(a,b,c)$, $(a\breve{\ },c,b)$, $(c,b\breve{\ },a)$, $(b,c\breve{\
},a\breve{\ })$, $(c\breve{\ },a,b\breve{\ })$, $(b\breve{\ },a\breve{\
},c\breve{\ })$ are called the _Peircean transforms_ of $(a,b,c)$. See Figure
1 for a pictorial explanation of Peircean triples. The relation $T$ above is
always closed under Peircean transforms.

$a$$b$$c$ Figure 1. If $(a,b,c)\in T$, then the Peircean transforms correspond
to all of the other cyclic traverses of this triangle. If any one is present
in a network, then all the others are too. In this article, all algebras are
symmetric, so the arrow direction is not important.

There are many finite relation algebras that admit strong representations over
infinite sets but no finite set, and in general deciding strong
representability for finite relation algebras is algorithmically undecidable
even [11]. Qualitative representability is decidable, though is NP-complete
[13, Theorem 15]. Much of the simplification is due to the following useful
fact.

######  Lemma 2.4.

[13, Lemma 13] If an atomic nonassociative algebra $\mathbf{A}$ admits a
qualitative representation, then it admits a qualitative representation as
relations on set of size at most $3|At(\mathbf{A})|$ points.

##  3\. Chromatic algebras

######  Definition 3.1.

Let $S\subseteq\\{1,2,3\\}$. We define a nonassociative algebra
$\mathfrak{E}_{n+1}^{S}$ with $n+1$ atoms as the complex algebra
$\mathfrak{Cm}(\mathcal{C})$ of the structure $\mathcal{C}=(C^{+},\ \breve{\
},I,T)$, where $C^{+}=\\{1^{\prime},c_{1},\dots,c_{n}\\}$, $c\breve{\ }=c$ for
any $c\in C^{+}$, $I=\\{1^{\prime}\\}$, and $T$ is given by

  1. (1)

$\forall b,c\in C^{+}:b=c\Leftrightarrow(1^{\prime},b,c)\in T$,

  2. (2)

$\forall a,b,c\in C:|\\{a,b,c\\}|\in S\Leftrightarrow(a,b,c)\in T$, where
$C=C^{+}\setminus\\{1^{\prime}\\}$.

We call algebras $\mathfrak{E}_{n+1}^{S}$ _chromatic_.

It is easy to see that $T$ is closed under the Peircean transforms. Note that
$S$ gives the types of _consistent_ triples rather than forbidden ones, which
would be more in line with the remarks in Section 1. We stated the definition
this way to keep the notation $\mathfrak{E}_{n+1}^{S}$ in agreement with [22].
Expressing (2) in terms of the operations in the complex algebra
$\mathfrak{Cm}(\mathcal{C})$, and identifying singletons with their single
elements in a set-theoretically incorrect but notationally convenient way we
get

$\forall a,b,c\in C:|\\{a,b,c\\}|\in S\Leftrightarrow(a\mathbin{;}b)\wedge
c\neq 0.$

Then, putting $F=\\{1,2,3\\}\setminus S$, we arrive at an equivalent version
of (2)

$\forall a,b,c\in C:|\\{a,b,c\\}|\in F\Leftrightarrow(a\mathbin{;}b)\wedge
c=0$

matching the remarks in Section 1 and the statement of Lemma 2.1. With this
the next lemma is not difficult to prove: the representation (strong,
qualitative or feeble) on the atoms is precisely $\lambda^{-1}$.

######  Lemma 3.2.

Let $S\subseteq\\{1,2,3\\}$ and $F=\\{1,2,3\\}\setminus S$. The following
hold.

  1. (1)

$\mathfrak{E}_{n+1}^{S}$ is strongly representable if and only if there exists
an edge $n$-colouring $\lambda$ of a complete graph, satisfying

    1. (a)

$\forall a,b,c\in C\colon|\\{a,b,c\\}|\in
F\Leftrightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\cap\lambda^{-1}(c)=\varnothing$,
and

    2. (b)

$\forall a,b,c\in C\colon|\\{a,b,c\\}|\in
S\Leftrightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\supseteq\lambda^{-1}(c)$.

  2. (2)

$\mathfrak{E}_{n+1}^{S}$ is qualitatively representable if and only if there
exists an edge $n$-colouring $\lambda$ of a complete graph, satisfying

    1. (a)

$\forall a,b,c\in C\colon|\\{a,b,c\\}|\in
F\Leftrightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\cap\lambda^{-1}(c)=\varnothing$.

  3. (3)

$\mathfrak{E}_{n+1}^{S}$ is feebly representable if and only if there exists
an edge $n$-colouring $\lambda$ of a complete graph satisfying

    1. (a′)

$\forall a,b,c\in C\colon|\\{a,b,c\\}|\in
F\Rightarrow\lambda^{-1}(a)\circ\lambda^{-1}(b)\cap\lambda^{-1}(c)=\varnothing$.

Note that the left-hand sides of (a) and (b) above are negations of one
another, but the right-hand sides are not. Thus (a) alone forces $\mathbin{;}$
to be represented as weak composition, but (a) together with (b) force
$\mathbin{;}$ to be represented as composition.

######  Lemma 3.3.

If $S\subseteq S^{\prime}$ and $\mathfrak{E}_{n+1}^{S}$ has a feeble
representation given as a colouring, the same colouring is also a feeble
representation of $\mathfrak{E}_{n+1}^{S^{\prime}}$.

###### Proof.

Let $F=\\{1,2,3\\}\setminus S$ and $F^{\prime}=\\{1,2,3\\}\setminus
S^{\prime}$. Then, $F^{\prime}\subseteq F$ and the claim follows by Lemma
3.2(3)(a′). ∎

##  4\. Algebras $\mathfrak{E}_{n+1}^{\varnothing}$,
$\mathfrak{E}_{n+1}^{\\{1\\}}$, $\mathfrak{E}_{n+1}^{\\{1,2\\}}$ and
$\mathfrak{E}_{n+1}^{\\{1,2,3\\}}$

For $\mathfrak{E}_{n+1}^{\varnothing}$ all triangles are forbidden, so the
only possible representation is the colouring of $K_{2}$ with a single colour
($n=1$). For $\mathfrak{E}_{n+1}^{\\{1\\}}$ the only possible representation
is $K_{m}$ for $m\geq 3$ coloured with a single colour ($n=1$). These
representations are strong.

It follows from Theorem 422 of Maddux [22] that
$\mathfrak{E}_{n+1}^{\\{1,2\\}}$ is always strongly representable. Strong
representations for $\mathfrak{E}_{n+1}^{\\{1,2\\}}$ can be easily built using
representability games of Hirsch and Hodkinson (see [12]), and a finite
qualitative representation can be then extracted by Lemma 2.4.

Finite strong representations of $\mathfrak{E}_{n+1}^{\\{1,2,3\\}}$ are
obtained by Jipsen, Maddux and Tuza in [15]. A qualitative representation is
much easier to get: take the disjoint union of all possible triangles, and use
an arbitrary colour for all the missing edges.

##  5\. Algebras $\mathfrak{E}_{n+1}^{\\{3\\}}$

The algebra $\mathfrak{E}_{4}^{\\{3\\}}$ has a unique strong representation on
$4$ points. For $n>3$, the algebras $\mathfrak{E}_{n+1}^{\\{3\\}}$ are not
associative, so strong representability is impossible, making qualitative
representability of particular interest. Our construction for representability
will be based around quasigroups, and we direct the reader to a text such as
Smith [28] for further background.

Let $(Q,\cdot)$ be a commutative idempotent quasigroup on $\\{0,\dots,n-1\\}$.
We define edge colourings $\lambda_{1}$ on the complete graph on
$\\{0,\dots,n-1\\}$ and $\lambda_{2}$ on $\\{-1,0,1,\dots,n-1\\}$ into the
colours111Note that the set of proper colours in this section is
$\\{c_{0},\dots,c_{n-1}\\}$, instead of $\\{c_{1},\dots,c_{n}\\}$ used in the
other sections. It makes calculations easier and should not cause confusion.
$\\{1^{\prime},c_{0},\dots,c_{n-1}\\}$ as follows:

$\lambda_{1}(i,j)=\begin{cases}1^{\prime}&\text{ (invisible) if }i=j\\\
c_{i\cdot j}&\text{ otherwise}\end{cases}$

and

$\lambda_{2}(i,j)=\begin{cases}1^{\prime}&\text{ (invisible) if }i=j\\\
\lambda_{1}(i,j)&\text{ if $i,j\neq-1$}\\\ c_{j}&\text{ if $i=-1\neq j$}\\\
c_{i}&\text{ if $j=-1\neq i$.}\end{cases}$

Commutativity of $(Q,\cdot)$ ensures that $\lambda_{i}(j,k)=\lambda_{i}(k,j)$.

######  Lemma 5.1.

If $(Q,\cdot)$ is a commutative idempotent quasigroup on
$\\{0,1,\dots,n-1\\}$, then $\lambda_{1}^{-1}$ and $\lambda_{2}^{-1}$ are
feeble representations of $\mathfrak{E}_{n+1}^{\\{3\\}}$. Moreover, the
following properties are related by (1)$\Leftrightarrow$(3) and
(1)$\Rightarrow$(2):

  1. (1)

$\lambda_{1}$ is a qualitative representation of
$\mathfrak{E}_{n+1}^{\\{3\\}}$,

  2. (2)

$\lambda_{2}$ is a qualitative representation of
$\mathfrak{E}_{n+1}^{\\{3\\}}$,

  3. (3)

$(Q,\cdot)$ satisfies the following _$3$ -cycle condition_: for each $x,y,z$
with $|\\{x,y,z\\}|=3$ there exists $u,v,w$ with $u\cdot v=x$, $v\cdot w=y$
and $w\cdot u=z$.

###### Proof.

It is clear that $\lambda_{1}$ and $\lambda_{2}$ are surjective, so to
establish that both determine feeble representations we must ensure that there
are no monochromatic or dichromatic triangles. For $\lambda_{1}$ this is just
the cancellativity property of quasigroups: for $i,j,k\in\\{0,\dots,n-1\\}$
with $j\neq k$, we have $\lambda_{1}(i,j)\neq\lambda_{1}(i,k)$ because $i\cdot
j=i\cdot k\Rightarrow j=k$, showing that no triangle contains two edges of the
same colour. Thus $\lambda_{1}^{-1}$ is a feeble representation. Now observe
that under $\lambda_{1}$, each point $i$ is incident to edges of all colours
$c_{0},\dots,c_{n-1}$ except colour $c_{i}$ (this is where idempotency of
$(Q,\cdot)$ is used). The colouring $\lambda_{2}$ extends $\lambda_{1}$ to the
extra vertex $-1$ by adding the missing colour for each vertex: an edge of
colour $c_{i}$ between $-1$ and $i$, for each $i\in\\{0,\dots,n-1\\}$. It
follows immediately that no non-trichromatic triangles are added under this
extension: edges leaving $-1$ are coloured according to the name of the vertex
at the other end, so cannot be the same colour; and such an edge does not
coincide in colour with any other edge incident to that vertex. Thus
$\lambda_{2}^{-1}$ also is a feeble representations of
$\mathfrak{E}_{n+1}^{\\{3\\}}$.

For the three conditions: (1) implies (2) because $\lambda_{2}$ extends
$\lambda_{1}$, while according to the definition of $\lambda_{1}$, the
$3$-cycle condition in (3) is precisely the condition that $\lambda_{1}$
provides instances of each trichromatic triangle, so (1) is equivalent to (3).
∎

It is well known that commutative idempotent quasigroups exist for all and
only odd orders, though we omit details because it emerges naturally from the
proof of our main classification of qualitative representability
$\mathfrak{E}_{n+1}^{\\{3\\}}$; Theorem 5.3 below. We next recall a standard
example of a commutative idempotent quasigroup, for every odd order, and
verify that it satisfies the $3$-cycle condition.

On universe $Q_{n}=\\{0,\dots,n-1\\}$ for an odd $n$, define a multiplication
$\cdot$ by

$i\cdot j=\frac{i+j}{2}$

where $\frac{x}{2}$ stands for the unique integer $u\in\mathbb{Z}_{n}$ such
that $2u=x\pmod{n}$, which exists because $n$ is odd.

######  Lemma 5.2.

The quasigroup $(Q_{n},\cdot)$ satisfies the $3$-cycle condition.

###### Proof.

Let $|\\{i,j,k\\}|=3$ (equivalently $|\\{c_{i},c_{j},c_{k}\\}|=3$). We claim
that it is possible to choose $a,y_{a},x_{a}\in Q_{n}$ , so that we have
$i=a\cdot x_{a},$ $j=a\cdot y_{a},$ $k=x_{a}\cdot y_{a}$, verifying the
$3$-cycle condition. By the unique solution property of $(Q_{n},\cdot)$, for
each $a\in Q_{n}$, there exists $x_{a},y_{a}\in Q_{n}$, where

$\displaystyle a\cdot x_{a}$ $\displaystyle=i$ $\displaystyle a\cdot y_{a}$
$\displaystyle=j.$

Then a simple calculation shows that

$x_{a}\cdot y_{a}=i+j-a\pmod{n}$

holds. It follows that choosing $a$ to be $k-i-j\pmod{n}$ provides the desired
solution. ∎

######  Theorem 5.3.

The algebra $\mathfrak{E}_{n+1}^{\\{3\\}}$ is qualitatively representable if
and only if $n\geq 3$ is odd. Up to isomorphism, every representation of
$\mathfrak{E}_{n+1}^{\\{3\\}}$ arises from a representation of the form
$\lambda_{1}^{-1}$ or $\lambda_{2}^{-1}$ of Lemma 5.1.

###### Proof.

Assume $\mathfrak{E}_{n+1}^{\\{3\\}}$ is qualitatively representable for some
$n$. Then, there exists a finite representation, over a complete graph
$K_{m}$. Equivalently, there is a colouring map $\lambda\colon K_{m}\times
K_{m}\to C$, with $|C|=n$. Consider an arbitrarily chosen vertex $v\in K_{m}$.
Since dichromatic and monochromatic triangles are forbidden, all adjacent
edges must be of different colours, so $m-1\leq n$. As there are $n\choose 3$
different trichromatic triangles to realise, we must have $m\geq n$. So,
$n\leq m\leq n+1$.

If $m=n+1$, then every vertex has adjacent edges of all colours. Since edges
of the same colour cannot be adjacent, the edges of any given colour form a
disjoint union of copies of $K_{2}$ and there are no isolated vertices. So the
number of vertices is even, hence $n$ is odd.

Next, assume $m=n$. Since there are ${n\choose 3}$ trichromatic triangles to
realise, each necessary triangle appears exactly once in the representation.
By symmetry of the colouring condition, each edge of a given colour appears
the same number of times, and as there are $\frac{n(n-1)}{2}$ edges and $n$
colours, each edge appears $\frac{n-1}{2}$ times, so $n$ is odd. Thus
qualitative representations can exist only for odd orders, and Lemma 5.2 and
Lemma 5.1 show that all odd orders of size at least $3$ are possible.

For the second part, first consider a representation on $n$ vertices. Each
vertex has adjacent edges of all but one colour, call it the missing colour.
Suppose there are vertices $v$ and $w$ such that they miss the same colour,
say $m$, so that no edge coloured $m$ is adjacent to either $v$ or $w$. As
each edge appears $\frac{n-1}{2}$ times, $K_{n}\setminus\\{v,w\\}$ contains
$\frac{n-1}{2}$ edges coloured $m$. These edges are disjoint, so
$K_{n}\setminus\\{v,w\\}$ must contain $n-1$ vertices, in contradiction to
$|K_{n}\setminus\\{v,w\\}|=n-2$. It follows that each vertex has a different
missing colour. It follows further that adding one vertex, say $v_{-1}$ to
$K_{n}$ and letting $\lambda(v_{-1},v_{i})$ be the missing colour of $v_{i}$,
we obtain a representation on $n+1$ vertices. So, every representation on $n$
vertices is uniquely extendable to a representation on $n+1$ vertices.
Equivalently, every representation on $n$ vertices can be obtained from a
representation on $n+1$ vertices by removing one vertex.

Now, consider a representation on $n+1$ vertices. Numbering the vertices
$v_{-1}$, $v_{0},\dots,v_{n-1}$ in such a way that
$\lambda(v_{-1},v_{i})=c_{i}$ for any $i\neq-1$, we define multiplication on
the set of indices $\\{0,\dots,n-1\\}$ putting $i\cdot i$ and $i\cdot j=k$ if
$i\neq j$ and $\lambda(v_{i},v_{j})=c_{k}$. It is then routine to verify that
$\\{0,\dots,n-1\\}$ is a commutative idempotent quasigroup, and that the
colouring coincides with $\lambda_{2}$ (restricting to coincide with
$\lambda_{1}$ amongst the vertices $v_{0},\dots,v_{n-1}$). ∎

The two qualitative representations of $\mathfrak{E}_{n}^{\\{3\\}}$ can be
visualised on the complex plane as follows. Let $v_{-1}$ be the origin, and
$v_{0},\dots,v_{n-1}$ be the $n$-th roots of unity. Put
$\lambda(v_{-1},v_{0})=c_{0}=\lambda(v_{j},\overline{v_{j}})$, for
$j\in\\{1,\dots,\lfloor\frac{n}{2}\rfloor\\}$, where $\overline{v_{j}}$ is the
complex conjugate of $v_{j}$. Rotate and repeat with a different colour, as in
Figure 2. To get a representation on $n$ points remove the origin and its
outgoing edges.

$v_{-1}$$v_{0}$$v_{1}$$v_{2}$$v_{3}$${v_{4}=\overline{v_{3}}}$${v_{5}=\overline{v_{2}}}$${v_{6}=\overline{v_{1}}}$
Figure 2. First stages of drawing a qualitative representation of
$\mathfrak{E}_{7}^{\\{3\\}}$ on the complex plane.

For feeble representations, we only need to consider
$\mathfrak{E}_{n+1}^{\\{3\\}}$ for an even $n$. Taking a qualitative
representation for $\mathfrak{E}_{n}^{\\{3\\}}$, and re-colouring a single
arbitrarily chosen edge with a new colour gives a feeble representation of
$\mathfrak{E}_{n+1}^{\\{3\\}}$. Hence, $\mathfrak{E}_{n+1}^{\\{3\\}}$ is
feebly representable for all $n\geq 3$. Now using Lemma 3.3 we immediately
obtain the following.

######  Observation 5.4.

Let $3\in S$. Then $\mathfrak{E}_{n+1}^{S}$ is feebly representable for all
$n\geq 3$.

##  6\. Algebras $\mathfrak{E}_{n+1}^{\\{2\\}}$

The algebras $\mathfrak{E}_{n+1}^{\\{2\\}}$ are associative. The pentagon
algebra is the unique strong representation of $\mathfrak{E}_{3}^{\\{2\\}}$,
and it is easy to show that strong representations do not exist for $n>2$. At
the other extreme, feeble representations always exist.

######  Observation 6.1.

Let $2\in S$. Then $\mathfrak{E}_{n+1}^{S}$ is feebly representable for all
$n\geq 2$.

###### Proof.

By Lemma 3.3, it suffices to show that $\mathfrak{E}_{n+1}^{\\{2\\}}$ is
feebly representable for all $n\geq 2$. Let $V=\\{v_{0},\dots,v_{n}\\}$ be a
set of vertices, and $C=\\{c_{1},\dots,c_{n}\\}$ a set of proper colours.
Define a colouring $\lambda\colon V^{2}\to C$ by $\lambda(v_{i},v_{j})=c_{j}$
if $i<j$. Then any triangle that occurs is dichromatic, and all colours are
used, so we have a feeble representation. ∎

Qualitative representations do not exist for $n>2$, but proving this is
considerably more difficult than for strong representations. We will work our
way towards a contradiction. Assume a qualitative representation over a base
$B$ exists, and let $v\in B$. The _chromatic degree_ $\mathrm{deg}_{\chi}(v)$
of $v$ is the number of colours of its adjacent edges. If a vertex $v$ has
$\mathrm{deg}_{\chi}(v)=n$, we call $v$ _chromatically saturated_. To
distinguish clearly between triangles given as sets of vertices, and triangles
given as sets of edges, we will use parentheses $(v_{i},v_{j},v_{k})$ for
vertices and square brackets $[\ell,p,q]$ for edges/colours.

######  Lemma 6.2.

If $\mathfrak{E}_{n+1}^{\\{2\\}}$ has a qualitative representation over a base
$B$, and $v_{0}\in B$, then it also has a qualitative representation over a
base $B^{\prime}$, extending $B$, in which $v_{0}$ is chromatically saturated.

###### Proof.

Assume $\mathfrak{E}_{n+1}^{\\{2\\}}$ has a qualitative representation over
$B$. Pick an arbitrary $v_{0}\in B$. We can assume
$B=\\{v_{0},\dots,v_{m}\\}$. If $\mathrm{deg}_{\chi}(v)=n$, there is nothing
to prove, so assume $\mathrm{deg}_{\chi}(v)=k<n$. Let $d$ be a colour not
adjacent to $v_{0}$. Add a vertex $v^{\prime}$ and extend the labelling by

$\lambda(v^{\prime},v_{i})=\begin{cases}d&\text{ if }i=0\\\
\lambda(v_{0},v_{i})&\text{ otherwise}\end{cases}$

We will show that this labelling is consistent. As the only possible
inconsistency involves $v^{\prime}$, consider $v_{i}$, $v_{k}$, $v^{\prime}$
with $|\\{v_{i},v_{k},v^{\prime}\\}|=3$. If $i\neq 0\neq k$, then we have
$\lambda(v^{\prime},v_{i})=\lambda(v_{0},v_{i})$ and
$\lambda(v^{\prime},v_{k})=\lambda(v_{0},v_{k})$. Since the triangle
$(v_{0},v_{i},v_{k})$ is consistent, so is $(v^{\prime},v_{i},v_{k})$. Next,
assume $i\neq 0=k$, so we consider the triangle $(v^{\prime},v_{0},v_{i})$.
Then, we have $\lambda(v^{\prime},v_{0})=d$, and
$\lambda(v^{\prime},v_{i})=\lambda(v_{0},v_{i})$ by construction. By
assumption, $\lambda(v_{0},v_{i})\neq d$, so the triangle
$(v^{\prime},v_{0},v_{i})$ is consistent.

Repeating the extension procedure sufficiently many times, produces the
desired qualitative representation. ∎

By Lemma 6.2, we can assume that $\mathfrak{E}_{n+1}^{\\{2\\}}$ has a
qualitative representation over some $B$ such that there is a chromatically
saturated vertex $v\in B$. Every vertex $u\in B$ defines a partition of
$B\setminus\\{u\\}$ by adjacent colours, i.e., $z\sim_{u}w$ if and only if
$\lambda(u,z)=\lambda(u,w)$. Let $v_{0}$ be chromatically saturated. Pick a
single representative of each equivalence class of $\sim_{v_{0}}$ and let the
representatives be $v_{1},\dots,v_{n}$, for the colours $1,\dots,n$, so that
$\lambda(v_{0},v_{i})=i$. Let $G$ be the induced labelled subgraph of $B$ on
the vertices $\\{v_{0},\dots,v_{n}\\}$. Define a binary relation $\sqsubset$
on $\\{v_{0},\dots,v_{n}\\}$ by putting $v_{i}\sqsubset v_{j}$ if
$\lambda(v_{i},v_{j})=j$. Note that $v_{0}\sqsubset v_{i}$ for every $i>0$.

######  Lemma 6.3.

The relation $\sqsubset$ is a strict linear order on
$\\{v_{0},\dots,v_{n}\\}$.

###### Proof.

Antireflexivity is immediate from the definition. To show transitivity, assume
$v_{p}\sqsubset v_{q}$ and $v_{q}\sqsubset v_{r}$. By definition of
$\sqsubset$, only $p$ can be $0$, and in this case the claim follows
immediately, as $\lambda(v_{0},v_{r})=r$ by definition.

Assume $p\neq 0$. Then $\lambda(v_{p},v_{q})=q=\lambda(v_{0},v_{q})$ and
$\lambda(v_{q},v_{r})=r=\lambda(v_{0},v_{r})$. Now, consider $\lambda(p,r)$.
Since $\lambda(v_{0},v_{p})=p$, we must have
$\lambda(v_{p},v_{r})\in\\{q,r\\}\cap\\{p,r\\}$, and since $p\neq q$, we get
$\lambda(v_{p},v_{r})=r$ as required.

Linearity is also immediate. Take arbitrary $v_{p}$ and $v_{q}$. If $p=0$ or
$q=0$ the claim holds trivially. Otherwise, we have
$\lambda(v_{p},v_{q})\in\\{\lambda(v_{0},v_{p}),\lambda(v_{0},v_{q})\\}=\\{p,q\\}$.
∎

Although $G$ is a feeble representation of $\mathfrak{E}_{n+1}^{\\{2\\}}$
(isomorphic to the one of Observation 6.1), it is not a qualitative
representation of $\mathfrak{E}_{n+1}^{\\{2\\}}$, as no triangle
$(v_{i},v_{i},v_{j})$ with $i\sqsubset j$ is realised in $G$. Hence, if $B$ is
the base of a qualitative representation of $\mathfrak{E}_{n+1}^{\\{2\\}}$,
then $G\neq B$. Consider a vertex $u\notin G$. As $|G|=n+1$, by the pigeonhole
principle we must have $\lambda(u,v_{p})=\lambda(u,v_{q})$ for some distinct
vertices $v_{p},v_{q}\in G$. Assume that $\ell$ denotes the value
$\lambda(u,v_{p})=\lambda(u,v_{q})$.

Renumbering the colours, we can assume that $\sqsubset$ coincides with the
usual strict order on natural numbers. From now on we will work under this
assumption, using $<$ for the induced order on colours. We will refer to $G$
as a _naturally ordered subgraph_ of $B$. While there may be many subgraphs of
this form, the proofs that follow do not require us to deviate from a single
chosen one. In contrast, will consider many different choices of $u\notin G$,
and the values $p,q,\ell$ clearly depend on the choice of $u$.

We can assume $p<q$, so $\lambda(v_{p},v_{q})=q$, and thus, $\ell\neq q$. We
can also assume that $q$ is the largest vertex (amongst $v_{0},\dots,v_{n}$)
with a repeat, that is, such that $\lambda(u,v_{s})=\lambda(u,v_{q})$ holds
for some $s\neq q$. Thus, for every distinct $s,t\geq q$ we have
$\lambda(u,v_{s})\neq\lambda(u,v_{t})$. We will keep these assumptions fixed
throughout the rest of the section, and invite the reader to draw pictures
while reading.

######  Lemma 6.4.

Let $G$ be a naturally ordered subgraph of $B$, and let $u\notin G$. The
following hold:

  1. (1)

If $p\neq\ell$, then, for every $r\leq p$ we have $\lambda(u,v_{r})=\ell$.

  2. (2)

If $p=\ell$, then, for every $r<p$ we have $\lambda(u,v_{r})=q$.

  3. (3)

For every $r,r^{\prime}<p$ we have
$\lambda(u,v_{r})=\lambda(u,v_{r^{\prime}})$.

  4. (4)

If $p<\ell<q$, we have $\lambda(u,v_{\ell})=q$.

  5. (5)

For every $r\neq\ell$ with $p<r<q$, we have $\lambda(u,v_{r})=\ell$.

  6. (6)

For every $r\neq\ell$ with $q<r$, we have $\lambda(u,v_{r})=r$.

###### Proof.

For (1), let $v_{r}\sqsubset v_{p}$. Then $\lambda(v_{r},v_{p})=p$ and
$\lambda(v_{r},v_{q})=q$, so
$\lambda(u,v_{r})\in\\{\ell,p\\}\cap\\{\ell,q\\}$, as $p\neq\ell$. Hence
$\lambda(u,v_{r})=\ell$.

For (2), let $v_{r}\sqsubset v_{p}$. By transitivity, $v_{r}\sqsubset v_{q}$,
so $\lambda(v_{r},v_{q})=q$, hence $\lambda(u,v_{r})\in\\{\ell,q\\}$. As
$p=\ell$, we also have $\lambda(v_{r},v_{p})=\ell$, so
$\lambda(u,v_{r})\neq\ell$, hence $\lambda(u,v_{r})=q$.

Next, (3) follows immediately from (1) and (2).

For (4), let $v_{p}\sqsubset v_{\ell}\sqsubset v_{q}$. Then
$\lambda(u,v_{\ell})\in\\{\ell,q\\}$, as $\lambda(u,v_{q})=\ell$ and
$\lambda(v_{\ell},v_{q})=q$. Since
$\lambda(u,v_{p})=\ell=\lambda(v_{\ell},v_{p})$, we also have
$\lambda(u,v_{\ell})\neq\ell$, hence $\lambda(u,v_{r})=q$.

For (5), let $v_{p}\sqsubset v_{r}\sqsubset v_{q}$ and $r\neq\ell$. Then,
$\lambda(v_{p},v_{r})=r$ and $\lambda(v_{q},v_{r})=q$, so
$\lambda(u,v_{r})\in\\{\ell,r\\}\cap\\{\ell,q\\}$, as $r\neq\ell$. Hence
$\lambda(u,v_{r})=\ell$.

For (6), we have $\lambda(u,v_{r})\in\\{\ell,r\\}$, but
$\lambda(u,v_{r})=\ell$ contradicts the assumption that $v_{q}$ is the largest
vertex with a repeat. Hence, $\lambda(u,v_{r})=r$. ∎

######  Lemma 6.5.

Let $G$ be a naturally ordered subgraph of $B$, and let $u\notin G$. Then,
$v_{\ell}=v_{q-1}$ or $v_{\ell}=v_{q+1}$. Therefore, $\ell=q-1$ or $\ell=q+1$.

###### Proof.

We will apply Lemma 6.4 repeatedly, and referring to numbers (1)–(6) under the
tacit understanding that these will be the items in Lemma 6.4. Firstly, assume
that $p=\ell$ and $p<r<q$. From (5), we get $\lambda(u,v_{r})=\ell$. By
assumption, $\lambda(u,v_{q})=\ell$. By transitivity, if $i<p$, then
$\lambda(v_{i},v_{r})=r$, and $\lambda(v_{i},v_{q})=q$, hence
$\lambda(u,v_{i})\in\\{\ell,r\\}\cap\\{\ell,q\\}$. Since $r\neq q$, we have
$\lambda(u,v_{i})=\ell$. This contradicts (2), so such a configuration cannot
occur. As $p>0$, such an $i$ always exists. So, when $p=\ell$, we require that
no such $r$ exists, i.e., that $\ell=p=q-1$. We can now assume that
$p\neq\ell$.

Now assume $p<\ell<q-1$. Then $p<q-1<q$, so by (5), we have
$\lambda(u,v_{q-1})=\ell$. As $\lambda(v_{\ell},v_{q-1})=q-1$ and
$\lambda(v_{\ell},v_{q})=q$, we have
$\lambda(u,v_{\ell})\in\\{\ell,q\\}\cap\\{\ell,q-1\\}=\\{\ell\\}$. This
contradicts (4), as $\ell\neq q$. It follows that $p<\ell<q$ implies
$\ell=q-1$.

Assume $q<\ell$. Clearly, $\lambda(v_{q},v_{\ell})=\ell$. By (6), $q+1<\ell$
means $\lambda(u,v_{q+1})=q+1$, so $\lambda(u,v_{\ell})\in\\{\ell,q+1\\}$. But
$\lambda(u,v_{q})=\ell=\lambda(v_{q},v_{\ell})$, so we have
$\lambda(u,v_{\ell})=q+1$, which contradicts our minimality assumption on
repeated labels of edges with $u$. Thus, we must have $\ell=q+1$ if $q<\ell$.

Assume $0<\ell<p$. Then by (1), we have
$[\ell,\ell,\ell]=[\lambda(v_{\ell},v_{0}),\lambda(u,v_{\ell}),\lambda(u,v_{0})]$,
which is a contradiction, as monochromatic triangles are forbidden.

Finally, the case $q=\ell$ is impossible due to
$[\lambda(u,v_{q}),\lambda(u,v_{p}),\lambda(v_{p},v_{q})]$, so the results
cover all cases. ∎

######  Lemma 6.6.

Let $G$ be a naturally ordered subgraph of $B$, and let $u\notin G$. Let $p$,
$q$ and $\ell$ be as in Lemmas 6.4 and 6.5. Then exactly one of the following
three cases occurs:

  1. (1)

$\lambda(u,v_{i})=q+1$ for all $i\in\\{0,\dots,q\\}$,
$\lambda(u,v_{q+1})\in\\{1,\dots,q\\}$,
$\lambda(u,v_{j})=j$ for all $j\in\\{q+2,\dots,n\\}$.

  2. (2)

$\lambda(u,v_{i})=q-1$ for all $i\in\\{0,\dots,q-2\\}\cup\\{q\\}$,
$\lambda(u,v_{q-1})=q$,
$\lambda(u,v_{j})=j$ for all $j\in\\{q+1,\dots,n\\}$.

  3. (3)

$\lambda(u,v_{i})=q$ for all $i\in\\{0,\dots,q-2\\}$,
$\lambda(u,v_{q-1})=\lambda(u,v_{q})=q-1$,
$\lambda(u,v_{j})=j$ for all $j\in\\{q+1,\dots,n\\}$.

###### Proof.

By Lemma 6.5, we have either $\ell=q+1$ or $\ell=q-1$. Thus, $\ell=q+1$
implies $\lambda(u,v_{q})=q+1$, and then cases (1), (5), and (6) of Lemma 6.4
apply, showing that the first and the third items of (1) above hold. For the
second item, note that $\lambda(u,v_{q+1})\geq q+1$ contradicts the assumption
of $v_{q}$ being the largest vertex with a repeat.

If $\ell=q-1$, then we have $\lambda(u,v_{q})=q-1=\lambda(u,v_{p})$. Recalling
that $p<q$, we will discover that case (3) above will result from $p=q-1$ and
case (2) from $p<q-1$.

If $p=q-1$, then case (2) of Lemma 6.4 applies yielding $\lambda(u,v_{j})=q$
for all $j\in\\{0,\dots,q-2\\}$, and these together with case (6) of the same
lemma imply that (3) above holds.

Finally, if $\ell=q-1$ and $\lambda(u,v_{p})=q-1$ for $p<q-1$, then
$\lambda(u,v_{q})=q-1$, and by case (4) of Lemma 6.4 we have
$\lambda(u,v_{q-1})=q$. As $p\neq q-1$, case (1) of Lemma 6.4 applies, giving
$\lambda(u,v_{j})=q-1$ for all $j\leq p$. Further, case (5) yields
$\lambda(u,v_{j})=q-1$ for all $j\in\\{p+1,\dots,q-2\\}$. Putting all of these
together, we have $\lambda(u,v_{j})=q-1$ for all
$j\in\\{0,\dots,q-2\\}\cup\\{q\\}$, and then applying case (6) we obtain
$\lambda(u,v_{j})=j$ for all $j>q$, as required by (2) above. ∎

######  Corollary 6.7.

Let $G$ be a naturally ordered subgraph of $B$, and let $u\notin G$. Then, the
following hold:

  1. (1)

If $\lambda(u,v_{i})<i$, then $\lambda(u,v_{j})=j$ for all $j>i$.

  2. (2)

If for some $j$ we have $\lambda(u,v_{j})=j$ and $\lambda(u,v_{j-1})=j-1$,
then there is an $i<j-1$ with $\lambda(u,v_{i})<i$.

  3. (3)

$|\lambda(u,v_{0})-\lambda(u,v_{1})|\leq 1$.

###### Proof.

Follows by inspecting the cases of Lemma 6.6. ∎

It will be useful to state separately one special case of Lemma 6.6, covering
the case where the largest repeat occurs somewhere at the last three vertices.

######  Lemma 6.8.

Let $G$ be a naturally ordered subgraph of $B$, and let $u\notin G$. Assume
$\lambda(u,v_{n})\neq n$. The exactly one of the following three cases occurs:

  1. (1)

$\lambda(u,v_{i})=n$ for all $i\in\\{0,\dots,n-1\\}$,
$\lambda(u,v_{n})\in\\{1,\dots,n-1\\}$.

  2. (2)

$\lambda(u,v_{i})=n-1$ for all $i\in\\{0,\dots,n-2\\}\cup\\{n\\}$,
$\lambda(u,v_{n-1})=n$.

  3. (3)

$\lambda(u,v_{i})=n$ for all $i\in\\{0,\dots,n-2\\}$,
$\lambda(u,v_{n-1})=\lambda(u,v_{n})=n-1$.

Now, by definition, $G$ does not contain the triangle $[1,1,n]$, so if $B$ is
the base of a qualitative representation of $\mathfrak{E}_{n+1}^{\\{1,3\\}}$,
there must exist vertices $a,b,c\in B$ realising this triangle. We can assume
$\lambda(a,b)=n$ and $\lambda(a,c)=1=\lambda(b,c)$. We have several cases to
consider.

######  Lemma 6.9.

Let $a,b,c\notin G$. Then, $G\cup\\{a,b,c\\}$ is an inconsistent
configuration.

###### Proof.

Consider $\lambda(a,v_{n})$ and $\lambda(b,v_{n})$. They cannot be both equal
to $n$, so assume $\lambda(a,v_{n})\neq n$. Taking $u=a$, we see that the
following possibilities can occur.

We begin with case (2) of Lemma 6.8. We have $\lambda(a,v_{i})=n-1$ for all
$i\in\\{0,\dots,{n-2}\\}\cup\\{n\\}$ and $\lambda(a,v_{n-1})=n$. This implies
$\lambda(b,v_{n-1})\neq n$. Let $k=\lambda(b,v_{n-1})$.

(2.1) If $k<n-1$, then by Corollary 6.7(1) we get $\lambda(b,v_{n})=n$. Hence,
$\lambda(c,v_{n})\in\\{\lambda(c,a),\lambda(a,v_{n})\\}\cap\\{\lambda(c,b),\lambda(b,v_{n})\\}=\\{1,n-1\\}\cap\\{1,n\\}=\\{1\\}$.
So, $\lambda(c,v_{n})=1$ and then Lemma 6.8(1) applies, giving
$\lambda(c,v_{i})=n$ for all $i<n$. In particular, $\lambda(c,v_{n-2})=n$, and
since $\lambda(c,a)=1$ and $\lambda(a,v_{n-2})=n-1$, we obtain an
inconsistent, trichromatic triangle $(a,c,v_{n-2})$.

(2.2) If $k=n-1$, then
$\lambda(c,v_{n-1})\in\\{\lambda(c,a),\lambda(a,v_{n-1})\\}\cap\\{\lambda(c,b),\lambda(b,v_{n-1})\\}=\\{1,n\\}\cap\\{1,n-1\\}=\\{1\\}$.
So, $\lambda(c,v_{n-1})=1$ and thus by Corollary 6.7(1) we have
$\lambda(c,v_{n})=n$. Then, however, we obtain $\lambda(a,c)=1$,
$\lambda(a,v_{n})=n-1$, and $\lambda(c,v_{n})=n$; an inconsistent,
trichromatic triangle.

Next, cases (1) and (3) of Lemma 6.8 will be dealt with together. For case (1)
we have $\lambda(a,v_{i})=n$ for all $i<n$. As $\lambda(a,b)=n$, it follows
that $\lambda(b,v_{i})\neq n$ for all $i<n$. For case (3), we have
$\lambda(a,v_{n-1})=\lambda(a,v_{n})=n-1$, and $\lambda(a,v_{i})=n$ for all
$i<n-1$. Then, $\lambda(b,v_{i})\neq n$ for all $i<n-1$. Therefore in both
cases we have $\lambda(b,v_{i})\neq n$ for all $i<n-1$. Since $n>2$, we get
$\lambda(b,v_{0})\neq n\neq\lambda(b,v_{1})$.

(1.1/3.1) If $\lambda(b,v_{i})\neq 1$ for $i\in\\{0,1\\}$, then
$\lambda(c,v_{i})\in\\{1,n\\}\cap\\{1,\lambda(b,v_{i})\\}=\\{1\\}$ for
$i\in\\{0,1\\}$, and then
$\lambda(c,v_{0})=\lambda(c,v_{1})=\lambda(v_{0},v_{1})=1$; an inconsistent,
monochromatic triangle.

(1.2/3.2) Assume $\lambda(b,v_{i})=1$ for exactly one $i\in\\{0,1\\}$. Putting
$\\{s,t\\}=\\{0,1\\}$, let $\lambda(b,v_{s})=1$ and $\lambda(b,v_{t})\neq 1$.
Thus, $\lambda(c,v_{s})=n$ and $\lambda(c,v_{t})=1$, contradicting Corollary
6.7(3). ∎

######  Lemma 6.10.

Let $a,b\notin G$ and $c\in G$. Then, $G\cup\\{a,b\\}$ is an inconsistent
configuration.

###### Proof.

By the assumption, $c=v_{j}$ for some $j$, so
$\lambda(a,v_{j})=1=\lambda(b,v_{j})$. As in the previous lemma, we can have
at most one of $\lambda(a,v_{n})$, $\lambda(b,v_{n})$ equal to $n$, so without
loss assume $\lambda(a,v_{n})\neq n$. We analyse possible cases.

Case (1) of Lemma 6.8. We have $\lambda(a,v_{i})=n$ for all
$i\in\\{0,\dots,n-1\\}$, which can only happen if $j=n$. But,
$\lambda(b,v_{j})=1$ as well, so, as $1<n-1$, case (1) is the only possibility
for $\lambda(b,v_{j})$, and thus we get $\lambda(b,v_{i})=n$ for all
$i\in\\{0,\dots,n-1\\}$. In particular,
$\lambda(a,v_{n-1})=\lambda(b,v_{n-1})=\lambda(a,b)=n$, producing an
inconsistent, monochromatic triangle.

Case (2) of Lemma 6.8. We have $\lambda(a,v_{i})=n-1$ for all
$i\in\\{0,\dots,{n-2}\\}\cup\\{n\\}$ and $\lambda(a,v_{n-1})=n$. Since
$\lambda(a,v_{j})=1$ for some $j$, it implies $n=2$, contradicting the
assumptions.

Case (3) of Lemma 6.8. We have $\lambda(a,v_{n-1})=\lambda(a,v_{n})=n-1$, and
$\lambda(a,v_{i})=n$ for all $i\in\\{0,\dots,n-2\\}$. Since
$\lambda(a,v_{j})=1$ for some $j$, it implies $n=2$, contradicting the
assumptions. ∎

######  Lemma 6.11.

Let $b,c\notin G$ and $a\in G$. Then, $G\cup\\{b,c\\}$ is an inconsistent
configuration.

###### Proof.

We have $a=v_{j}$ for some $j$. First we show that we can assume $j\neq n$. If
$j=n$, then $\lambda(c,v_{n})=1$, and since $n>2$ only the case (1) of Lemma
6.8 applies. It follows that $\lambda(c,v_{i})=n$ for all $i<n$. Then
$\lambda(b,v_{n-1})\in\\{\lambda(b,c),\lambda(c,v_{n-1})\\}=\\{1,n\\}$. But
$\lambda(b,v_{n})=\lambda(v_{n},v_{n-1})=n$, so $\lambda(b,v_{n-1})\neq n$,
hence $\lambda(b,v_{n-1})=1$. Thus we have a $[1,1,n]$ triangle on
$(c,b,v_{n-1})$, so switching the roles of $b$ and $c$, and putting
$a=v_{n-1}$ we get $\lambda(a,b)=n$ with $a\neq v_{n}$, and
$\lambda(a,c)=1=\lambda(b,c)$.

Now we can assume $a=v_{j}$ for some $j\neq n$. Then, since $\lambda(b,c)=1$
and
$\lambda(c,v_{n})\in\\{\lambda(c,v_{j}),\lambda(v_{j},v_{n})\\}=\\{1,n\\}$, we
have $\lambda(b,v_{n})\in\\{1,n\\}$. However,
$\lambda(b,v_{j})=n=\lambda(v_{j},v_{n})$, so $\lambda(b,v_{n})=1$. This
excludes cases (2) and (3) of Lemma 6.8, as $n>2$. The remaining case (1)
gives $\lambda(b,v_{i})=n$ for all $i<n$ and then it follows that
$\lambda(c,v_{k})\in\\{\lambda(c,v_{j}),\lambda(v_{j},v_{k})\\}\cap\\{\lambda(c,b),\lambda(b,v_{k})\\}=\\{1,\lambda(v_{j},v_{k})\\}\cap\\{1,n\\}=\\{1\\}$,
for all $k\in\\{0,\dots,j-1\\}\cup\\{j+1,n-1\\}$ as $\lambda(v_{j},v_{k})\neq
n$ for all such $k$. Therefore, $\lambda(c,v_{k})=1$ for all $k<n$. In
particular, $\lambda(v_{0},v_{1})=\lambda(c,v_{1})=\lambda(c,v_{0})=1$,
producing an inconsistent, monochromatic triangle. ∎

######  Lemma 6.12.

Let $c\notin G$ and $a,b\in G$. Then, $G\cup\\{c\\}$ is an inconsistent
configuration.

###### Proof.

Let $a=v_{i}$ for some $i<n$ and $b=v_{n}$. As $\lambda(c,v_{n})=1$ and $n>2$,
the only applicable case of Lemma 6.8 is (1). However, it implies
$\lambda(c,v_{i})=n$ for all $i<n$, contradicting $\lambda(c,a)=1$. ∎

######  Lemma 6.13.

Let $b\notin G$ and $a,c\in G$. Then, $G\cup\\{b\\}$ is an inconsistent
configuration.

###### Proof.

We must have $\\{a,c\\}=\\{v_{0},v_{1}\\}$. But then $\lambda(b,a)=n$ and
$\lambda(b,c)=1$ contradicts Corollary 6.7(3). ∎

Lemma 6.13 completed the last possibility for the triangle $\\{a,b,c\\}$, and
as each possibility led to inconsistent networks, the proof of the claimed
impossibility of qualitative representability is complete.

######  Theorem 6.14.

The algebra $\mathfrak{E}_{n+1}^{\\{2\\}}$ is not qualitatively representable
for any $n>2$.

##  7\. Algebras $\mathfrak{E}_{n+1}^{\\{2,3\\}}$

The so-called _Ramsey algebras_ $\mathfrak{E}_{n+1}^{\\{2,3\\}}$ (sometimes
also known as Monk algebras and as Comer relation algebras) have received
particularly ardent attention in the literature, with the obvious close
connection to classical Ramsey-theoretic considerations of avoidance of
monochromatic triangles, as discussed in the introduction; [10] and [16] for
example. Strong representability presents very tightly constrained condition
(see Lemma 3.2) and proves too be particularly challenging. Ramsey algebras
appear in both of the texts [12] and [22], with strong representability for
$1\leq n\leq 5$ established by Comer [8] and later $n=6,7$ by Maddux [23]. The
limits of strong representability were subsequently pushed upward via a series
of efforts of Kowalski [17], Alm and Manske [4] and finally Alm [2], which is
the current state of knowledge: strong representability is achievable for all
$n\leq 2000$ except possibly $n=8,13$. The cases of $n=8,13$ and $n>2000$
remain tantalisingly unresolved, though the finite field constructions in the
above articles have been computationally verified as not providing solutions
for $n=8,13$ (see A263308 in the Online Encyclopædia of Integer Sequences
[3]). Qualitative representability presents an interesting intermediate
condition, and in this section we show that qualitative representability is
possible for all $n$.

We employ a variant of Walecki’s construction (see, e.g., [5]) originally used
to partition $K_{2k}$ into $k$ Hamiltonian paths. Let the vertices of $K_{2n}$
be distributed evenly on a circle. Colour a zigzagging path in one colour, as
in Figure 3. Then rotate the picture one step, change the colour and repeat.
Rotating $n$ times and using $n$ different colours gives the desired colouring
of $K_{2n}$.

$u_{1}$$u_{2}$$u_{3}$$u_{4}$$u_{n-2}$$u_{n-1}$$u_{n}$$u_{n+1}$$u_{n+2}$$u_{n+3}$$u_{n+4}$$u_{2n-2}$$u_{2n-1}$$u_{2n}$
Figure 3. The Walecki construction.

It is clear that no monochromatic triangles occur, so it remains to be shown
that all non-monochromatic triangles are realised. To avoid cluttering
subscripts, we will use $1,\dots,n$ as the colours, instead of
$c_{1},\dots,c_{n}$. For each $n\in\mathbb{N}$, define a map
$s_{n}\colon\mathbb{Z}\to\\{1,\dots,n\\}$ by $x\mapsto R_{n}(x-1)+1$, where
$R_{n}(k)$ is $k\pmod{n}$. In particular, we have
$s_{n}(s_{2n}(a)+s_{2n}(b))=s_{n}(a+b)$ for all $a,b\in\mathbb{Z}$ and
$n\in\mathbb{N}$. We will use this fact repeatedly below to omit $s_{2n}$
within parentheses.

It can be seen from the construction that the colour of $(u_{1},u_{1+s})$ is
$\lceil\frac{s+1}{2}\rceil$, for each $s\in\\{1,2,\dots,2n-1\\}$. Rotating $i$
steps clockwise, we get that for each $i\in\\{1,\dots,2n\\}$ and
$s\in\mathbb{Z}\setminus\\{2mn:m\in\mathbb{Z}\\}$, the colour of
$(u_{i},u_{s_{2n}(i+s)})$ is

$s_{n}\bigg{(}\bigg{\lceil}\frac{s+1}{2}\bigg{\rceil}+i-1\bigg{)}.$

To see this, note that the colour of $(u_{1},u_{s_{2n}(1+s)})$ is
$s_{n}(\lceil\frac{s+1}{2}\rceil)$ and then shift the colour $i-1$ steps
forward using the rotational symmetry and the fact that the colours cycle with
period $n$.

######  Lemma 7.1.

The colouring defined above realises all non-monochromatic triangles.

###### Proof.

Take $i,j,k\in\\{1,\dots,n\\}$ with $i<j$. We will show that there is a
triangle coloured $(i,j,k)$. We consider two cases: $k\neq i$ and $k\neq j$.
Assume first that $k\neq i$. Put

$\ell\mathrel{\mathop{:}}=s_{2n}(i+j-k),\quad
s\mathrel{\mathop{:}}=2k-2j+1,\quad\textrm{and}\quad
t\mathrel{\mathop{:}}=2k-2i.$

Note that $s,t\in\mathbb{Z}\setminus\\{2mn:m\in\mathbb{Z}\\}$. Hence the
colour of $(u_{\ell},u_{s_{2n}(\ell+s)})$ is

$s_{n}\bigg{(}\bigg{\lceil}\frac{(2k-2j+1)+1}{2}\bigg{\rceil}+(i+j-k)-1\bigg{)}=s_{n}(k-j+1+i+j-k-1)=i.$

The colour of $(u_{\ell},u_{s_{2n}(\ell+t)})$ is

$s_{n}\bigg{(}\bigg{\lceil}\frac{(2k-2i)+1}{2}\bigg{\rceil}+(i+j-k)-1\bigg{)}=s_{n}(k-i+1+i+j-k-1)=j.$

As $i<j$, we have $s<t$. Now,

$t-s=(2k-2i)-(2k-2j+1)=2(j-i)-1,$

which is not a multiple of $2n$. Hence the colour of
$(u_{s_{2n}(\ell+s)},u_{s_{2n}(\ell+t)})$ is

$\displaystyle
s_{n}\bigg{(}\bigg{\lceil}\frac{(2(j-i)-1)+1}{2}\bigg{\rceil}+(i+j-k)+(2k-2j+1)-1\bigg{)}$
$\displaystyle=$ $\displaystyle s_{n}(j-i+i+j-k+2k-2j+1-1)$ $\displaystyle=k.$

So, $(u_{\ell},u_{s_{2n}(\ell+s)},u_{s_{2n}(\ell+t)})$ is a triangle with
edges coloured by $i$, $j$, and $k$. Next, assume $k\neq j$ and put

$\ell\mathrel{\mathop{:}}=s_{2n}(i+j-k),\quad
s\mathrel{\mathop{:}}=2k-2j,\quad\textrm{and}\quad
t\mathrel{\mathop{:}}=2k-2i+1.$

Again, $s,t\in\mathbb{Z}\setminus\\{2mn:m\in\mathbb{Z}\\}$. By calculations
similar to the first case, we get that the colour of
$(u_{\ell},u_{s_{2n}(\ell+s)})$ is $i$, and the colour of
$(u_{\ell},u_{s_{2n}(\ell+t)})$ is $j$. Moreover,

$t-s=(2k-2i+1)-(2k-2j)=2(j-i)+1,$

so the colour of $(u_{s_{2n}(\ell+s)},u_{s_{2n}(\ell+t)})$ is

$\displaystyle
s_{n}\bigg{(}\bigg{\lceil}\frac{(2(j-i)+1)+1}{2}\bigg{\rceil}+(i+j-k)+(2k-2j)-1\bigg{)}$
$\displaystyle=$ $\displaystyle s_{n}(j-i+1+i+j-k+2k-2j-1)$ $\displaystyle=k.$

Choosing between the two cases, as needed for (i) $k=i,k\neq j$, (ii) $k\neq
i,k=j$, or (iii) $k\neq i,j$ we can construct all non-monochromatic triangles.
∎

######  Theorem 7.2.

For any natural number $n$ the algebra $\mathfrak{E}_{n+1}^{\\{2,3\\}}$ is
qualitatively representable on the graph $K_{2n}$.

###### Proof.

Immediate by Lemma 7.1. ∎

##  8\. Algebras $\mathfrak{E}_{n+1}^{\\{1,3\\}}$

These algebras are better known as _Lyndon algebras_. Lyndon [20] showed that
for $n\geq 4$, strong representations of the algebra
$\mathfrak{E}_{n+1}^{\\{1,3\\}}$ precisely correspond to affine planes of
order $n-1$, so that by the Bruck-Ryser Theorem [7] and standard field
constructions, there are infinitely many $n$ for which
$\mathfrak{E}_{n+1}^{\\{1,3\\}}$ is strongly representable, and infinitely
many for which it is not strongly representable. This was used by Monk to show
that the strongly representable relation algebras admit no finite
axiomatisation [24]. We now explore how qualitative and even feeble
representations of $\mathfrak{E}_{n+1}^{\\{1,3\\}}$ relate similarly to
geometric objects. The natural starting point will be feeble representations,
which we find corresponds to parallelisms of linear spaces, in the sense of
finite geometry. We direct the reader to a text on linear spaces such as [6]
for further background on linear spaces, though the connection with feeble
representations of Lyndon algebras is presented here for the first time.

A _linear space_ is a system $(G,\mathscr{L})$, where $G$ is a set of points,
and $\mathscr{L}$ a family of subsets of $G$ called _lines_ satisfying the
following axioms:

  1. (LS1)

Every pair of distinct points is contained in a line;

  2. (LS2)

Every pair of distinct lines have intersection that is either empty or a
singleton;

  3. (LS3)

Every line contains at least two points.

An obvious consequence of LS1 and LS2 is that each pair of points $p$, $q$ are
contained within a unique line, which we denote by $\overline{pq}$. As usual,
points lying on the same line are said to be _collinear_ , two lines are
_incident_ if they intersect to a common point.

A _parallelism_ of a linear space $(G,\mathscr{L})$ is an equivalence relation
$\varpi$ on $\mathscr{L}$ with the property that lines within a common block
do not intersect. The blocks of $\varpi$ are referred to as _parallel classes_
and lines within a block are _parallel_. The identity relation on
$\mathscr{L}$ is always an example of a parallelism, and we refer to this as
the _trivial parallelism_. But in general there may be many other
parallelisms, with various numbers of parallel classes. The next theorem shows
that $n$-block parallelisms of linear spaces precisely capture feeble
representations of the algebra $\mathfrak{E}_{n+1}^{\\{1,3\\}}$, modulo the
choice of bijection between diversity atoms and parallel classes.

######  Theorem 8.1.

Every linear space $(G,\mathscr{L})$ with $n$-block parallelism $\varpi$
yields a feeble representation of $\mathfrak{E}_{n+1}^{\\{1,3\\}}$ by relating
$p,q\in G$ by the $i^{\rm th}$ colour whenever $p$ is collinear with $q$ by
way of a line in the $i^{\rm th}$ block of $\varpi$. Moreover, every feeble
representation $\mathfrak{E}_{n+1}^{\\{1,3\\}}$ arises in this way.

###### Proof.

For the forward direction, we consider the $n$-block parallelism $\varpi$ of
$(G,\mathscr{L})$ and the defined mapping of diversity atoms of
$\mathfrak{E}_{n+1}^{\\{1,3\\}}$ to parallel classes as given. For
convenience, we allow the parallel classes to share the same name as the
colour of the atom to which they are matched. So the (attempted) feeble
representation $a^{\theta}$ of a diversity atom $a$ labels the edge from $p$
to $q$ if $p$ is collinear to $q$ by way of a line in $a$ (the identity atom
is represented, as required, by the identity relation). By Axioms LS1 and LS2,
all pairs receive a unique colour. By LS3, all colours appear, so that
$\theta$ is a feeble representation of $\mathfrak{E}_{n+1}^{\\{1,3\\}}$.

For the converse direction, let $\theta$ be a feeble representation of
$\mathfrak{E}_{n+1}^{\\{1,3\\}}$ on a set $G$. To define the lines
$\mathscr{L}$, for each diversity atom $a$ we will include maximal cliques
with respect to edges $a^{\theta}$ as lines in $\mathscr{L}$. To define the
parallelism $\varpi$, we define lines to be parallel if they are cliques with
respect to a common atom. Because each pair of points in $G$ are related by
$a^{\theta}$ for some atom $a$, we have that Axiom LS1 holds. Because no edge
is coloured by more than one atom, we have that Axiom LS2 holds. It is trivial
that Axiom LS3 holds. Because $\theta$ is a feeble representation, each atom
labels at least one edge, so that the number of blocks in $\varpi$ is exactly
$n$. Because there are no dichromatic triangles in the feeble representation
$\theta$ we have that the lines within common blocks of $\varpi$ do not
intersect, so that $\varpi$ is a parallelism of $(G,\mathscr{L})$. Finally, it
is clear that the representation of $\mathfrak{E}_{n+1}^{\\{1,3\\}}$ over
$(G,\mathscr{L})$, $\varpi$ agrees with the one defined in the first half of
the proof, with the obvious matching of atoms to parallel classes. ∎

We mention in passing that an alternative presentation here is to begin with a
linear space $(G,\mathscr{L})$ in which there is a distinguished line
$L_{\infty}$ (the line at infinity) that is incident with all other lines and
contains precisely $n$ points. Provided that every line other than
$L_{\infty}$ contains at least $3$ points, we may obtain a linear space
$(G\backslash L_{\infty},\mathscr{L}\backslash\\{L_{\infty}\\})$ and define an
$n$-block parallelism by letting two lines be parallel if they were incident
in $(G,\mathscr{L})$ to a common point on $L_{\infty}$. Conversely, any
parallelism $\varpi$ of a linear space gives rise to a new linear space by
letting the blocks of $\varpi$ be treated as additional new points, and the
set of blocks of $\varpi$ be considered as an additional new line (“at
infinity”). This of course is a general case of the familiar interplay between
projective planes and affine planes.

Since $3\in\\{1,3\\}$, applying Observation 5.4 immediately gives the next
result.

######  Observation 8.2.

Feeble representations of Lyndon algebras, and hence the corresponding linear
spaces, exist for all $n\geq 3$.

A simple application of Theorem 8.1 yields another solution. The _near pencil_
is a linear space on $n\geq 3$ points $p_{0},p_{1},\dots,p_{n-1}$, where the
lines are $\\{p_{1},\dots,p_{n-1}\\}$ along with $\\{p_{0},p_{i}\\}$ for each
$i=1,\dots,n-1$. This near pencil has $n$ lines, and with the trivial
parallelism yields a further easy feeble representation of
$\mathfrak{E}_{n+1}^{\\{1,3\\}}$.

We now consider qualitative representations; each triangle type has a natural
geometric interpretation, the first that there are large enough lines, the
second that there are enough points in general position.

######  Theorem 8.3.

A linear space $(G,\mathscr{L})$ with $n$-block parallelism $\varpi$
represents all monochromatic triangles in $\mathfrak{E}_{n+1}^{\\{1,3\\}}$
precisely when (LS4) holds and all trichromatic triangles precisely when (LS5)
holds:

  1. LS4

each parallel class contains a line with at least $3$ points.

  2. LS5

each triple of parallel classes are witnessed by $3$ points in general
position. That is, for parallel classes $d_{1},d_{2},d_{3}$ there are points
$p_{1},p_{2},p_{3}$ in general position, with $\overline{p_{1}p_{2}}\in
d_{1}$, $\overline{p_{2}p_{3}}\in d_{1}$, $\overline{p_{3}p_{1}}\in d_{3}$.

###### Proof.

This is immediate, as it simply states the condition on representations in the
geometric formulation shown equivalent by Theorem 8.1. ∎

We will refer to a linear space with parallelism $(G,\mathscr{L},\varpi)$ as
an _affine Lyndon geometry_ if it satisfies the extra axioms LS4 and LS5. The
linear space obtained from an affine Lyndon geometry by adjoining the line at
infinity and associated directions, will be called a _Lyndon geometry_ ; note
that a Lyndon geometry is a linear space with a distinguished line. As with
affine planes and projective planes, these two concepts in some sense differ
only in that parallel classes and the parallelism are given the name “points
at infinity” and “line at infinity”. In order to match the case for affine
planes, we let the _order_ of affine Lyndon geometry $(G,\mathscr{L},\varpi)$
be the number $n$ such that $\varpi$ has $n+1$ blocks.

We now show that affine Lyndon geometries of every order exist.

######  Theorem 8.4.

Let $(G,\mathscr{L})$ be an affine plane of order $n\geq 3$ and consider any
set $D$ of $k\leq n-2$ points in $G$. Define a parallelism $\varpi$ on the
subspace on $G\setminus D$ by defining two lines parallel if: in
$(G,\mathscr{L})$ they pass through a unique point of $D$; and otherwise if
they were parallel in $(G,\mathscr{L})$. The parallelism $\varpi$ has $n+k+1$
blocks.

###### Proof.

Let $\mathscr{L}_{D}$ denote the lines in the defined subspace: so
$K\in\mathscr{L}_{D}$ is of the form $L\setminus D$ for a unique
$L\in\mathscr{L}$. For $L\in\mathscr{L}$ we will write $L^{-}$ to denote
$L\setminus D$. We will refer to blocks of $\varpi$ corresponding to a
parallel class in $(G,\mathscr{L})$, as _old_ directions, and those consisting
of the pencil of lines that pass through precisely one single point $p\in D$
as _new_ directions. Since each line in $\mathscr{L}$ contains $n$ points,
each line in $\mathscr{L}_{D}$ contains at least $2$ points, verifying the
axiom (LS3). The axioms (LS1) and (LS2) are inherited from $(G,\mathscr{L})$,
so $(G\setminus D,\mathscr{L}_{D})$ is a linear space.

To verify axiom (LS4) note that as there are $n$ lines in each direction of
the affine plane $(G,\mathscr{L})$, and at most $n-2$ of these lines are
through unique points in $D$, there are at least $2$ lines in each old
direction. Let $m$ be the number of lines in an old direction $o$. These lines
contain at least $mn-(n-2)$ points, and as $n\geq 3$ and $m\geq 2$ we have
$mn-n+2>2m$, showing that at least one of the $m$ lines must contain strictly
more than 2 points. Analogously, there are $n+1$ lines through each point $p$
of $D$, and at most $k-1\leq n-3$ of them can pass through a second point of
$D$, so each new direction contains at least $4$ lines. As above, it follows
that at least one of these lines contains at least $3$ points. It is now also
clear that the parallelism $\varpi$ has $n+k+1$ blocks.

For axiom (LS5), consider three directions from $\varpi$. If all three are
old, say, $o_{1}$, $o_{2}$ and $o_{3}$, then as there are $n$ lines of
$\mathscr{L}$ in $o_{1}$, there is a line $L_{1}\in\mathscr{L}\cap o_{1}$,
with $L_{1}\cap D=\varnothing$, so $L_{1}\in\mathscr{L}_{D}\cap o_{1}$, that
is, $L_{1}^{-}=L_{1}$. Similarly, there is a line $L_{2}\in\mathscr{L}\cap
o_{2}$ with $L_{2}^{-}=L_{2}$. Let $p$ be the unique point in $L_{1}\cap
L_{2}$. As there are $n$ lines in $\mathscr{L}\cap o_{3}$, and
$|D\cup\\{p\\}|=k+1\leq n-1$, there is a line $L_{3}\in\mathscr{L}\cap o_{3}$
with $L_{3}\cap(D\cup\\{p\\})=\varnothing$, so that $L_{3}^{-}=L_{3}$. Since
$L_{1}$, $L_{2}$ and $L_{3}$ are lines from $\mathscr{L}$, not all through the
same point, they intersect pairwise at 3 distinct points. Hence, $p\in
L_{1}\cap L_{2}$, $q\in L_{1}\cap L_{3}$ and $r\in L_{2}\cap L_{3}$ are 3
points in general position in $G\setminus D$. But since $L_{1}=L_{1}^{-}$,
$L_{2}=L_{2}^{-}$ and $L_{3}=L_{3}^{-}$ they witness (LS5) for $o_{1}$,
$o_{2}$ and $o_{3}$ in $(G\setminus D,\mathscr{L}_{D})$.

Next, let $o_{1}$ and $o_{2}$ be old directions and let $d_{3}$ be a new
direction. Reasoning as before, we find lines $L_{1}\in\mathscr{L}\cap o_{1}$
and $L_{2}\in\mathscr{L}\cap o_{2}$ such that $L_{1}^{-}=L_{1}$,
$L_{2}^{-}=L_{2}$, and $L_{1}\cap L_{2}=\\{p\\}$ with $p\in G\setminus D$. As
there are $n+1$ lines in $\mathscr{L}$ passing through $d_{3}$, there is a
line $L_{3}\in\mathscr{L}$ passing through $d_{3}$, with
$L_{3}\cap((D\cup\\{p\\})\setminus\\{d_{3}\\})=\varnothing$. Then, $p\in
L_{1}\cap L_{2}$, $q\in L_{1}\cap L_{3}$ and $r\in L_{2}\cap L_{3}$ are 3
points in general position in $G\setminus D$. Moreover,
$L_{3}^{-}=L_{3}\setminus\\{d_{3}\\}$, so $L_{1}^{-}$, $L_{2}^{-}$ and
$L_{3}^{-}$ witness (LS5) for $o_{1}$, $o_{2}$ and $d_{3}$ in $(G\setminus
D,\mathscr{L}_{D})$.

Further, let $o_{1}$ be an old direction and let $d_{2}$ and $d_{3}$ be new
directions. As there are $n+1$ lines in $\mathscr{L}$ passing through $d_{2}$,
there are $n$ lines in $\mathscr{L}\setminus o_{1}$ passing through $d_{2}$,
so we find a line $L_{2}\in\mathscr{L}\setminus o_{1}$ such that $d_{2}\in
L_{2}$ and $L_{2}\cap(D\setminus\\{d_{2}\\})=\varnothing$. Let $o_{2}$ be the
direction of $L_{2}$ in $(G,\mathscr{L})$. As there there are $n-1$ lines in
$\mathscr{L}\setminus(o_{1}\cup o_{2})$ passing through $d_{3}$, we find
$L_{3}\in\mathscr{L}\setminus(o_{1}\cup o_{2})$ with $d_{3}\in L_{3}$ such
that $L_{3}\cap(D\setminus\\{d_{3},\\})=\varnothing$. Then $L_{2}$ and $L_{3}$
intersect at a point $r\in G\setminus D$. Now consider $o_{1}$. There are $n$
lines of $\mathscr{L}$ in $o_{1}$, at most $k+1=n-1$ of them having nonempty
intersections with $D\cup\\{r\\}$, so there is a line $L_{1}\in o_{1}$ such
that $L_{1}\cap(D\cup\\{r\\})=\varnothing$. Then, $p\in L_{1}\cap L_{2}$,
$q\in L_{1}\cap L_{3}$ and $r\in L_{2}\cap L_{3}$ are 3 points in general
position in $G\setminus D$. So the lines $L_{1}^{-}=L_{1}$,
$L_{2}^{-}=L_{2}\setminus\\{d_{2}\\}$ and
$L_{3}^{-}=L_{3}\setminus\\{d_{3}\\}$, witness (LS5) for $o_{1}$, $d_{2}$ and
$d_{3}$ in $(G\setminus D,\mathscr{L}_{D})$.

Finally, let $d_{1}$, $d_{2}$ and $d_{3}$ be new directions. We find
$L_{2}\in\mathscr{L}$ such that $d_{2}\in L_{2}$ and
$L_{2}\cap(D\setminus\\{d_{2}\\})=\varnothing$. Let $o_{2}$ be the direction
of $L_{2}$ in $(G,\mathscr{L})$. Then we find $L_{3}\in\mathscr{L}\setminus
o_{2}$, with $d_{3}\in L_{3}$ and
$L_{3}\cap(D\setminus\\{d_{3},\\})=\varnothing$, so $r\in L_{2}\cap L_{3}$ is
a point in $G\setminus D$. Let $o_{3}$ be the direction of $L_{3}$ in
$(G,\mathscr{L})$. There are $n-1$ lines in $\mathscr{L}\setminus(o_{2}\cup
o_{3})$ passing through $d_{1}$, and
$|(D\setminus\\{d_{1}\\})\cup\\{r\\}|=k\leq n-2$, so there is a line
$L_{1}\in\mathscr{L}\setminus(o_{2}\cup o_{3})$ passing through $d_{1}$ with
$L_{1}\cap((D\setminus\\{d_{1}\\})\cup\\{r\\})=\varnothing$. Then, $p\in
L_{1}\cap L_{2}$, $q\in L_{1}\cap L_{3}$ and $r\in L_{2}\cap L_{3}$ are 3
points in general position in $G\setminus D$, and the lines
$L_{1}^{-}=L_{1}\setminus\\{d_{1}\\}$, $L_{2}^{-}=L_{2}\setminus\\{d_{2}\\}$
and $L_{3}^{-}=L_{3}\setminus\\{d_{3}\\}$, witness (LS5) for $d_{1}$, $d_{2}$
and $d_{3}$ in $(G\setminus D,\mathscr{L}_{D})$. ∎

######  Corollary 8.5.

There exist affine Lyndon geometries of all orders greater than $3$;
equivalently, $\mathfrak{E}_{n+1}^{\\{1,3\\}}$ is qualitatively representable
for all $n\geq 3$.

###### Proof.

By Theorem 8.3 it suffices to cover all $n\geq 3$ using Theorem 8.4. There are
affine planes of every prime order $p$, so Theorem 8.4 shows that there are
affine Lyndon geometries of all orders $p,p+1,\dots,2(p-1)$. All numbers
$n\geq 2$ lie in the interval $[p,2(p-1)]$ for some prime $p$: this is trivial
to verify for small $n$, and follows, for example, from Nagura’s variant of
Bertrand’s postulate [25], showing that for $m\geq 25$ there is a prime
between $m$ and $5m/4$. ∎

##  9\. Infinite cardinalities

The definition of chromatic algebras $\mathfrak{E}_{n}^{S}$ easily extends to
allow for the case $n=\kappa$ for an infinite cardinal $\kappa$. Strong
representations for $\mathfrak{E}_{\kappa}^{S}$ are known for $S=\\{1,3\\}$
(by way of affine planes of order $\kappa$), while strong representations for
$\mathfrak{E}_{\kappa}^{S}$ in the case of $S=\\{1,2\\},\\{2,3\\},\\{1,2,3\\}$
are easily achievable using the game-theoretic methods of Hirsch and Hodkinson
[12], but they are somewhat convoluted, being subdirect products of
representations of countable subalgebras of $\mathfrak{E}_{\kappa}^{S}$ (even
in the case $\kappa=\omega$). We will not investigate them here. The remaining
cases do not admit strong representations: for $\varnothing$ and $\\{1\\}$
this is trivial, while for $S=\\{3\\}$ and $S=\\{2\\}$, the situation is
discussed in the relevant Sections 5 and 6.

For qualitative representations there emerges an interesting contrast with the
finite colour results, namely, $\mathfrak{E}_{\kappa}^{\\{2\\}}$ becomes
qualitatively representable for all infinite $\kappa$, despite
$\mathfrak{E}_{n+1}^{\\{2\\}}$ not being qualitatively representable for any
finite $n$. Moreover, there is a direct, uniform method of constructing
representations for all infinite cases.

######  Theorem 9.1.

Let $\kappa$ be an infinite cardinal. For $S\subseteq\\{1,2,3\\}$, the algebra
$\mathfrak{E}_{\kappa}^{S}$ has a qualitative representation if and only if
$S\cap\\{2,3\\}\neq\varnothing$.

###### Proof.

For $S=\varnothing$ or $S=\\{1\\}$ it is trivial that no representations
exist.

Now assume that $3\in S$, and let $C_{\kappa}$ be the set of all colours.
There are $\kappa$ triangles $(T_{\alpha}:\alpha<\kappa)$ to be witnessed in
order to achieve a qualitative representation of $\mathfrak{E}_{\kappa}^{S}$.
We will construct a chain of complete networks $(N_{\alpha}:\alpha<\kappa)$
and a chain of sets of colours $(C_{\alpha}:\alpha<\kappa)$ such that
$C_{\alpha}$ is the set of all colours used in $N_{\alpha}$. We use $\otimes$
and $\oplus$ for cardinal multiplication and addition, and $+$ for ordinal
addition. Let $N_{0}$ be the empty network. Assume inductively that a chain of
complete networks $(N_{\beta}:\beta<\alpha)$ has been constructed, such that
(i) each $N_{\beta}$ witnesses the triangles $T_{\gamma}$ for all
$\gamma<\beta$, (ii) $|N_{\beta}|\leq 3\otimes|\beta|$, and (iii)
$|C_{\beta}|\leq 9\otimes|\beta|\otimes|\beta|$. Construct $N_{\alpha}$ as
follows.

  * •

If $\alpha=\gamma+1$ for some $\gamma$, let
$N^{\prime}_{\alpha}:=N_{\gamma}\uplus T_{\gamma}$. Then
$|N^{\prime}_{\alpha}|=|N_{\gamma}|\oplus 3\leq 3\otimes|\gamma|\oplus 3\leq
3\otimes|\alpha|$, and $N^{\prime}_{\alpha}$ witnesses all triangles
$T_{\beta}$ for $\beta<\alpha$. So $N^{\prime}_{\alpha}$ satisfies (i) and
(ii) but it is not complete (except for $\gamma=0$). Let
$M^{\prime}_{\alpha}:=\\{\\{x,y\\}:x\in N_{\gamma},\ y\in T_{\gamma}\\}$.
Then, $|M^{\prime}_{\alpha}|=3\otimes|N_{\gamma}|$, and putting
$C^{\prime}_{\alpha}$ for the set of colours used in $N^{\prime}_{\alpha}$ we
get $|C^{\prime}_{\alpha}|=|C_{\gamma}|\oplus 3\leq
9\otimes|\gamma|\otimes|\gamma|\oplus 3<\kappa$. Hence $|C_{\kappa}\setminus
C_{\alpha}^{\prime}|=\kappa$ and therefore we can choose from
$C_{\kappa}\setminus C_{\alpha}^{\prime}$ a unique colour for each
$\\{x,y\\}\in M^{\prime}_{\alpha}$ and thus complete $N_{\alpha}^{\prime}$ to
$N_{\alpha}$. Then $|N_{\alpha}|=|N^{\prime}_{\alpha}|\leq 3\otimes|\alpha|$,
and $|C_{\alpha}|\leq|C_{\alpha}^{\prime}\cup M^{\prime}_{\alpha}|\leq
9\otimes|\gamma|\otimes|\gamma|\oplus 3\oplus 3\otimes|N_{\gamma}|\leq
9\otimes|\gamma|\otimes|\gamma|\oplus 3\oplus 9\otimes|\gamma|\leq
9\otimes|\alpha|\otimes|\alpha|$. Thus, (i), (ii) and (iii) are satisfied.

  * •

If $\alpha$ is a limit ordinal, let
$N_{\alpha}:=\bigcup_{\beta<\alpha}N_{\beta}$. Then $N_{\alpha}$ is a complete
network witnessing the triangles $T_{\beta}$ for all $\beta<\alpha$, so (i) is
satisfied. Moreover, $|N_{\beta}|\leq 3\otimes|\beta|\leq|\alpha|$ for each
$\beta<\alpha$, so $N_{\alpha}$ is a union of $|\alpha|$ sets, each of
cardinality at most $|\alpha|$; hence $|N_{\alpha}|\leq|\alpha|$, satisfying
(ii). Similarly, $|C_{\beta}|\leq 9\otimes|\beta|\otimes|\beta|\leq|\alpha|$
for each $\beta<\alpha$, so
$|C_{\alpha}|=|\bigcup_{\beta<\alpha}C_{\beta}|\leq|\alpha|$, showing that
(iii) is satisfied.

The union $\bigcup_{\alpha<\kappa}N_{\alpha}$ is a well-defined qualitative
representation of $\mathfrak{E}_{\kappa}^{S}$. If $3\notin S$ but $2\in S$ we
can apply same methodology as for $3\in S$, except that now to complete
$N^{\prime}_{\alpha}$ to $N_{\alpha}$ for a successor $\alpha$ we select a
single colour from $\kappa$ unused ones for all the missing edges. ∎

##  10\. Summary

The table below summarises the known results on representability of finite
chromatic algebras. The main question that remains open is for which $n$
strong representations of Ramsey algebras $\mathfrak{E}_{n+1}^{\\{2,3\\}}$
exist.

Representations of $\mathfrak{E}_{n+1}^{S}$
---
$S$ | comp. of diversity atoms | quali-rep. | strong rep.
$\\{1,2,3\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}0^{\prime}&\text{ if }i\neq j\\\ 1&\text{ if }i=j\end{cases}$ | Yes | Yes
$\\{2,3\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}0^{\prime}&\text{ if }i\neq j\\\ \neg a_{i}&\text{ if }i=j\end{cases}$ | Yes |  Yes for $n\lesssim 2000$ except 8 and 13 Not known in general
$\\{1,3\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}\neg a_{i}\wedge\neg a_{j}\wedge 0^{\prime}&\text{ if }i\neq j\\\ 1^{\prime}\vee a_{i}&\text{ if }i=j\end{cases}$ |  Yes iff $n>3$ |  Yes iff $\exists$ proj. plane of ord. $n-1$
$\\{1,2\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}a_{i}\vee a_{j}&\text{ if }i\neq j\\\ 1&\text{ if }i=j\end{cases}$ | Yes |  Yes (only infinite rep’s)
$\\{3\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}\neg a_{i}\wedge\neg a_{j}\wedge 0^{\prime}&\text{ if }i\neq j\\\ 1^{\prime}&\text{ if }i=j\end{cases}$ | Yes iff $n$ is odd | Yes iff $n=3$
$\\{2\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}a_{i}\vee a_{j}&\text{ if }i\neq j\\\ \neg a_{i}&\text{ if }i=j\end{cases}$ | No | No
$\\{1\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}0&\text{ if }i\neq j\\\ 1^{\prime}\vee a_{i}&\text{ if }i=j\end{cases}$ | Yes iff $n=1$ | Yes iff $n=1$
$\\{\varnothing\\}$ | $a_{i}\mathbin{;}a_{j}=\begin{cases}0&\text{ if }i\neq j\\\ 1^{\prime}&\text{ if }i=j\end{cases}$ | Yes iff $n=1$ | Yes iff $n=1$

## Acknowledgements

The authors wish to thank Michael Payne for his discussions around aspects of
this paper, particularly around developments leading to Theorem 8.4.

## References

  * [1] J.F. Allen, Maintaining knowledge about temporal intervals, Comm. ACM 26(11) (1983), 832–843.
  * [2] J.F. Alm, 401 and beyond: improved bounds and algorithms for the Ramsey algebra search, J. Integer Seq. 20 (2017), no. 8, Art. 17.8.4, 10pp.
  * [3] J. F. Alm, Entry A263308 in The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A263308.
  * [4] J. F. Alm and J. Manske, Sum-free cyclic multi-bases and constructions of Ramsey algebras, Discrete Appl. Math. 180 (2015), 204–212.
  * [5] B. Alspach., The wonderful Walecki construction, Bull. Inst. Combin. Appl 52 (2008), 7–20.
  * [6] L.M. Batten and A. Beutelspacher, _The Theory of Finite Linear Spaces_ , Cambridge University Press, 1993.
  * [7] R.H. Bruck, and H.J. Ryser, The nonexistence of certain finite projective planes, Canadian Journal of Mathematics 1 (1949), 88–93.
  * [8] S. Comer, Color schemes forbidding monochrome triangles, Proceedings of the fourteenth Southeastern conference on combinatorics, graph theory and computing (Boca Raton, Fla., 1983), Congr. Numer., 39 (1983), 231–236.
  * [9] F. Dylla, J.H. Lee, T. Mossakowski, T. Schneider, A. Van Delden, J. Van De Ven, D. Wolter, A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties, ACM Computing Surveys 50 (2017) Article No.: 7, pp 1–39.
  * [10] R. Greenwood and A. Gleason, Combinatorial relations and chromatic graphs, Canadian J. Math. 7 (1955), 1–7.
  * [11] R. Hirsch and I. Hodkinson, Representability is not decidable for finite relation algebras, Trans. Amer. Math. Soc. 353 (2001), 1403–1425.
  * [12] R. Hirsch and I. Hodkinson, Relation algebras by games, North-Holland. Elsevier Science, 2002.
  * [13] R. Hirsch, M. Jackson, T. Kowalski, Algebraic foundations for qualitative calculi and networks, Theoret. Comput. Sci. 768 (2019), 1–27.
  * [14] A. Inants, J. Euzenat, So, what exactly is a qualitative calculi?, Artificial Intelligence 289 (2020), 103385.
  * [15] P. Jipsen, R. Maddux, and Z. Tuza, Small representations of the relation algebra $\mathfrak{C}_{n+1}^{\\{1,2,3\\}}$, Algebra Universalis 33 (1995), 136–139.
  * [16] J.G. Kalbfleisch and R. G. Stanton, On the maximal triangle-free edge-chromatic graphs in three colors, J. Combinatorial Theory 5 (1968), 9–20.
  * [17] T. Kowalski, Representability of Ramsey relation algebras, Algebra Universalis 74 (2015), 265–275.
  * [18] J.H. Lee, J. Renz, and D. Wolter, StarVars – Effective reasoning about relative directions. In International Joint Conference on Artificial Intelligence (IJCAI), (2013) pp. 976–982.
  * [19] G. Ligozat, Qualitative Spatial and Temporal Reasoning, Wiley 2012.
  * [20] R.C. Lyndon, Relation algebras and projective geometries, Michigan Math. J. 8 (1961), 21–28.
  * [21] R. Maddux, Some varieties containing relation algebras, Trans. Amer. Math. Soc. 272 (1982), 501–526.
  * [22] R. Maddux, Relation algebras. North-Holland. Elsevier Science, Amsterdam, 2006.
  * [23] R. Maddux, Do Ramsey algebras exist? Talk at AMS Sectional Meeting, University of Iowa, Iowa City, March 2011, 18–20,
  * [24] J.D. Monk, On representable relation algebras, Michigan Math. J. 11 (1964) 207–210.
  * [25] J. Nagura, On the interval containing at least one prime number, Proc. Japan Acad. 28 (1952), 177–181.
  * [26] D.H. Perico, P.E. Santos, R.A.C. Bianchi, Guided navigation from multiple viewpoints using qualitative spatial reasoning, Spat. Cogn. Comput. 21 (2021), 143–172.
  * [27] D.A. Randell, Z. Cui, A.G. Cohn, A spatial logic based on regions and connection. In 3rd Int. Conf. on Knowledge Representation and Reasoning. Morgan Kaufmann. (1992) pp. 165–176.
  * [28] J.D.H. Smith, An introduction to Quasigroups and their representations. Chapman and Hall/CRC, 2006.
  * [29] A. Tarski, On the calculus of relations, J. Symb. Logic 6 (1941), 73–89.
  * [30] M. Westphal, J. Hué, S. Wölfl, On the scope of qualitative constraint calculi, in: Proceedings, KI 2014: Advances in Artificial Intelligence – 37th Annual German Conference on AI, Stuttgart, Germany, September 22–26, 2014, 2014, pp. 207–218.