Linearly Derived Steiner Triple Systems.
We attach a graph to every Steiner triple system. The chromatic number of this graph is related to the possibility of extending the triple system to a quadruple system. For example, the triple systems with chromatic number one are precisely the classical systems of points and lines of a projective geometry over the two-element field, the Hall triple systems have chromatic number three (and, as is well-known, are extendable) and all Steiner triple systems whose graph has chromatic number two are extendable. We also give a configurational characterization of the Hall triple systems in terms of mitres.
Introduction
In November of 1852 Steiner [32] posed an infinite series of questions concerning
what are now known as Steiner triple systems. The second of these
questions asked whether or not it was always possible, given a Steiner triple
system on n points, to introduce n(n 4-subsets of the underlying
set of the given triple system with the property that no one of these
4-subsets contained a triple and, on the other hand, each of the 3-subsets of
the underlying set not a triple were in one of the chosen 4-subsets (necessarily
unique). In other words he asked whether or not every Steiner triple system
extends to a Steiner quadruple system. Triple systems that do extend are
now known as derived triple systems. 1
Despite an enormous effort, especially in the last twenty years, not a great
deal of progress has been made in answering this second question, but it is
known that all Steiner triple systems on fifteen or fewer points are derived
[10, 25] - a result obtained by computer attack.
We here introduce a rather restricted notion of "derived" for Steiner triple
systems. The ideas were inspired, indeed flowed naturally from, the binary
view of Steiner triple systems taken in [2]. We call a triple system possessing
such an extension to a Steiner quadruple system linearly derived . Although
The author wishes especially to thank Paul Camion and Pascale Charpin. The
research atmosphere that they have created at Projet Codes, INRIA surely contributed to
this investigation, the bulk of which took place during the Spring of 1995 while the author
was a visitor there.
Apparently Pl-ucker in 1835 had not only defined triple systems but had even asked
about extending them to quadruple systems and Pl-ucker's work may have been the inspiration
for Steiner's paper. See [37].
not all Steiner triple systems are linearly derived, all the geometric 2 systems
are - and many, many others too.
If a Steiner triple system is linearly derived so are any subsystems it may
possess. Hence whenever one finds a Steiner triple system that is not linearly
derived one knows that any system of which it is a subsystem cannot be
linearly derived.
To find a "linear extension" of a Steiner triple system one restricts one's
attention to those 4-subsets of the underlying set of the system that are
symmetric differences of two triples - that is, those 4-subsets that are the
support of the binary sum of the incidence vectors of two triples. We call
such 4-subsets linear 4-subsets.
Being linearly derived is related to the existence of quadrilaterals (the
unique four-line configurations on six points) and non-Fano planes (the
unique six-line configurations on seven points) in the triple system. In par-
ticular, the non-Fano planes of the system are in one-to-one correspondence
with those linear 4-subsets of the system that can be seen in three distinct
ways as the symmetric difference of two triples.
In order to more easily express and understand the results we present,
we attach a graph to each Steiner triple system. The vertices of the graph
are the linear 4-subsets of the system with two joined by an edge if the two
4-subsets intersect in three points. The geometric systems of points and lines
of projective spaces over F 2
are characterized as those Steiner triple systems
whose graph is monochromatic (that is, there are no edges).
Among the quadrilateral-free Steiner triple systems one finds the Hall
triple systems (which can be viewed as generalizations of the geometric systems
of points and lines of the affine spaces over F 3
We show that these
systems have graphs with chromatic number three and that they are linearly
derived. In fact, any quadrilateral-free Steiner triple system whose graph
has chromatic number three will be linearly derived, but it may be that the
Hall triple systems are characterized among the quadrilateral-free systems as
those whose graph has chromatic number three.
There are Steiner triple systems whose graphs have chromatic number
two; they are linearly derived and seem to form an interesting class of systems,
which, as far as we know, have never been considered. A linear extension
Following [5] we call a Steiner triple system geometric if it is the system of lines of
a projective geometry over the binary field or an affine geometry over the ternary field.
of such a system can be constructed from the quadrilaterals and non-Fano
planes of the systems - in fact, from the quadrilaterals alone. Indeed, one
of the most surprising outcomes - to the author at least - of this investigation
was the realization that if a Steiner triple system contains enough
Fano planes and proper non-Fano planes, then it is linearly derived. This
result, Theorem 4.3, may be viewed as a generalization of the Stinson-Wei
[33] result characterizing the geometric binary Steiner triple systems in terms
of the number of quadrilaterals.
Probably the vast majority of systems have graphs with chromatic number
greater than three. Since the maximum possible degree of the graph of
a Steiner triply system is eight, it follows from Brooks's theorem [6, Theorem
8.4] that the chromatic number of the graph is at most eight. We do not
have an example of a linearly derived Steiner triple system whose graph has
chromatic number greater than three. The cyclic system of order 5 (on 13
points) has chromatic number greater than three and is not linearly derived;
the quadrilateral-free system of order 6 (on 15 points) also has chromatic
number greater than three.
Mitres, the unique five-line configurations on seven points with two "par-
allel" lines, play a role in the discussion to follow. We also give a configurational
characterization of the Hall triple systems couched in terms of mitres.
Just as the geometric binary systems are characterized as those systems with
the maximum number of quadrilaterals, the Hall triple systems are characterized
as those systems with the maximum number of mitres.
Only an elementary knowledge of design theory (such as can be found,
for example, in Chapter 1 of [4]) and graph theory are necessary in order to
read this paper. Any of the standard references on design theory and graph
theory will contain the necessary background. Moreover, we define most
notions as they are introduced. The only departure from the nomenclature
of the vast existing literature on Steiner triple systems is that we use "order"
in the design-theory sense; it does not denote the number of points n of the
triple system, but rather (n \Gamma 3)=2.
Linear 4-subsets and their graph
Recall that a 4-subset of the underlying set of a Steiner triple system is
linear if it is the symmetric difference of two triples. The name comes from
the binary view of Steiner triple systems: a linear 4-subset is the support of
a weight-four vector in the binary code of the triple system that is the sum
of the incidence vectors of two triples.
Linear 4-subsets come in three flavors according to whether they arise
just one way, two ways, or three ways as a symmetric difference (or sum).
Clearly three is the maximum number, since a 4-set splits in exactly three
ways as the disjoint union of two 2-subsets. We will distinguish these linear
4-subsets by calling them singly-linear, doubly-linear and triply-linear,
respectively.
A triangle in a Steiner triple system is simply a 3-subset of the underlying
set which is not a triple of the system. A Steiner triple system on n points
triangles. A triangle can be expanded to a linear 4-subset in three ways,
clearly, but the resulting linear 4-subsets might not differ.
In fact, a triangle is a subset of one, two, or three linear 4-subsets so
triangles, too, come in three flavors: a Type I triangle is contained in exactly
one linear 4-subset; a Type II triangle is in exactly two linear 4-subsets; a
Type III triangle is in exactly three linear 4-subsets.
It is a simple matter to check that all four 3-subsets of a linear 4-subset
are triangles, that all four 3-subsets of a triply-linear 4-subset are of Type I,
and that all four 3-subsets of a doubly-linear 4-subset are of Type II. But
a singly-linear 4-subset could contain both Type II and Type III triangles.
Sometimes a singly-linear 4-subset contains only Type II triangles. In fact a
singly-linear 4-subset contains only Type II triangles if and only if its valency
in the graph is four. Of course, in a quadrilateral-free Steiner triple system
all linear 4-subsets are singly-linear and contain only Type III triangles. In
such systems, the valency of every vertex is eight.
denote the set of singly-linear 4-subsets, L 2
denote the set of
doubly-linear 4-subsets, and L 3
denote the set of triply-linear 4-subsets. Sim-
ilarly, \Delta I
will denote the set of Type I triangles, \Delta II
will denote the set of
Type II triangles, and \Delta III
will denote the set of Type III triangles.
The number of linear 4-subsets of a Steiner triple system on n points
depends, in general, not only on n but on the system. There are, however,
ways to form the symmetric difference of two triples. The following lemma
summarizes the easily proven relationships among the cardinalities of the sets
just described and some simple consequences of these relationships.
Lemma 2.1 1. jL
2.
3.
4.
5.
A quadrilateral of a Steiner triple system is the four-line configuration 3
containing exactly six points. Here is the configuration:
s
s
s
s
Doubly-even 4-subsets are obviously related to quadrilaterals but the notions
are different: a quadrilateral gives rise to three doubly-linear 4-subsets
and the triply-linear 4-subsets complicate the relationship still further. On
the other hand a quadrilateral-free Steiner triple system is the same as a
Steiner triple system all of whose linear 4-subsets are singly-linear. In fact,
"linearity" is a somewhat finer notion. Here is the easily proven relationship
between quadrilaterals and linearity:
Proposition 2.2 The number of quadrilaterals in a Steiner triple system is3 jL 2
and, in particular, the number of doubly-linear 4-subsets of a Steiner triple
system is divisible by 3.
3 We are using "line" rather than "triple" here to conform with common usage. The
four-line configurations of a Steiner triple system have been catalogued and counted by
Grannell, Griggs and Mendelsohn [13] and the number of quadrilaterals determines the
number of all other four-line configurations.
Corollary 2.3 The number of singly-linear 4-subsets of a Steiner triple system
is divisible by 3.
Proof: By Lemma 2.1 we have that
and the result is obvious. 2
A triply-linear 4-subset of a Steiner triple system corresponds precisely to
a configuration isomorphic to a non-Fano plane. Such a configuration is the
six-line configuration on exactly seven points and can be viewed as the usual
Fano plane with a line removed; as a linear space, it plays an important role
in coordinatization problems - see Delandtsheer, [9, Page 197]. Here is
the picture, the triply-linear 4-subset being the complement of the missing
line (the vertices of the large triangle plus the central point):
s
s
s
s
Observe that the triply-linear 4-subset given by the non-Fano plane is the
support of the binary sum of the incidence vectors of the six lines of the
configuration.
In order to easily state some of the results we wish to discuss we attach a
graph 4 to each Steiner triple system. Since no other graphs will appear in the
paper we simply call it the graph of the Steiner triple system. The vertices
of the graph are the linear 4-subsets and two vertices will be connected by
an edge if the two linear 4-subsets intersect in three points. The vertices of
the graph corresponding to the elements of L 3
are clearly isolated vertices
and there are no edges between vertices corresponding to elements of L 2
There will be edges between elements of L 2
and elements of L 1
, however.
4 There are at least two other ways to attach a graph to a Steiner triple system. Perhaps
the most interesting of these other graphs is the "block graph", which is a strongly-
regular graph. For an account of this graph the reader may wish to consult Peeters, [28,
Section 3.1]. The graph we are introducing is quite different and should not be confused
with the others.
In fact, the valency of an element of L 2
is clearly four. Because every Type
III triangle of a Steiner triple system gives rise to a 3-clique of the graph,
implies, by Lemma 2.1, that the graph is at least 3-chromatic; in
particular, the graph of any quadrilateral-free Steiner triple system is at least
3-chromatic. As we shall see, the Hall triple systems do have 3-chromatic
graphs.
Since every triangle is contained in a linear 4-subset and no linear 4-
subset contains a triple of the system, it is at least conceivable that one
might find among the linear 4-subsets the means to extend the triple system
to a quadruple system. In terms of the graph of the system, an extension of
a given Steiner triple system found among the linear 4-subsets, is the same
thing as a stable 5 subset of the vertices of its graph with cardinality precisely24
Because a collection of linear 4-subsets will form an extension provided there
are enough with no two intersecting in three points, the graph of a Steiner
triple system can have a stable subset of vertices of cardinality at most 624
We call a Steiner triple system that posesses such an
extension linearly derived and the collection of 1n(n linear
4-subsets a linear extension. Since L 2 [L 3
is always a stable subset of the
graph of a Steiner triple system, we have the following easy
Proposition 2.4 For a Steiner triple system on n points
In the case of equality L 2 [L 3
is a linear extension and the system is linearly
derived.
Remarks: 1) In fact, equality does occur for some Steiner triple systems. As
we shall see, Corollary 4.2, they are precisely those systems whose graph has
5 A stable subset of a graph is a set of vertices with no two connected by an edge; such
a subset is also sometimes called an independent set of vertices. A stable subset of a graph
is the same as a clique of the complementary graph.
6 In general it is "hard" - in the technical, computer-science sense - to compute
the maximum number of vertices in a stable subset of a graph and hard to compute the
chromatic number also. For an expository discussion of these matters see Knuth [18].
chromatic number one or two. 2) Since the triangles of Type I are in a unique
linear 4-subset - which is, in fact, triply-linear - any linear extension of a
Steiner triple system must contain all triply-linear subsets; that is, L 3
must
be a subset of any linear extension.
Observe that a linear 4-subset is always among the points of the subsystem
generated by any one of its triangles. It follows that a linear extension of
any Steiner triple system automatically yields linear extensions of all of its
subsystems. Since the cyclic Steiner triple system of order 5 (on 13 points)
is, as we shall see, not linearly derived, there will be many triple systems
without linear extensions.
In the next section we investigate the geometric Steiner triple systems
and show not only that they are linearly derived but that their graphs have
the smallest possible chromatic numbers.
3 Linear extensions of geometric systems
The Steiner triple systems we will deal with in this section are either the
systems of points and lines of a projective geometry over the binary field
or Hall triple systems - i.e., Steiner triple systems each of whose triangles
is contained in a subsystem isomorphic to the affine plane of order 3. We
begin with a characterization, in terms of the graph, of the binary geometric
systems. This result, although different, is equivalent to Theorems 3.1 and
3.2 in [33].
Proposition 3.1 If a Steiner triple system has no singly-linear 4-subsets
then it has precisely 1n(n\Gamma1)(n\Gamma3) linear 4-subsets and these 4-subsets form
a linear extension. Moreover, the triple system is the system of points and
lines of a projective geometry over the binary field and its graph is monochromatic

Proof: By Lemma 2.1 jL
is empty so is L 2
. It
follows that all linear subsets are triply-linear and that all triangles are of
Type I. Hence each triangle is contained in a unique linear 4-subset and we
have the necessary linear extension. The extension is simply given by L 3
and
the graph has no edges, i.e., is monochromatic. That the system must be
a geometric binary system follows rather easily. One can simply apply the
Theorem 3.2] or see below - since the number of
quardilaterals is maximal by Proposition 2.2, or use [15, 16].2
Corollary 3.2 The graph of a Steiner triple system is monochromatic if and
only if it is a geometric binary system.
Proof: It follows easily from the discussion presented with the description
of the graph that, if the graph is monochromatic, then jL and we have
the geometric system. On the other hand, in a geometric binary system of
points and lines of a projective geometry every triangle generates a Fano
plane and every linear 4-subset is triply-linear. In particular the graph is
monochromatic.2
The characterization of the binary geometric systems due to Stinson and
Wei [33, Theorems 3.1 and 3.2] is the following:
A Steiner triple system on n points has at
quadrilaterals with equality if and only if it is the geometric system of points
and lines of a projective geometry over the binary field.
From the point of view of [2], such a characterization should have a
"ternary" analogue - and indeed it does. Since the characterization is via
local properties, however, it is not the systems of points and lines of affine
geometries over the ternary field that are characterized but, instead, the Hall
triple systems - that is, systems that are locally like the affine plane of order
3. In the ternary analogue, quadrilaterals are replaced by mitres. 7 A mitre is
the five-line configuration with exactly seven points and two disjoint triples:
s
s
Here is the characterization:
7 The terminology is due to Andries Brouwer.
Theorem 3.3 A Steiner triple system on n points has at most12
mitres with equality if and only if it is a Hall triple system.
Proof: We first describe a pre-mitre - which can be viewed as a mitre
with one of the disjoint triples removed. Here is the picture:
s
s
s
s
Now, the four-line configuration above may or may not complete to a mitre.
The important point is that every mitre gives rise to exactly two such configurations
and that the number of such configurations is easily counted (see
[13] where pre-mitres are simply the four-line configurations of type C 15
There are precisely 1n(n pre-mitres in every Steiner triple system
on n points. This immediately gives the inequality with equality if and only
if every pre-mitre completes to a mitre. Since every triangle embeds in a
pre-mitre - in at least three ways, in fact - starting with a triangle and
using the fact that all pre-mitres complete to a mitre, it is an easy exercise
to show that every triangle is contained in a subsystem isomorphic to an
affine plane of order 3, that is, that the triple system is a Hall triple system.
On the other hand, given a Hall triple system every pre-mitre must be in an
affine plane of order 3 and hence must complete to a mitre, since the three
points that should be collinear must be on one of the two lines parallel to
the base of the pre-mitre.2
The proof above also gives the following
Corollary 3.4 A Steiner triple system in which every pre-mitre completes
to a mitre must be a Hall triple system.
We next want to show that the geometric systems of points and lines of
an affine geometry over the ternary field are linearly derived. We show more:
that Hall triple systems are linearly derived and, in fact, we show that the
graph of a Hall triple system is 3-chromatic, which is an apparently stronger
property.
First note that a Hall triple system cannot contain a quadrilateral since
affine planes of order 3 do not contain quadrilaterals. Thus, in this case we
have that both L 2
and L 3
are empty, with all linear 4-subsets singly-linear
- in contrast to the binary geometric systems where all linear 4-subsets
were triply-linear. That is, Hall triple systems are quadrilateral-free. There
are certainly many, many other quadrilateral-free Steiner triple systems, the
first non-Hall system occuring at order system #80 of the eighty triple
systems on 15 points. Andries Brouwer proved that quadrilateral-free
Steiner triple systems existed for all n j 3 (mod 6); this was independently
shown by Griggs, Murphy and Phelan in [14], where a brief history of the
problem is given. Griggs has constructed systems for many
and, moreover, conjectures that quadrilateral-free Steiner triple systems exist
for all admissible orders except 2 and 5.
Observe that the graph of a quadrilateral-free Steiner triple system is
regular of valency 8, contains 3-cliques, but does not contain a 4-clique. Its
chromatic number is, of course, at least 3. We first show that, if it is 3, then
it is linearly derived.
Proposition 3.5 In a quadrilateral-free Steiner triple system whose graph
has chromatic number 3, the linear 4-subsets split into three disjoint subsets,
each of which yields a linear extension of the triple system.
Proof: It follows from Lemma 2.1 that a quadrilateral-free Steiner triple
system on n points has precisely8 n(n
linear 4-subsets. Since the cardinality of a stable subset of its graph is at
whenever the graph is 3-chromatic the linear 4-subsets must split into three
stable subsets of cardinality each corresponding to one of
the three colors and each yielding a linear extension.2
We next show that the graphs of Hall triple systems have chromatic number
three by splitting their linear 4-subsets into three disjoint linear exten-
sions. We do not have an example of a quadrilateral-free Steiner triple system
whose graph is 3-chromatic that is not a Hall triple system.
Theorem 3.6 The linear 4-subsets of a Hall triple system on n points split
into three disjoint subsets, each of cardinality 1n(n \Gamma 1)(n \Gamma 3), with each
yielding a linear extension. In particular, the graph of a Hall triple system
is 3-chromatic.
Proof: Simple counting shows that there are precisely fifty-four 4-subsets of
an affine plane of order 3 that do not contain a line. All of these must be
linear 4-subsets since an affine plane of order 3 is quadrilateral-free and hence
contains fifty-four linear 4-subsets. It is well-known (see, for example, [22,
Section 7] for a direct proof from first principles or use the small Mathieu
design to get the desired splitting) that these fifty-four 4-subsets split into
three extensions - which are therefore necessarily linear extensions. We now
apply an idea first used in [3]. It can be applied to our present situation either
through [1] or [17] to split the linear 4-subsets of any Hall triple system into
the required three disjoint pieces. Briefly stated, the idea is that the linear
4-subsets all occur in subsystems of affine planes of order 3 and that one can
piece together the extensions of these planes to get linear extensions of the
Hall triple system.2
Thus we have shown that the geometric binary system of points and lines
of a projective geometry over the binary field has a linear extension as does
the geometric ternary system of points and lines of an affine space over the
ternary field. Moreover, we have characterized the binary geometric system
in terms of the graph and shown that, in this context, the Hall systems
are a natural generalization of the system of points and lines of the affine
geometry in the sense that they have linear extensions also and that their
graphs have chromatic number three. We do not have any other examples of
quadrilateral-free Steiner triple system whose graph has chromatic number 3.
We are indebted to Wendy Myrvold for the following computer-generated,
but easily hand-checked, proof that the graph of the unique quadrilateral-free
Steiner triple system of order 6 (on 15 points) has chromatic number greater
than 3.
Example: The unique quadrilateral-free Steiner triple system on 15 points
can be taken to be the cycles of the following three triples:
There are twenty-one cycle classes of (necessarily singly-linear) 4-subsets.
The reader can check, step-by-step, that at least four colors are necessary
by examining the vertices in the following order: f1; 2; 8; 12g, f2; 4; 8; 12g,
Of course, one must first check that the above 4-subsets are linear, but that
too is easily done by hand.
4 Chromatic number two
There are Steiner triple systems whose graphs have chromatic number 2. We
characterize these in the following result. It is a case in which the inequality
of Lemma 2.1 is an equality - thus also an extremal case.
Theorem 4.1 The graph of a Steiner triple system has chromatic number 2
if and only if it has singly-linear 4-subsets and the number of singly-linear 4-
subsets equals the number of doubly-linear 4-subsets. Moreover, in this case,
the graph, when its isolated points are removed, is a regular bipartite graph
of valency 4 and the Steiner triple system has at least two linear extensions,
one consisting of the singly-linear and triply-linear 4-subsets and the other of
the doubly-linear and triply-linear 4-subsets.
implies the existence of 3-cliques in the graph of a
Steiner triple system, for the graph to be 2-chromatic we must have
it is a simple matter to check directly from the definitions that,
putting L 3
aside, the graph on
is bipartite with parts L 1
and L 2
and is regular of valency 4. It follows immediately from Lemma 2.1 that
and since there are no edges among the vertices in L 2
this set forms a
linear extension. Since there are no edges among the vertices in L 1
either,
also yields a linear extension. It is also clear that when jL
is empty and all the above obtains.2
Remark: If the bipartite subgraph of the graph of the Steiner triple system
is disconnected, then there will definitely be more than two linear extensions
since, for each connected component, one can choose either of the parts.
Examples: 1) The Steiner triple systems #2, #3 and #16 in the usual ordering
([23]) of the 80 on 15 points satisfy the conditions of the Theorem and
hence have the announced linear extensions. 8 We are indebted to Vladimir
Tonchev for making the necessary computations for both this example and
the one that follows (which is easily done by hand). In fact, he computed
the data listed in Section 5 giving, for each of the 80 systems, not only the
number of linear 4-subsets of each type but also, by Proposition 2.2, the number
of quadrilaterals. The number of triply-linear 4-subsets is the number
of non-Fano planes contained in the Steiner triple system as six-line configurations
on seven points - as we have already remarked. For the systems
of full 2-rank (#23 9 through #80 except for #61) none of these non-Fano
planes complete to a Fano plane. For the systems #1 through #22 and #61
one can use the 2-rank to compute easily the number of non-Fano planes
that do not complete to a Fano plane - since the number of Fano planes is
is the corank, a Fano plane being a maximal subsystem in
this case. For example, #61 has no such non-Fano planes while #2, which
is of 2-rank 12 and hence has seven Fano planes, has eight non-Fano planes
which do not complete to a Fano plane. The general results presented above
show that four of the eighty Steiner triple systems of order 6 are linearly
derived and explicitly give the linear extensions. But all of them are known
to be derived and the history of the proof of that fact is interesting. As recently
as 1980 the possibility of a computer attack on the eighty systems was
8 These are precisely those systems which are both mitre-free and possess singly-linear
4-subsets, [7, page 215].
9 In [23, Page 42] it is incorrectly reported (see [24], where this error and several misprints
are recorded) that system #23 has a subsystem; in fact, it has none, but it does
have four non-Fano planes. The same reference missed the occurrence - apparently by
a misreading of the beautiful classification done by hand over seventy-five years ago by
White, Cole and Cummings [38] - of non-Fano planes in nine of the systems, each of
which has a single non-Fano plane. This omission was also observed by Grannell and
Griggs, [12, Page 187], who give the nine systems and the single non-Fano plane in each
one.
deemed "not feasible" (see [29, Page 113]) but Grannell and Griggs [12]
rather quickly made progress via computer and then the remaining fourteen
cases were despatched with a computer attack by Diener, Schmitt and de
Vries [10]. See the Introduction to [10] for a slightly more detailed history
and the body of that paper for a short description of the methods used. 2)
The two Steiner triple systems of order 5 (on 13 points) have the following
"linear" structure:
System Singly \Gamma Doubly \Gamma T riply \Gamma Quadrilaterals
linear linear linear
The cyclic system is mitre-free [7, page 221]. Wendy Myrvold generated,
by computer, the following easily hand-checked proof that the chromatic
number of the cyclic system is at least 4. The system can be taken to be the
cycles of
and, by examining the vertices of the graph in the following order, one
sees that at least four colors are needed: f2; 3; 4; 8g, f2; 3; 4; 6g, f3; 4; 6; 8g,
These systems
are known to be derived (see [25]) but not linearly. In fact, Myrvold
ran her clique program on the cyclic system which gave 52 as the cardinality
of the maximal stable subset. It follows from this computer result that no
Steiner triple system containing a subsystem isomorphic to the cyclic system
of order 5 can be linearly derived.
Corollary 4.2 For a Steiner triple system on n points we have that
with equality if and only its graph has chromatic number 1 or 2. Moreover,
in the case of equality both linear extensions.
Remark: It is at least theoretically possible for a Steiner triple system to
have lots of quadrilaterals, but be non-Fano-free - that is, have no non-
Fano planes. It seems unlikely that such systems exist since the non-Fano
planes of a system produce many of its quadrilaterals in known examples.
We do, however, have the following, perhaps empty, result, which, in any
case, does give a sharper upper bound on the number of quadrilaterals in the
non-Fano-free case than that given, in general, by the Stinson-Wei result.
Suppose a Steiner triple system on n points contains no non-Fano planes.
Then the number of quadrilaterals is at most72
with equality if and only if the chromatic number of its graph is 2. Moreover,
in the case of equality, both L 1
and L 2
yield linear extensions.
The proof is simple: Since L 3
is empty and jL
Proposition 2.2 implies the inequality. We have equality if and only if
Proposition 2.2 and Lemma 2.1. The
graph is bipartite, the parts being L 1
and L 2
and either part yields a linear
extension. One can phrase this characterization entirely in terms of quadri-
laterals. Observe first that in any Steiner triple system each quadrilateral has
three 4-subsets of its six points that do not contain a line of the quadrilateral.
These subsets will be either doubly-linear or triply-linear. In the following
result we call these subsets the 4-subsets given by the quadrilateral.
A Steiner triple system without non-Fano planes has a graph with chromatic
number 2 if and only if the collection of those 4-subsets given by the
quadrilaterals of the system forms an extension.
We now suppose given an arbitrary Steiner triple system on n points.
Let F denote the number of Fano planes contained in the system and N the
number of proper non-Fano planes, that is, non-Fano planes which do not
complete to a Fano plane of the system. Then the number of triply-linear
4-subsets is 7F + N . Since every non-Fano plane which does not complete
to a Fano plane gives rise to 6 doubly-linear 4-subsets, we have the following
consequence of Lemma 2.1, Proposition 2.2 and Proposition 2.4:
Theorem 4.3 Suppose given a Steiner triple system on n points containing
F Fano planes and N proper non-Fano planes Then
and the number of quadrilaterals of the system is at least 7F +3N . Moreover,
equality implies that the Steiner triple system has a graph with chromatic
number 1 or 2 and precisely 7F
the geometric system of points and lines of a projective geometry over the
binary field or else N 6= 0, jL
and L 1 [L 3
providing
linear extensions.
Proof: Since jL 1
and hence the inequality. Proposition 2.2 underbounds the number of quadri-
laterals. Equality forces jL and the rest of the Theorem
Remarks: 1) Observe that each of the three systems on 15 points that have
graphs with chromatic number two - #2, #3 and #16 - satisfy the bound
of the Theorem, that is F system #1 does also - as do all the
geometric binary systems. 2) Systems of of order 8 (on 19 points) cannot
furnish further examples of equality since the right-hand-side of the inequality
is not an integer, but, for systems of order 9 (systems on 21 points), the
right-hand-side is an integer presumably further examples
do exist in this case. It would be very interesting to have a suitably easy
construction of Steiner triple systems on n points, where n j 0;
with F
in any Steiner triple system on n points, it is, at least in principle, possible
that its graph might be highly disconnected consisting of the isolated vertices
comprising L 3
, a bipartite subgraph with one part L 2
and the other part jL 2 j
vertices from L 1
, with the other components of the graph, in the case in
which of chromatic number 3. Should that happen, then, as
in the Proposition 3.5 and the result above, we could extract at least six
linear extensions consisting of one-third of the vertices from the 3-chromatic
components, either one of the two parts of the bipartite subgraph and the
isolated vertices. The cyclic system of order 5 shows that this is not always
LINEAR STRUCTURE OF SYSTEMS OF ORDER SIX
possible since, as we have seen, the chromatic number of its graph is at least
4. In fact, for such a highly disconnected graph to arise one must have
singly-linear 4-subsets all of whose 3-subsets are of Type II since each vertex
corresponding to elements of L 2
is of valency four and therefore those vertices
from L 1
making up the other part of the bipartite subgraph must also have
valency four. Moreover, it is impossible to have more than jL 2 j such singly-
linear 4-subsets and, when there is such a set of singly-linear 4-subsets, all
remaining singly-linear 4-subsets must have all their 3-subsets of Type III.
Usually, this makes it easy to check that such a decomposition of the graph
cannot occur. Neither of the two triple systems of order 5 have graphs with
such a decomposition for just this reason. We have no examples of such a
decomposition with jL it is possible that none exist.
5 Linear structure of systems of order six
We record below results of computations made by Vladimir Tonchev and
Robert Weishaar; for further information see [36]. The corank is simply
is the 2-rank of the given system (the rank over the binary
field of the incidence matrix of the system). The number of Fano planes
contained in a system is simply c is the corank. Since the
number of non-Fano planes is the same as the number of triply-linear 4-
subsets, one has that the number of proper non-Fano planes is
where T is the number of triply-linear 4-subsets and c is the corank. The
number of quadrilaterals - which we have recorded - is simply
Proposition 2.2, where D is the number of doubly-linear 4-subsets.
LINEAR STRUCTURE OF SYSTEMS OF ORDER SIX 19
Number
linear linear linear
6 QUASI-LINEARLY DERIVED SYSTEMS? 21
6 Quasi-linearly derived systems?
It is widely believed that every Steiner triple system is derived. Since the
problem can be reduced to those systems of full 2-rank (see [2, Corollary 6.2])
it follows from Corollary 6.3 of [2] that, if all Steiner triple systems are
derived, then a suitable set of quadruples always can be found among the
binary linear span of incidence vectors of the triples.
In this work we have demanded that the quadruples be found among the
binary sums of the incidence vectors of two triples. One could investigate
what further systems can be shown to be derived by looking at the binary
sums of the incidence vectors of either two or four triples (using only those
yielding, of course, vectors of weight four). In fact, one could envisage a
measure of how difficult it is to find a derivation - using six or fewer triples,
eight or fewer triples, etc. We have not tried to do this.
In the case of four triples we do have the study of Grannell, Griggs
and Mendelsohn [13] of four-line configurations to aid us. Of the sixteen
possible four-line configurations only three, C
and C 15
give weight-four
vectors
appears to be the most interesting candidate, being a pre-
mitre. The weight-four vector produced by such a pre-mitre will have all
four of its 3-subsets triangles if and only if it does not complete to a mitre.
Only those, of course, could be used in trying to find what might be called
a quasi-linear extension of the triple system. Since we know, Corollary 3.4,
that whenever each pre-mitre complete to a mitre we have a Hall triple
system - which has a linear extension - in any other case there will be
4-subsets coming from pre-mitres that could be used to find a quasi-linear
extension. We do not have an example of a Steiner triple system that has
no linear extension but does have a quasi-linear extension, but one presumes
that such systems exist.
Although it is believed that all Steiner triple systems are derived, one still
does not have a suitably easy construction of derived triple systems. It might
conceivably be true that for all admissible n ? 13 there is a linearly derived
Steiner triple system and, if one could find an easy construction, one would
have an alternative to Hanani's recursive techniques for providing derived
10 The support of such a weight-four vector might, in fact, be linear. We have already
noted that a triply-linear 4-subset is the support of the binary sum of the incidence vectors
of the six lines of the non-Fano plane to which it corresponds.
7 AN HISTORICAL ASIDE 22
Steiner triple systems for all admissible orders.
7 An historical aside
In [13, Page 52] Grannell, Griggs and Mendelsohn wonder about the
fact that certain results on four-line configurations had been neglected in the
literature of Steiner triple systems. The same question could be asked about
the results we have here described since the ideas seem so natural, flowing
easily from a either a geometric or coding-theoretic view of the subject, and
the results so easily discovered. We would like to suggest a possible explanation
different from that proposed by Grannell, Griggs and Mendlesohn: an
insularity - and unreceptiveness to ideas coming from disparate disciplines
- that seems to be particularly acute among some workers investigating
Steiner triple systems.
Thoralf Skolem complained [31, Page 274] - perhaps because of the
announcement by Hanani at the 1958 International Conference of Mathematicians
- about the inattention paid by workers in the field to his appendices
to Netto's book. Indeed, his ideas on constructing triple systems 11 seem
to have been ignored for over a half century - except by members of the
Belgian school. When Skolem, probably best known for his work during the
20s and 30s on the foundations of set theory, complained in 1958, his ideas
had been in print for well over a quarter of a century in the Second Edition,
published in 1927, of the Lehrbuch der Combinatorik by Eugen Netto,
[26, Note 16]. It was nearly a quarter of a century after his complaint that
Lindner, [21, Page 184], observed that Skolem's ideas led to an "incredibly
simple" proof of the existence of Steiner triple systems on 6n
in 1987 that proof entered the English monograph literature: Steeet and
Street, [34, Chapter 5]. 12
Ever since its very infancy - in the work of Pl-ucker on cubic curves in
see de Vries [37] - Steiner systems have been intimately related to
11 A direct and easy proof of existence of Steiner triple systems of all admissible orders
can be constructed from [27, 30, 31]. See, for example, [34, Chapter 5] for an efficient and
easily understood direct construction.
I am indebted to D. R. Stinson for pointing out these two sources to me. Neither of
them took account of the work of O'Keefe; the Streets became aware of O'Keefe's work
only after the publication of their book.
geometry and its configurational aspects. 13 Yet, in [29, Pages 105-106] -
the same paper that asserted the infeasibility of the use of computers in determining
whether or not the eighty systems of order six were derived - the
contributions made by finite geometry to the study of Steiner triple systems
are summarily dismissed as "of minor consequence" for the question of deriv-
ability. This despite not only the history of the subject but also the fact that
the fundamental work of Teirlinck [35] - and its elaboration by Doyen,
Hubaut and Vandensavel [11] - had already shown the importance the
geometric systems had for Steiner systems of orders other than the geometric
ones.
Insularity may be more prevalent in combinatorial mathematics (see, for
example, the historical essay by Crapo, [8]) but it clearly can also appear
in the most developed fields with even world-class mathematicians being
unreceptive to new ideas (see Lang, [19, 20]).



--R





On the binary codes of Steiner triple systems.
Graph Theory with Applications.


Dimensional linear spaces.
Hans Ludwig de Vries.
Ranks of incidence matrices of Steiner triple systems.
Derived Steiner triple systems of order 15.
A small basis for four- line configurations in Steiner triple systems



On an infinite class of Steiner systems constructed from affine spaces.
The sandwich theorem.
Mordell's review
Mordell's review
A survey of embedding theorems for Steiner systems.
Transitive Erweiterungen endlicher Permutationsgrup- pen
Small Steiner triple systems and their properties.
Small Steiner triple systems and their properties - Errata
On the Steiner systems S(3
Lehrbuch der Combinatorik.
Verification of a conjecture of
Ranks and structure of graphs.
A survey of derived triple systems.
On certain distributions of integers in pairs with given differences.
Some remarks on the triple systems of Steiner.
Combinatorische Aufgabe.
Some results on quadrilaterals in Steiner triple systems.
Combinatorics of Experimental Design.
On projective and affine hyperplanes.
Steiner triple systems of order 15 and their codes.
Hans Ludwig de Vries.
Complete classification of the triad systems on fifteen elements.
--TR

--CTR
J. D. Key , H. F. Mattson, Jr., Edward F. Assmus, Jr. (19311998), Designs, Codes and Cryptography, v.17 n.1-3, p.7-11, Sept. 1999
graphs;chromatic number;derived triple systems;steiner triple systems