# Properties of Steiner triple systems of order 21

Grahame Erskine and Terry S. Griggs
School of Mathematics and Statistics
The Open University
Walton Hall
Milton Keynes MK7 6AA
UNITED KINGDOM
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Properties of the 62,336,617 Steiner triple systems of order 21 with a non-
trivial automorphism group are examined. In particular, there are 28 which
have no parallel class, six that are 4-chromatic, five that are 3-balanced, 20
that avoid the mitre, 21 that avoid the crown, one that avoids the hexagon and
two that avoid the prism. All systems contain the grid. None have a block
intersection graph that is 3-existentially closed.

MSC2020 classification: 05B07.
Keywords: Steiner triple system of order 21, parallel class, resolvable,
colouring, configuration, cycle structure, independent set, existential
closure.

##  1 Introduction

A _Steiner triple system_ of _order_ $v$, denoted by $\operatorname{STS}(v)$,
is an ordered pair $S=(V,\mathcal{B})$ where $V$ is a _base set_ of _elements_
or _points_ of cardinality $v$, and $\mathcal{B}$ is a collection of _triples_
, also called _blocks_ , which collectively have the property that every pair
of distinct elements of $V$ is contained in precisely one triple. Such systems
exist if and only if $v\equiv 1$ or $3\pmod{6}$; first proved by Kirkman in
1847 [24]. Two Steiner triple systems $(V,\mathcal{B})$ and $(W,\mathcal{D})$
are said to be _isomorphic_ if there exists a one-one mapping $\phi:V\to W$
such that every triple $B\in\mathcal{B}$ maps to a triple
$\phi(B)\in\mathcal{D}$. To within isomorphism the $\operatorname{STS}(7)$ and
$\operatorname{STS}(9)$ are unique. Already in the nineteenth century it was
known that there are two non-isomorphic $\operatorname{STS}(13)$s [4], [38].
The number of non-isomorphic $\operatorname{STS}(15)$s is 80; first determined
by White, Cole and Cummings in 1919 [35] and verified by Hall and Swift in
1955 [18] in one of the first uses of digital computers in Combinatorial
Design Theory. Nearly fifty years then elapsed before Kaski and Östergård [23]
enumerated the number of non-isomorphic $\operatorname{STS}(19)$s; there are
11,084,874,829 which are now stored in compact notation on the Internet [34].
They have been extensively analysed with the results appearing in [2].

Recently, Heinlein and Östergård [19] considered the next order for which
Steiner triple systems exist and determined the number of non-isomorphic
$\operatorname{STS}(21)$s: 14,796,207,517,873,771. It would be good to make a
thorough analysis of these too, but the fact that there are more than a
million times more systems than for $\operatorname{STS}(19)$ seems to make
both storage and computation infeasible in the near future. However, previous
to this enumeration, Kaski [20] had determined all non-isomorphic
$\operatorname{STS}(21)$s having a non-trivial automorphism group, by
comparison a mere 62,336,617. It is feasible to investigate some of their
properties; indeed Kaski himself already did so in the paper (automorphism
groups, anti-Pasch systems). Two further papers [25], [26] also deal
respectively with Kirkman triple systems and sparse systems. It is our aim to
add to this analysis and identify systems which may be of particular interest.
In the interests of economy of space, where such systems already appear in the
literature we will not repeat them but instead point to their reference.
Systems which have not already appeared in the literature will be listed. The
focus will be mainly but not exclusively on parallel classes, colourings and
configurations. For precise definitions of these concepts see later in the
relevant sections. Our investigations also lead to a number of interesting
questions.

When providing listings of particular systems, we will often employ the
following compact notation which is common in the literature, see for example
[6]. The set $V$ of points is taken to be $\\{0,1,2,\ldots,20\\}$. The points
$10,\ldots,20$ are represented by the letters $a,\ldots,k$ respectively. The
70 blocks of an $\operatorname{STS}(21)$ are represented by a string of
symbols $s_{1}s_{2}\ldots s_{70}$. Using the usual lexicographical order, the
symbol $s_{i}$ is the largest element $z_{i}$ in the $i$th triple
$\\{x_{i},y_{i},z_{i}\\}$, where $x_{i}<y_{i}<z_{i}$. The remaining two
elements implicitly have the property that there is no pair
$x^{\prime}_{i}<y^{\prime}_{i}$ such that
$\\{x^{\prime}_{i},y^{\prime}_{i}\\}$ does not appear in an earlier triple,
and either (i) $x^{\prime}_{i}<x_{i}$ or (ii) $x^{\prime}_{i}=x_{i}$ and
$y^{\prime}_{i}<y_{i}$.

##  2 Parallel classes

In an $\operatorname{STS}(v)$, $S=(V,\mathcal{B})$ where $v\equiv 3\pmod{6}$,
a _parallel class_ or _resolution class_ is a set of blocks which contain
every element precisely once. If the blocks of $\mathcal{B}$ can be
partitioned into parallel classes then the $\operatorname{STS}(v)$ is said to
be _resolvable_ and the set of parallel classes is called a _resolution_. Such
an $\operatorname{STS}(v)$ together with the resolution is called a _Kirkman
triple system_ and denoted by $\operatorname{KTS}(v)$. The
$\operatorname{STS}(v)$ is said to be the _underlying_ Steiner triple system
of the $\operatorname{KTS}(v)$. A Steiner triple system may underlie more than
one Kirkman triple system. If an $\operatorname{STS}(v)$ underlies two
$\operatorname{KTS}(v)$s and the latter have the property that every pair of
parallel classes, one from each of the two systems, have either zero or one
block in common then the $\operatorname{STS}(v)$ is said to be _doubly
resolvable_. Kirkman triple systems of order 21 with a non-trivial
automorphism group were considered by Cohen, Colbourn, Ives and Ling [1] and
later by Kokkala and Östergård [25]. The latter paper further considered those
systems whose underlying Steiner triple system has a non-trivial automorphism
group. They obtained the following result.

