Combinatorial and Automata Applications
Steiner Triple Systems, Squags and Sloops
A Steiner triple system is a combinatorial design. A squag is an algebra. They are the same object, and once the translation is made, the algebraic machinery applies to the design without further argument.
- State the definition of a Steiner triple system and its admissibility condition.
- Write the equational axioms for squags and for sloops.
- Translate between a triple system and its associated algebra in both directions.
- Explain why squags and sloops form varieties and what that buys.
- Identify subalgebras and congruences in combinatorial terms.
- Recognise where numeric enumeration data belongs and where it does not.
01Steiner triple systems
A Steiner triple system on a finite set S is a collection of three-element subsets, called triples or blocks, such that every pair of distinct elements of S lies in exactly one triple. The order of the system is |S|.
A Steiner triple system of order n exists precisely when n ≡ 1 or 3 (mod 6), together with the trivial cases n = 0 and n = 1. Kirkman established this in 1847. The counting argument for necessity is short: each element lies in (n−1)/2 triples, so n must be odd, and the total triple count n(n−1)/6 must be an integer.
The combinatorial description is complete but inert. It tells you what a triple system is; it gives no leverage for constructing new systems from old, for decomposing a system, or for understanding the class of all systems as a single object. Recasting the design as an algebra supplies all three.
02Squags: the quasigroup encoding
Define a binary operation on S by setting x·y to be the third element of the unique triple containing x and y, and x·x = x. The resulting algebra is a Steiner quasigroup, or squag.
- design → algebra:
- for x ≠ y: x·y := the third point of the unique triple {x, y, z}
- for x = y: x·x := x
- verify the three squag identities hold
- algebra → design:
- triples := { {x, y, x·y} : x ≠ y }
- idempotency ensures no degenerate triples arise
- x·(x·y) ≈ y ensures each pair determines exactly one triple
- the two translations are mutually inverse
03Sloops: adding an identity
The alternative encoding adjoins a new element to serve as an identity. Given a triple system on S, take the universe S ∪ {e} and define a product that returns e when the arguments coincide.
The choice between the two encodings is a choice of type, and it changes the subalgebra lattice exactly as the general theory predicts. Squags have no constant, so the empty set is a subuniverse; sloops have a nullary operation, so every subalgebra contains the identity and the smallest subalgebra is {e}.
04What the variety structure delivers
Both axiom sets are purely equational, so squags and sloops each form a variety. By Birkhoff's theorem the classes are closed under H, S and P, and every general theorem about varieties applies immediately.
- Products give new designs from oldThe direct product of two squags is a squag, so a triple system of order mn arises from systems of orders m and n. The combinatorial construction is not obvious; the algebraic one is a triviality.
- Subalgebras are subsystemsA subuniverse of a squag is a subset closed under the operation, which is exactly a subsystem of the triple system — a subset carrying its own triple system on the induced blocks.
- Congruences give quotient designsA congruence on a squag yields a quotient squag, hence a quotient triple system. The combinatorial meaning is a partition of the points that respects blocks.
- Free squags existThe free squag on n generators is a legitimate object, and its structure encodes which triple-system identities are forced rather than accidental.
This is the pattern the source uses throughout Chapter III: take a combinatorial or computational structure, find an equational encoding, and inherit the whole variety machinery at no cost. The prediction in the preface that such 'applied universal algebra' would become prominent has been borne out, most visibly in the algebraic approach to constraint satisfaction.
05Congruence properties
Squags are congruence-permutable but not congruence-distributive, which places them in the modular but not arithmetical region of the classification.
| Property | Squags | Note |
|---|---|---|
| Variety | Yes | Three identities, type (2). |
| Congruence-permutable | Yes | A Mal'cev term exists. |
| Congruence-modular | Yes | Follows from permutability. |
| Congruence-distributive | No | Not arithmetical. |
| Locally finite | Yes | Finitely generated squags are finite. |
| Finitely based | Yes | Three identities suffice. |
Local finiteness matters for the applications: a finitely generated squag is finite, so the free squag on n generators is a finite object and can in principle be computed. That computation is what tells you which triple systems are generated by n points.
06Enumeration data and where it belongs
The number of non-isomorphic Steiner triple systems of a given order is a natural question, and the answers are catalogue data of exactly the kind this collection does not transcribe.
Counts of non-isomorphic triple systems, of Kirkman triple systems and of resolvable designs are the output of large computer searches. They have been extended repeatedly as computing power has grown, and figures printed in a 1981 text reflect what had been enumerated by then. Reproducing such a table here would create a plausible-looking artefact that ages silently.
The durable content is the method: the admissibility condition, the algebraic encoding, the construction of products and quotients, and the congruence properties. For current enumeration figures, consult the Handbook of Combinatorial Designs and the design-theory databases routed from the sourcing policy page. The distinction runs through the whole collection and is set out there.
Frequently asked
Why two encodings rather than one?
Because they answer different questions. The squag encoding keeps the universe equal to the point set, which makes subalgebras correspond directly to subsystems. The sloop encoding adds an identity, which makes the algebra a loop and connects the theory to the wider study of commutative loops of exponent two. Neither is canonical; the choice is a choice of type.
Does every squag come from a Steiner triple system?
Yes for finite squags — the translation is a bijection between Steiner triple systems and squags on the same underlying set. Infinite squags exist too and correspond to infinite triple systems, where the admissibility condition has no analogue.
Is the variety of squags generated by a single finite algebra?
No. Squags of different orders generate different subvarieties, and no single finite squag generates them all. This is why the variety is not locally finite in the strong sense of having a bounded free spectrum, even though each finitely generated member is finite.
- S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
- G. Grätzer, Universal Algebra, 2nd edition, Springer.
- R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.
Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.