######  Theorem 2.1.

(Kokkala and Östergård)
The Steiner triple systems of order 21 with a non-trivial automorphism group
underlie 66,937 non-isomorphic Kirkman triple systems with a non-trivial
automorphism group and a further 1,992 Kirkman triple systems having only the
identity automorphism. None of these systems is doubly resolvable.

The reader is referred to the papers and the Tables therein for further
information. In particular Table 8 of [1] and Table 5 of [25] detail how the
$\operatorname{KTS}(21)$ with an automorphism of order 3 and 2 respectively
are distributed amongst the underlying $\operatorname{STS}(21)$. Table 1 shows
the same information for ALL 68,929 $\operatorname{KTS}(21)$ having an
underlying $\operatorname{STS}(21)$ with a non-trivial automorphism group and
may be of interest. There are 55,900 such systems and Table 2 shows the number
of resolutions that all of them have. One system stands out: that with 12,480
resolutions. Not surprisingly it is the one which underlies 18 Kirkman triple
systems and also has 406 parallel classes, the most of any of the
$\operatorname{STS}(21)$s. It is the direct product of the unique
$\operatorname{STS}(7)$ and $\operatorname{STS}(3)$ systems and has
automorphism group of order $168\times 6=1008$. We represent the points of the
system by $V=\mathbb{Z}_{7}\times\\{A,B,C\\}$ and the blocks by
$\mathcal{B}=\\{\\{(i,X),(i+1,Y),(i+3,Z)\\},i\in\mathbb{Z}_{7},\\{X,Y,Z\\}=\\{A,B,C\\}$
or $X=Y=Z\in\\{A,B,C\\},\\{(i,A),(i,B),(i,C)\\},i\in\mathbb{Z}_{7}\\}$. This
system is isomorphic to the cyclic system on the points of $\mathbb{Z}_{21}$
generated by the blocks $\\{0,1,5\\}$, $\\{0,2,10\\}$, $\\{0,3,9\\}$ and
$\\{0,7,14\\}$ under the mapping $i\mapsto i+1$: it is system C3 as listed in
[30].

We remark that the system containing the next largest number of parallel
classes, which is 294, is not resolvable. This system has an automorphism
group of order 72 and is listed below.

2468bcfgjk578cbgfkj867degfik7ihdekj8gfjkihaihkjghiedjkjkceihfgkjhikjhi

#KTS | #STS | #KTS | #STS | #KTS | #STS
---|---|---|---|---|---
1 | 45,604 | 7 | 9 | 13 | 1
2 | 8,629 | 8 | 19 | 14 | 3
3 | 1,025 | 9 | 5 | 15 | 1
4 | 459 | 10 | 3 | 16 | 1
5 | 99 | 11 | 3 | 18 | 1
6 | 37 | 12 | 1 |  |
Table 1: Underlying $\operatorname{STS}(21)$s #Res | #STS | #Res | #STS | #Res | #STS
---|---|---|---|---|---
1 | 44,651 | 13 | 3 | 28 | 2
2 | 9,208 | 14 | 3 | 32 | 4
3 | 1,045 | 15 | 3 | 36 | 1
4 | 639 | 16 | 5 | 44 | 2
5 | 97 | 17 | 1 | 62 | 1
6 | 90 | 18 | 3 | 64 | 1
7 | 15 | 19 | 2 | 264 | 1
8 | 75 | 20 | 3 | 336 | 1
9 | 23 | 21 | 1 | 448 | 1
10 | 7 | 22 | 2 | 12,480 | 1
12 | 8 | 24 | 1 |  |
Table 2: Numbers of resolutions

Turning now to systems with no parallel classes, it is known that there are 12
non-isomorphic 4-rotational $\operatorname{STS}(21)$s, i.e. having an
automorphism consisting of a fixed point and four 5-cycles, and there are
given in [31]. We have determined that there are a total of 28 non-isomorphic
$\operatorname{STS}(21)$s with a non-trivial automorphism which have no
parallel class. The other 16 seem not to be known. All have an automorphism of
order 3; in 9 of these this acts as seven 3-cycles and the other 7 as three
fixed points and six 3-cycles, We list the 16 new systems below.

The 9 systems with seven 3-cycles:

fh6idgkacjge7jihdbkkc8fjbei5acfgjidbhgkj9efhikkjcehicdhedgikjkkjfhjgki

kj69cfedgiid7acghejbe8hdcfk5ekicgjicjdkhdjekhibagfk9hgkfhjkjfighkjiijk

269cikhdjgd7aijefkhbe8kjgciha9chkjibfdikjegjkia9jhgbkfhifgfhdjgekekjki

kj697acfhii87abdfgjb689ehgkgfehkjihcfikjdjgkiikcjfhjdkghiehggfkhijejkk

kj6f7dachii87gedbfjh68cbegkji9gdkfkaehgibfchjdcjhikekfjigijkhkfjgkjikh

26fdejcigke7gkchdjihc8dikfejbajgidk9hkjeiifkejcejgfdgkhfhiedcjhkhkjgik

kj69dcbegiie7a9dcjhbc8eadhkgf9ikjhhjaikfbkjgi8dfikegijchkjfhgkghjfkikj

kj6f7acdgii87gbedhjh689cefkjigfbkekhbgeifahdj8hkgjifijhkjgikfgkhjfkikj

kj6b7cafhii879dbfgja68ebhgkcehfgjkdfhgkjgfhikikjhcfjdkfggeihkijikjejik

The 7 systems with three fixed points and six 3-cycles:

2678cdeijk9abdecjkiijk9abfghgfbaekjhb9dika9jeikjifhigjhhkghgfjkfkgjhik

2678cdeijk9abfghijkdecjkighfcebjgkidk9hjiaifkjdcighehjffkgbkjkijiehhgk

2678cdeijk9abcdejkicdefghijkhgafjikfgbkij9hikj8kdijeijkjckibfhghhggfhk

2678cdeijk9abfghijk786kijhfgjibgekhk9hdigafjehedbgjkcbhkjafikgjikhjfik

2678cdeijk9abdecjkiijkab9hfgcejgfhkdhkfgiifhgjgfeckhdckedjkjiijkikgjhh

2678cdeijk9abdecjkiijk9abfgh5cajhgkbdkhfie9igfjhgfkjfgikhjkgfjihjkikeh

2678cdeijk9abdecjki867ijkhfgjidhgekkehfdicgfejjibkhgkaifhjbghkfgijhkjk

In addition there are 64 systems containing just a single parallel class.

##  3 Colourings

A _(weak) colouring_ of an $\operatorname{STS}(v)$, $S=(V,\mathcal{B})$ is a
mapping $\phi:V\to C$ where $C$ is a set of cardinality $m$ whose elements are
called _colours_ , such that $|\phi(B)|>1$ for all $B\in\mathcal{B}$, i.e. no
block is monochromatic.The system is said to be _$m$ -colourable_. The
_chromatic number_ of $S$, $\chi(S)$ is the smallest value of $m$ for which
$S$ admits a colouring with $m$ colours. We say that the Steiner triple system
is _$m$ -chromatic_. All $\operatorname{STS}(v)$, $7\leq v\leq 19$ are
3-chromatic. However for $v=21$ , there exist 4-chromatic systems. The first
of these was given by Haddad [17] and five further ones were constructed in
[6] by applying various trades to Haddad’s system. Respectively in the order
in which they appear in [6] their automorphism groups have order 108, 12, 12,
4, 3 and 18. Thus the system found by Haddad is the unique
$\operatorname{STS}(21)$ with an automorphism group of order 108. We have
determined that these six systems are the only 4-chromatic
$\operatorname{STS}(21)$s having a non-trivial automorphism group. We have
also tried various methods to try to construct further 4-chromatic
$\operatorname{STS}(21)$s with no success. But with the large number of
$\operatorname{STS}(21)$s it would be highly speculative and indeed rather
foolish to conjecture that these are the only six 4-chromatic
$\operatorname{STS}(21)$s.

With regard to the remaining 3-chromatic $\operatorname{STS}(21)$s, we focus
on the cardinalities of the colour classes. An $\operatorname{STS}(v)$ is said
to be _equitably $m$-chromatic_ if it is $m$-chromatic and the cardinalities
of the colour classes differ by at most one. It is _$m$ -balanced_ if every
$m$-colouring is equitable and _$m$ -unbalanced_ if every $m$-colouring is not
equitable. It was proved in [6] that every 3-chromatic
$\operatorname{STS}(21)$ has a 3-colouring in which the cardinalities of the
colour classes are either $(8,7,6)$ or $(7,7,7)$. Our investigations show that
in fact every 3-chromatic $\operatorname{STS}(21)$ with a non-trivial
automorphism group is equitably 3-chromatic. Further all but five also have a
3-colouring with colour classes with cardinalities $(8,7,6)$. Two of these
systems appear in [6] but the other three were previously unknown. For
completeness we list all five of these 3-balanced $\operatorname{STS}(21)$s
below.

2468bcfgjk56jkcbgfi65ihacegkdahjgik9eifkhjgbekijhcfjdhkifekgdjkijhikhj

2678cdeijk9abfghjkiijkecdfghkjdchgfidehfgcegfh8ikjhkjihjikgedcekijikjk

2468bcfgjk578dehijk867jkchig7ihfgkj8kjihgfcbihkjadeihkgfjkeiedgfkjhikj

2468bcfgjk56jkcbgfi65ihacegkdahkgij9eifjhkgbekijhcfjdhkifekgdjkijhijhk

2468bcfgjk578achijk867cbjkhi7ihdekj8fgkjihhijkgfjkhiegedgfikgfedkjkjih

Let $v\equiv 3\pmod{6}$. A simple counting argument shows that in any
equitable colouring of a 3-chromatic $\operatorname{STS}(v)$, the number of
blocks which contain a point from each of the three colour classes is $v/3$.
Call this set of blocks the _rainbow set_. This is suggestive that the rainbow
set might be a parallel class. We checked this for the 3-chromatic
$\operatorname{STS}(21)$s having a non-trivial automorphism group and found
that all have an equitable 3-colouring in which the rainbow set is NOT a
parallel class. Only 465,006, less than 1% of the total, have such a colouring
where the rainbow set is a parallel class. No system had an equitable
3-colouring based solely on the rainbow set being a parallel class and it is
an interesting question of whether such a system exists among those with only
the identity automorphism. Certainly such systems exist for other orders. The
$\operatorname{STS}(15)$ formed by the point-line design of the projective
geometry $\operatorname{PG}(3,2)$ has up to isomorphism a unique 3-colouring
which is equitable and the rainbow set is a parallel class [33, 9]. Further in
[5], Forbes lists a number of systems which are uniquely equitably
3-colourable.In those of order 39 and 57, the rainbow set is a parallel class.

##  4 Configurations

A $(k,\ell)$-_configuration_ in a Steiner triple system is a collection of
$\ell$ blocks which contain $k$ points. It is said to be _even_ if every point
occurs in an even number of blocks. It is _full_ if no point occurs in just
one block. Configurations with $k=\ell+2$ play a special role in the
structural theory of $\operatorname{STS}(v)$. Apart from the single block, the
smallest example is the so-called _Pasch configuration_ , the unique
configuration with $(k,\ell)=(6,4)$. The four blocks are isomorphic to
$\\{x,y,z\\}$, $\\{x,b,c\\}$, $\\{a,y,c\\}$, $\\{a,b,z\\}$. There are two
$(7,5)$-configurations. One of them, the _mia_ is obtained by extending the
Pasch configuration with one extra block through any pair of uncovered points
and so is not full. The other is the _mitre_ ; five blocks isomorphic to
$\\{x,a,d\\}$, $\\{x,b,e\\}$, $\\{x,c,f\\}$, $\\{a,b,cz\\}$, $\\{d,e,f\\}$.
There are five $(8,6)$-configurations (and one $(7,6)$-configuration) but
three are obtained by extending the mia or the mitre and are not full. The
other two (full) configurations are the _6-cycle_ or _hexagon_ , six blocks
isomorphic to $\\{x,a,b\\}$, $\\{x,c,d\\}$, $\\{x,e,f\\}$, $\\{y,a,f\\}$,
$\\{y,b,c\\}$, $\\{y,d,e\\}$. and the _crown_ , six blocks isomorphic to
$\\{x,y,z\\}$, $\\{x,a,b\\}$, $\\{y,c,d\\}$, $\\{z,a,c\\}$, $\\{w,x,d\\}$,
$\\{w,y,b\\}$. Steiner triple systems which do not contain some or all of
these configurations are of particular interest. For $n\geq 4$, an
$\operatorname{STS}(v)$ with the property that it contains no
$(\ell+2,\ell)$-configuration for $4\leq\ell\leq n$ is said to be
$n$-_sparse_.

& Pasch Mitre Hexagon Crown

Figure 1: The full $(\ell+2,\ell)$ configurations on at most six blocks

& Grid Prism

Figure 2: The even $(9,6)$-configurations

So a 4-sparse $\operatorname{STS}(v)$ is just one which contains no Pasch
configurations. Such systems are more commonly known as _anti-Pasch_ and they
exist for all $v\equiv 1$ or $3\pmod{6}$, $v\neq 7,13$ [29], [16]. Analogously
a system which contains no mitres is called _anti-mitre_ and a 5-sparse
$\operatorname{STS}(v)$ is one which avoids both the Pasch and the mitre
configurations. Anti-mitre $\operatorname{STS}(v)$ exist for all $v\equiv 1$
or $3\pmod{6}$, $v\neq 9$ but the exact spectrum for 5-sparse
$\operatorname{STS}(v)$ is not completely determined, [3], [28], [10], [11],
[36], [37]. Kokkala and Östergård [26] have enumerated all anti-Pasch
$\operatorname{STS}(21)$s; there are 83,003,869 non-isomorphic such systems,
of which just three are 5-sparse and none are 6-sparse. See [27] for a
listing. Previous to this, Kaski [20] had determined that there are 958 non-
isomorphic anti-Pasch $\operatorname{STS}(21)$s with a non-trivial
automorphism group. Just one of these is cyclic: it is system C2 as listed in
[30]. On the base set $V=\mathbb{Z}_{21}$ it can be obtained by the action of
the mapping $i\mapsto i+1$ on the blocks $\\{0,1,3\\}$, $\\{0,4,12\\}$,
$\\{0,5,15\\}$, $\\{0,7,14\\}$.

On the same data set, our investigations show that there are 20 non-isomorphic
anti-mitre systems including the three that are 5-sparse and 21 systems which
do not contain the crown including one of those which is anti-mitre. This
system which avoids both the mitre and the crown is cyclic and on the base set
$V=\mathbb{Z}_{21}$ is obtained by the action of the mapping $i\mapsto i+1$ on
the blocks $\\{0,1,5\\}$, $\\{0,2,13\\}$, $\\{0,3,9\\}$, $\\{0,7,14\\}$. It is
system C5 as listed in [30]; its full automorphism group has order 882. We
return to this system later in the paper. There is also a unique system
containing no hexagon, listed below:

2468bcfgjkde78afgik78hijkcegjahegki9kidjfhgbdikfcehjgjdhkkfiejihhikjkj

Turning now to systems containing the largest numbers of these configurations,
the $\operatorname{STS}(21)$ with a non-trivial automorphism group having the
largest number of Pasch configurations is the unique system with automorphism
group of order 108 listed below; it contains 117 Pasch configurations. This
system has one fixed point (0) and three further point orbits of sizes 9, 9
and 2 respectively.

2468bcfgjk578achijk867cbjkhi7ihfgkj8dekjihhijkgfjkhiegedgfkjgfedikkjih

The largest number of mitres in any such system is 252, occurring in 12
systems, Remarkably, all also contain precisely 252 hexagons and no crowns.
Two of these systems are cyclic: they are systems C1 and C3 as listed in [30].
On the base set $V=\mathbb{Z}_{21}$ they can be obtained by the action of the
mapping $i\mapsto i+1$ on the blocks $\\{0,1,3\\}$, $\\{0,4,12\\}$,
$\\{0,5,11\\}$, $\\{0,7,14\\}$ and $\\{0,1,5\\}$, $\\{0,2,10\\}$,
$\\{0,3,9\\}$, $\\{0,7,14\\}$ respectively. Of the remainder, one is the
unique Pasch-maximal system described above with an automorphism group of
order 108. The others have automorphism groups varying in order from 6 to 54;
none is point-transitive.

There is a unique $\operatorname{STS}(21)$ with a non-trivial automorphism
group having the largest number of crowns. It contains 396 crowns, has
automorphism group of order 18 and is listed below.

2468bcfgjkbcdejkagi9afghicekh7fjigk8igkhjfaekgj9dfjkcdikbehjijhhikjikh

Possibly of greatest interest though is the unique system having the greatest
number of hexagons, 441 in total. It is the same system which has no mitres or
crowns listed above.

Turning now to even configurations, the smallest (least number of blocks) is
obviously the Pasch configuration. The next smallest are two
$(9,6)$-configurations, the _grid_ and the _prism_. Respectively the blocks
are isomorphic to $\\{a,b,c\\}$, $\\{\ell,m,n\\}$, $\\{x,y,z\\}$,
$\\{a,\ell,x\\}$, $\\{b,m,y\\}$, $\\{c,n,z\\}$ and $\\{a,b,n\\}$,
$\\{a,c,m\\}$, $\\{b,c,\ell\\}$, $\\{\ell,y,z\\}$, $\\{m.x.z\\}$,
$\\{n,x,y\\}$. In [12], Fujiwara and Colbourn proved that every Steiner triple
system contains an even configuration of cardinality 8 or less. It follows
therefore that systems avoiding either the grid of prism are of interest.
However little seems to be known. The unique $\operatorname{STS}(7)$ avoids
both configurations trivially because it does not contain enough points and
the unique $\operatorname{STS}(9)$ avoids the prism but not the grid. It is
readily verified by computer that both $\operatorname{STS}(13)$s and all 80
$\operatorname{STS}(15)$s contain both grids and prisms. In [2], this was
extended to show that the same is true for all $\operatorname{STS}(19)$s.

Investigating the $\operatorname{STS}(21)$s with a non-trivial automorphism
group, we can report that there is no system which avoids the grid. However
there are two systems which avoid the prism. One of these is the cyclic system
C5 and the other is the unique system with automorphism group of order 294. It
is also one of the 21 systems which do not contain the crown. It is listed
below.

2468acegik56ijbghfk659fkdjihcehdgkjkhfcijggajkehidbeifjkbhjcikkijhfjgk

With regard to systems containing most grids and prisms, the largest number of
grids in an $\operatorname{STS}(21)$ with a non-trivial automorphism group is
798 which occurs in two systems, both of which are cyclic (C1 and C3). The
largest number of prisms is 1773, occurring in the unique system with
automorphism group of order 54 and listed below.

2468acegik857kfehij678gjidhk7bcfgjk8idkfjhdejkhichgkfjhifgjkebjgikjkhi

##  5 Pasch trades

The Pasch configuration is a _trade_ , i.e. it can be replaced in a Steiner
triple system by a different collection of blocks containing the same pairs,
possibly to create a non-isomorphic Steiner triple system. Specifically the
blocks $\\{x,y,z\\}$, $\\{x,b,c\\}$, $\\{a,y,c\\}$, $\\{a,b,z\\}$ are replaced
by the blocks $\\{a,b,c\\}$, $\\{a,y,z\\}$, $\\{x,c,z\\}$, $\\{x,y,c\\}$. It
is known that any one of the 79 $\operatorname{STS}(15)$s which contain a
Pasch configuration can be transformed to any other by a sequence of such
Pasch trades [13].

This led the authors of [14] to define the concept of _twin Steiner triple
systems_ which are two $\operatorname{STS}(v)$s, each of which contains
precisely one Pasch configuration which when switched produces the other
system. Each twin of a pair of twin Steiner triple systems has the same
automorphism group. However the twins themselves need not be isomorphic. When
they are, appropriately they are called _identical twins_. There are 838 non-
isomorphic Steiner triple systems with a non-trivial automorphism group which
contain one Pasch configuration, all in fact having an automorphism of order
3. This includes six pairs of twins which are listed below but no identical
twins. There does however exist a pair of identical twin
$\operatorname{STS}(21)$s, see [14], necessarily of course having only the
identity automorphism. There are no systems containing precisely one hexagon
(which also is a trade) or one crown, and just one system containing one
mitre, given below.

The six pairs of twin systems:

kj69cfegihid7acgjhfbe8hdfkggfaihjkhjbfik9kgjiedbikcbjiajkkeieijdjkhghk

269cfegihkd7acgjhfkbe8hdfkgjgfaihjkhjbfik9kgjiedbikcbjiajkkeieijdjkhgh

kj69cfbdhiid7a9gefjbe8hacgka9ikjfhbijgkhkjhigbaefj9dgkheihgikjfijkkjik

269cfbdhikd7a9gefjkbe8hacgkja9ikjfhbijgkhkjhigbaefj9dgkheihgikjfijkkji

ed69chbjikcd7a9fkjibe8gaijkji8cfkhk8dgih7hejgejfhkkcgfjdighkgfjhkiejki

269chbjeikd7a9fkejibe8gaidjkji8cfkhk8dgih7hejgejfhkkcgfjdighkgfjhkijki

26bcgfakjid79ghbkijae8fhbjik87gehik6chfjkdfgkjkjiehdifjcedgkekjikjighh

a96bcgfkjibd79ghkijae8fhjik87gehik6chfjkdfgkjkjiehdifjcedgkebkjikjighh

26bcgfakjid79ghbkijae8fhbjik87gcfjk6dhgkjefhikikjchejfkdeegidikjikjhgh

a96bcgfkjibd79ghkijae8fhjik87gcfjk6dhgkjefhikikjchejfkdeegidbikjikjhgh

26h7jacfik87fkdbjgig68ibehkjikafdejjbegdk9cheidcjihgejkfhikghgkhifjkjk

a96h7jcfikb87fkdjgig68iehkjikafdejjbegdk9cheidcjihgejkfhikghbgkhifjkjk

The unique system containing a single mitre:

2678cdeijk9abfghijkdeckijghfjibakfhkb9giha9hjg8jhgikjfhifkgbekiejidkjk

The authors of [2] extended this analysis. They considered Steiner triple
systems containing precisely two Pasch configurations, say P and Q, such that
when P (respectively Q) is switched what is obtained is a Steiner triple
system containing just one Pasch configuration P’ (respectively Q’). Clearly P
and Q must have a single common block. (They cannot have two common blocks;
otherwise the Steiner triple system would contain at least one further Pasch
configuration.) Considering only the $\operatorname{STS}(21)$s with a non-
trivial automorphism group having precisely two Pasch configurations, there
are four systems which have this property. They are listed below. In all four
cases, the system admits an automorphism which exchanges its two Pasch
configurations P and Q, and thus the two switched systems containing a single
Pasch configuration are isomorphic.

2468acegik69beghjikcfa8jdehkdgkfbhjjaheigkicgkhcbgijkkdfijhfejkfijkhij

2468acegik69ejcfhgkgjh8kicdfchkeifj7bidgkh9jgkiadjikhgiefbhgjkfjhkjikj

2468acegikh8adjcfgk9igkcdfejd7egkijkbdhjgff9ijhijefheigkcjhkdkihkhkijj

2468acegikajhdf9gekgekihbcjfeb9hjki8gcdfikafdijjfkcheikdkgjhjikihjghjk

This situation does not occur with the $\operatorname{STS}(19)$s where there
are nine such systems, but in every case the two systems containing a single
Pasch configuration are non-isomorphic; see [2]. For the
$\operatorname{STS}(21)$s, a system containing two Pasch configurations which
when either is switched gives a system with one Pasch configuration and the
two systems are not isomorphic is given below. The systems of course only have
the identity automorphism.

2468acegikgkfbh9jdich8djegfkajkhdifcfeaigjbgijkighkecfgdjkikjeihjhkkhj

##  6 Other properties

Let $(V,\mathcal{B})$ be an $\operatorname{STS}(v)$. For each pair $x,y\in V$,
define a graph $G_{x,y}$ with vertex set $G\setminus\\{x,y,z\\}$ where
$\\{x,y,z\\}\in\mathcal{B}$, and two vertices $u,v$ are joined by an edge if
either $\\{x,u,v\\}\in\mathcal{B}$ or $\\{y,u,v\\}\in\mathcal{B}$. The graph
$G_{x,y}$ is a union of cycles of even length greater than 2, and these can be
recorded as a list of cycle lengths in non-decreasing order. The _cycle
structure_ of the Steiner triple system is the collection of all such _cycle
lists_. Within this framework, the greatest interest is in Steiner triple
systems in which all cycle lists are the same; such systems are called
_uniform_. Of even greater interest are uniform Steiner triple systems in
which each cycle list is $v-3$; such systems are called _perfect_ and only 14
of these are known [15], [7]. Kaski [21], [22] has determined that there is no
perfect $\operatorname{STS}(21)$. Amongst the $\operatorname{STS}(21)$s with a
non-trivial automorphism group, we have determined that there is also no
uniform system. Indeed all systems except one have at least three different
cycle structures in their cycle lists. Not surprisingly the exception is the
system C5 as listed in [30] which contains the largest number of hexagons,
There are 147 pairs with cycle structure $6,6,6$ and 63 pairs with cycle
structure $4,14$.

An _independent set_ $I\subset V$ in a Steiner triple system
$S=(V,\mathcal{B})$ is a set of points with the property that no block of
$\mathcal{B}$ is contained in $I$. A _maximum independent set_ is an
independent set of maximum cardinality. It is know that a maximum independent
set of an $\operatorname{STS}(21)$ has cardinality 8, 9 or 10 [7]. The number
of non-isomorphic $\operatorname{STS}(21)$s with a non-trivial automorphism
group having each of these values is 15,614,086, 43,050,614 and 3,671,917
respectively.

The _block intersection graph_ of a Steiner triple system has one vertex for
each block and an edge between two vertices when the corresponding blocks
intersect. A graph $G=(W,\mathcal{E})$ is _n-existentially closed_ if for
every $n$-element subset $S\subseteq W$ of vertices and for every subset
$T\subseteq S$, there exists a vertex $x\notin S$ that is adjacent to every
vertex in $T$ and not adjacent to every vertex in $S\setminus T$. The block
intersection graph of an $\operatorname{STS}(v)$ is 2-existentially closed if
and only if $v\geq 13$ [8], [32]. It cannot be 3-existentially closed for
$v\leq 15$ or $v\geq 25$. There are two $\operatorname{STS}(19)$s which
possess 3-existentially closed block intersection graphs [2]. So the only
order for which this property is not determined is $v=21$. We can report that
no $\operatorname{STS}(21)$ with a non-trivial automorphism group has a block
intersection graph which is 3-existentially closed.

##  7 Extremal systems

Much of this paper has been concerned with identifying
$\operatorname{STS}(21)$s with a non-trivial automorphism group which are
extremal with respect to a certain property. As we have shown, and perhaps not
surprisingly, some systems are extremal with respect to a number of
properties. We collect these systems together in this section which we hope
will provide a succinct summary of the main results, presented by system
rather than property. There are seven systems in all, four of which are
cyclic.

Unique system with automorphism group of order 54. This is the unique system
containing the largest number of prisms (1773) and one of the 12 systems
containing the largest number of mitres (252).

Unique system with automorphism group of order 108. This is the unique system
containing the largest number of Pasch configurations (117) and one of the 12
systems containing the largest number of mitres (252). It has no crowns.

Unique system with automorphism group of order 294. This is one of the two
systems which contains no prisms. It also has no crowns.

Cyclic system C1 with automorphism group of order 504. This is one of the two
systems which contains the largest number of grids (798) and one of the two
_cyclic_ systems which contains the largest number of mitres (252). It has no
crowns.

Cyclic system C2 with automorphism group of order 21. This is the unique
_cyclic_ anti-Pasch $\operatorname{STS}(21)$.

Cyclic system C3 with automorphism group of order 1008. This is the other
system which contains the largest number of grids (798), the other _cyclic_
system which contains the largest number of mitres (252) and no crowns. It is
also the direct product of the Steiner triple systems $\operatorname{STS}(7)$
and $\operatorname{STS}(3)$ and has the largest number of resolutions (12,480)
and parallel classes (406) and underlies the most Kirkman triple systems (18).

Cyclic system C5 with automorphism group of order 882. This system is extremal
with respect to a number of properties. It is the unique system which avoids
both the mitre and the crown and is also the other system which contains no
prisms. It is the unique system containing the largest number of hexagons
(441) and the only system with just two cycle structures.

##  8 Further questions

The analysis of the $\operatorname{STS}(21)$s with a non-trivial automorphism
group presented in this paper naturally raises a number of questions relating
to ALL $\operatorname{STS}(21)$s which would be answered if and when a
complete investigation of these systems becomes possible. Some however might
be resolved by alternative means, though we do not underestimate the tedium or
difficulty of doing so. The first question comes from Section 2 and is simply
stated.

Question 1. Does there exist a doubly resolvable $\operatorname{STS}(21)$?

A number of questions are raised from Section 3. The chromatic number of all
$\operatorname{STS}(21)$s with a non-trivial automorphism group is 3, except
for six systems which are 4-chromatic. It would be good to know whether these
are the only systems with this property.

Question 2. Does there exist a 4-chromatic $\operatorname{STS}(21)$ with a
trivial automorphism group?

In relation to 3-chromatic systems, we have noted that all
$\operatorname{STS}(21)$s have a colouring in which the cardinalities of the
colour classes are either $(8,7,6)$ or $(7,7,7)$. Amongst the
$\operatorname{STS}(21)$s with a non-trivial automorphism group, all have a
colouring with colour classes of cardinalities $(7,7,7)$, i.e. they are
equitably 3-chromatic, and all but five also have a colouring with colour
classes of cardinalities $(8,7,6)$. These five systems having only an
equitable 3-colouring are 3-balanced. This leads to the next two questions.

Question 3. Do there exist further 3-balanced $\operatorname{STS}(21)$s?

Question 4. Is every 3-chromatic $\operatorname{STS}(21)$ also equitably
3-chromatic?

Also in Section 3, in an equitable colouring of a 3-chromatic
$\operatorname{STS}(v)$, where $v\equiv 3\pmod{6}$, we introduced the concept
of a rainbow set. This has the same cardinality ($v/3$) as that of a parallel
class. However none of the $\operatorname{STS}(21)$s under consideration had a
colouring in which the rainbow set is a parallel class and leads to the final
question from the section.

Question 5. Does there exist a 3-chromatic $\operatorname{STS}(21)$ which has
an equitable colouring in which the rainbow set is a parallel class?

The main questions to arise from Section 4 concern the numbers of systems
which avoid the mitre, crown, hexagon, grid or prism or any of these in
combination. As we have noted, there are 83,003,689 anti-Pasch
$\operatorname{STS}(21)$s of which just 958 have a non-trivial automorphism
group. The number of anti-mitre, anti-crown and anti-hexagon systems with a
non-trivial automorphism group are 20, 21 and 1 respectively which may
indicate that there are not too many of such systems in total. But the most
interesting problems concern the grid and the prism.

Question 6. Does there exist an anti-grid $\operatorname{STS}(21)$?

Question 7. Are there any anti-prism $\operatorname{STS}(21)$s other than the
two identified in this paper?

Referring to Section 5, we recall that Pasch trades partition the set of non-
isomorphic $\operatorname{STS}(21)$s into equivalence classes. Based on
admittedly very limited evidence from the situations for the
$\operatorname{STS}(15)$s and $\operatorname{STS}(19)$s, the expectation is
probably that most systems will be in one gigantic class (the _peloton_ to
borrow a term from cycling) with some smaller classes such as twins and other
small sets of systems. But this may not be the case; the peloton may be
divided and the smaller classes may in fact contain thousands or even millions
of systems, given the huge number of non-isomorphic $\operatorname{STS}(21)$s.
A complete determination of these equivalence classes seems to be totally
infeasible but any further information would undoubtedly be welcome.

Finally from section 6, the main question concerns whether there exists an
$\operatorname{STS}(21)$ whose block intersection graph is 3-existentially
closed? As we noted $v=21$ is the only order for which this is not determined
and we have shown that the answer is in the negative for
$\operatorname{STS}(21)$s with a non-trivial automorphism group. So our final
question is the following.

Question 8, Does there exist an $\operatorname{STS}(21)$, necessarily having
only the identity automorphism, whose block intersection graph is
3-existentially closed?

Given the total number of $\operatorname{STS}(21)$s, we have been reluctant to
make conjectures concerning the above questions but for this final one we
would be surprised if such a system exists.

## Acknowledgements

We thank Petteri Kaski for making available to us the systems having non-
trivial automorphism group identified in [20], and Patric Östergård for
helpful discussions during the drafting of this paper.

## References

  * [1] M. B. Cohen, C. J. Colbourn, L. A. Ives and A. C. H. Ling, _Kirkman triple systems of order 21 with nontrivial automorphism group_ , Math. Comp. 71 (2002), 873 – 881.
  * [2] C. J. Colbourn, A. D. Forbes, M. J. Grannell. T. S. Griggs, P. Kaski, P. R. J. Östergård, D. A. Pike and O. Pottonen, _Properties of the Steiner Triple Systems of order 19_ , Electron. J. Combin. 17 (2010), #R98.
  * [3] C. J. Colbourn, E. Mendelsohn, A. Rosa and J. Širáň, _Anti-mitre Steiner triple systems_ , Graphs Combin. 10 (1994), 215 – 224.
  * [4] V. De Pasquale, _Sui sistemi ternari di 13 elementi_ , Rend. R. Ist. Lombardo Sci. Lett. 32 (1899), 213 – 221.
  * [5] A. D. Forbes, _Uniquely 3-colourable Steiner triple systems_ , J. Combin. Theory Ser. A 101 (2003), 49 –68.
  * [6] A. D. Forbes, M. J. Grannell and T. S. Griggs, _On colourings of Steiner triple systems_ , Discrete Math. 261 (2003), 255 – 276.
  * [7] A. D. Forbes, M. J. Grannell and T. S. Griggs, _Independent sets in Steiner triple systems_ , Ars Combin. 72 (2004), 161 – 169.
  * [8] A. D. Forbes, M. J. Grannell and T. S. Griggs, _Steiner triple systems and existentially closed graphs_ , Electron. J. Combin. 12 (2005), #R42.
  * [9] J. Fugère, L. Haddad and D. Wehlau, _5-chromatic Steiner triple systems_ , J. Combin. Des. 2 (1994), 287 – 299.
  * [10] Y. Fujiwara, _Constructions for anti-mitre Steiner triple systems_ , J. Combin. Des. 13 (2005), 286 – 291.
  * [11] Y. Fujiwara, _Infinite classes of anti-mitre and 5-sparse Steiner triple systems_ , J. Combin. Des. 14 (2006), 237 – 250.
  * [12] Y. Fujiwara and C. J. Colbourn, _A combinatorial approach to X-tolerant compaction circuits_ , IEEE Trans. Inform. Theory 56 (2010), 3196 –3026.
  * [13] P. B. Gibbons, _Computing Techniques for the Construction and Analysis of Block Designs_ , Ph.D. thesis, University of Toronto (Department of Computer Science, University of Toronto Technical Report No. 92) (1976).
  * [14] M. J. Grannell, T. S. Griggs and J. P. Murphy, _Twin Steiner triple systems_ , Discrete Math. 167/168 (1997), 341 – 352.
  * [15] M. J. Grannell, T. S. Griggs and J. P. Murphy, _Some new perfect Steiner triple systems_ , J. Combin. Des. 7 (1999), 327 – 330.
  * [16] M. J. Grannell, T. S. Griggs and C. A. Whitehead, _Anti-Pasch Steiner triple systems_ , J. Combin. Des. 8 (2000), 300 – 309.
  * [17] L. Haddad, _On the chromatic numbers of Steiner triple systems_ , J. Combin. Des, 7 (1999), 1 – 10.
  * [18] M. Hall and J. D. Swift, _Determination of Steiner triple systems of order 15_ , Math. Tables Aids Comput. 9 (1955), 146 – 152.
  * [19] D. Heinlein and P. R. J. Östergård, _Enumerating Steiner Triple Systems_ , https://arxiv.org/abs/2303.01207.
  * [20] P. Kaski, _Isomorph-free exhaustive generation of designs with prescribed groups of automorphisms_ , SIAM J. Discrete Math. 19 (2005), 664 – 690.
  * [21] P. Kaski, _Nonexistence of perfect Steiner triple systems of orders 19 and 21_ , Bayreuth Math. Schr. 74 (2005), 130 –135.
  * [22] P. Kaski, V. Mäkinen and P. R. J. Östergård, _The cycle switching graph of the Steiner triple systems of order 19 is connected_ , Graphs Combin. 27 (2011), 539 –546.
  * [23] P. Kaski and P. R. J. Östergård, _The Steiner triple systems of order 19_ , Math. Comp. 73 (2004), 2075 – 2092.
  * [24] T. P. Kirkman, _On a problem in combinations_ , Cambridge and Dublin Math. J. 2 (1847), 191 – 204.
  * [25] J. I. Kokkala and P. R. J. Östergård, _Kirkman triple systems with subsystems_ , Discrete Math. 343 (2020), 111960.
  * [26] J. I. Kokkala and P. R. J. Östergård, _Sparse Steiner triple systems of order 21_ , J. Combin. Des. 29 (2021), 75 – 83.
  * [27] J. I. Kokkala and P. R. J. Östergård, _Dataset for Sparse Steiner triple systems of order 21_ , Zenodo (June 18, 2020), https://doi.org/10.5281/zenodo.3899950/, accessed Oct. 2023.
  * [28] A. C. H. Ling, _A direct product construction for 5-sparse triple systems_ , J. Combin. Des. 5 (1997), 443 – 447.
  * [29] A. C. H. Ling, C. J. Colbourn, M. J. Grannell and T. S. Griggs, _Construction techniques for anti-Pasch Steiner triple systems_ , J. London Math. Soc. 61 (2000), 641 – 657.
  * [30] R. A. Mathon, K. T. Phelps and A. Rosa, _Small Steiner triple systems and their properties_ , Ars Combin. 15 (1983), 3–110.
  * [31] R. A. Mathon and A. Rosa, _The 4-rotational Steiner and Kirkman triple systems of order 21_ , Ars Combin. 17A (1984), 241 – 250.
  * [32] N. A. McKay and D. A. Pike, _Existentially closed BIBD Block-Intersection Graphs_ , Electron. J. Combin. 14 (2007), #R70.
  * [33] J. Pelikán, _Properties of balanced incomplete block designs_ in; Combinatorial Theory and its Applications III, Colloq. Math. Soc. J. Bolyai 4 (1969), 869 – 889.
  * [34] O. Pottonen, _Classification of Steiner triple systems of order 19_ , https://pottonen.kapsi.fi/sts19/, accessed Sep. 2023.
  * [35] H. S. White, F. N. Cole and L. D. Cummings, _Complete classification of the triad systems on fifteen elements_. Memoirs Nat. Acad. Sci. U.S.A., 2nd memoir, 14 (1919), 1 – 89.
  * [36] A. J. Wolfe, _The resolution of the anti-mitre Steiner triple system conjecture_ , J. Combin. Des. 14 (2006), 229 – 236.
  * [37] A. J. Wolfe, _The existence of 5-sparse Steiner triple systems of order_ $n\equiv 3\pmod{6}$, $n\notin\\{9,15\\}$, J. Combin. Theory Ser. A 115 (2008), 1487 – 1503.
  * [38] K. Zulauf, _Über Tripelsysteme von 13 Elementen_ , Dissertation Giessen, Wintersche Buchdruckerei, Darmstadt (1897).