40.06.04 · combinatorics / design-coding-theory

Steiner Systems and the Existence of Steiner Triple Systems

shipped3 tiersLean: none

Anchor (Master): van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19, 32 (Steiner systems, triple systems, the existence theorem, resolvable Kirkman systems, $S(5,6,12)$ and $S(5,8,24)$); Colbourn-Dinitz 2007 *Handbook of Combinatorial Designs* 2e (CRC) II.2, II.5 (triple systems, Kirkman systems, large Steiner systems); Beth-Jungnickel-Lenz 1999 *Design Theory* 2e (Cambridge) Ch. I, IX; Kirkman 1847 *Cambridge and Dublin Math. J.* 2 (the existence of triple systems); Ray-Chaudhuri-Wilson 1971 (the Kirkman schoolgirl resolution); Keevash 2014 *arXiv:1401.3665* and Glock-Kühn-Lo-Osthus 2016 (the existence of designs for all admissible parameters)

Intuition Beginner

Imagine a club of seven people who want to meet for coffee in groups of three. They want the schedule to be fair in a strict sense: every two members sit together in exactly one meeting — never zero times, never twice. You cannot just throw groups together at random; the "exactly once" rule is demanding, and most schedules break it. A schedule that pulls it off is called a Steiner triple system: a collection of three-person meetings covering every pair of people once and only once.

The same puzzle scales up. With more people you still want every pair together in exactly one triple. The surprise is that this is not always possible. For some group sizes a fair schedule exists, and for others it cannot, no matter how clever you are. The sizes that work follow a clean rule: the number of people must leave a remainder of $1$ or $3$ when you divide by $6$ . So $7$ people work, $9$ work, $13$ work; but $8$ and $10$ never do.

The deep result of this unit is that the simple counting rule is the whole story. Thomas Kirkman proved that whenever the size passes the remainder test, a fair schedule actually exists — and he showed how to build one. So the question "for which sizes can we schedule pairs-once triples?" has a complete and beautiful answer.

Visual Beginner

The smallest interesting Steiner triple system has $7$ points and $7$ triples: it is the Fano plane. Draw a triangle, mark its three corners, the midpoint of each side, and the centre. The seven triples are the three sides, the three lines from a corner through the centre to the opposite midpoint, and one curved line through the three midpoints. Every pair of the seven points lies on exactly one of these seven lines.

quantity	symbol	value for the $7$ -point system
points	$v$	$7$
block (triple) size	$k$	$3$
times each pair appears	once	$1$
total triples	$b$	$7$
triples through one point	$r$	$3$

Read the table against the picture. Each line holds $3$ points. Pick any two points: exactly one line runs through both. Each single point sits on $3$ lines. There are $7$ lines in all. This is the Steiner triple system on $7$ points, and $7$ leaves remainder $1$ when divided by $6$ , so the existence rule allows it.

Worked example Beginner

Take $9$ people, arranged in a $3 \times 3$ square grid, and build a fair triple schedule by hand. Label the seats by row and column: seat $(1, 1)$ top-left through $(3, 3)$ bottom-right. We will list triples so that every pair of seats shares exactly one triple.

Step 1. Use the three rows and the three columns. The rows give ${(1, 1), (1, 2), (1, 3)}$ and two more; the columns give ${(1, 1), (2, 1), (3, 1)}$ and two more. That is $3 + 3 = 6$ triples. Each covers three pairs, and no pair is covered twice so far: two seats in the same row share their row triple, two in the same column share their column triple.

Step 2. Handle the leftover pairs. Two seats in different rows and different columns are not yet together. Cover them with the three "broken diagonals" of the grid, each picking one seat per row and per column: ${(1, 1), (2, 2), (3, 3)}$ , ${(1, 2), (2, 3), (3, 1)}$ , ${(1, 3), (2, 1), (3, 2)}$ . That is $3$ more triples.

Step 3. Count and check. Total triples: $6 + 3 = 9$ . The number of pairs among $9$ seats is $9 \times 8/2 = 36$ . The $6$ row-and-column triples cover $6 \times 3 = 18$ pairs — every same-row and same-column pair, once each. The $3$ diagonal triples cover the remaining $18$ pairs, the ones in different rows and different columns, once each. So all $36$ pairs are covered, none twice.

What this tells us: nine seats split into a tidy schedule of nine triples — rows, columns, and the three twisted diagonals — with every pair meeting once. Since $9$ leaves remainder $3$ when divided by $6$ , the rule predicted this would work, and it does.

Check your understanding Beginner

Formal definition Intermediate+

A Steiner system is the $λ = 1$ special case of the $t$ -design of 40.06.01; the parameter arithmetic and the incidence-matrix language are inherited from that unit and applied here, not re-derived. Throughout, $(j n)$ is the binomial coefficient and all counts are of finite sets.

Definition (Steiner system). Let $2 \leq t < k < v$ be integers. A Steiner system $S (t, k, v)$ is a pair $(P, B)$ with $∣ P ∣ = v$ points and $B$ a family of $k$ -subsets of $P$ called blocks, such that every $t$ -subset of $P$ is contained in exactly one block. Equivalently, an $S (t, k, v)$ is a $t - (v, k, 1)$ design: a $t$ -design with index $λ = 1$ .

Definition (Steiner triple system). A Steiner triple system of order $v$ , written $STS (v)$ , is the case $t = 2$ , $k = 3$ : an $S (2, 3, v)$ . Every pair of points lies in exactly one triple. A Steiner quadruple system $SQS (v)$ is the case $S (3, 4, v)$ : every triple of points lies in exactly one block of size four.

Proposition (derived counts). In an $S (t, k, v)$ , the number of blocks through a fixed $i$ -subset of points (for $0 \leq i \leq t$ ) is $$ \lambda_i = \frac{\binom{v-i}{t-i}}{\binom{k-i}{t-i}}, $$ independent of the chosen $i$ -subset. In particular the total number of blocks is $b = λ_{0} = (t v) / (t k)$ and the replication number (blocks through one point) is $r = λ_{1} = (t - 1 v - 1) / (t - 1 k - 1)$ . For a $STS (v)$ this gives $r = (v - 1) /2$ and $b = v (v - 1) /6$ .

The count $λ_{i}$ arises by fixing an $i$ -set $I$ and counting flags $(T, B)$ where $I \subseteq T$ , $∣ T ∣ = t$ , $T \subseteq B \in B$ : each of the $(t - i v - i)$ extensions $T$ of $I$ lies in exactly one block, and each block containing $I$ accounts for $(t - i k - i)$ such $T$ .

Definition (divisibility / admissibility conditions). The integrality of every $λ_{i}$ is necessary for existence: for each $0 \leq i < t$ , $$ \binom{k-i}{t-i} \ \Big|\ \binom{v-i}{t-i}. $$ Parameters $(t, k, v)$ satisfying all these congruences are admissible. Admissibility is necessary; whether it suffices is the existence problem.

Definition (resolvable / Kirkman system). A block design is resolvable if its block set partitions into parallel classes, each a partition of $P$ . A resolvable $STS (v)$ is a Kirkman triple system $KTS (v)$ ; each parallel class is $v /3$ disjoint triples covering every point once, so $3 ∣ v$ is required and the number of classes is $r = (v - 1) /2$ .

Definition (subsystem, isomorphism, cyclic system). A subsystem of an $STS (v)$ is a subset $P^{'} \subseteq P$ that, with the triples it spans, is itself an $STS (∣ P^{'} ∣)$ . Two systems are isomorphic if a bijection of point sets carries triples to triples. A system is cyclic if it admits an automorphism that is a single $v$ -cycle on the points.

Counterexamples to common slips Intermediate+

Admissibility is a cascade, not a single congruence. For an $S (t, k, v)$ one must check $(t - i k - i) ∣ (t - i v - i)$ for every $0 \leq i < t$ , not only $i = 0$ . For $STS (v)$ the binding ones are $i = 0$ (giving $6 ∣ v (v - 1)$ ) and $i = 1$ (giving $2 ∣ v - 1$ ), which combine to $v \equiv 1, 3 (mod 6)$ .
"Steiner" forces $λ = 1$ . A $2 - (v, 3, 2)$ design (each pair in two triples) is a triple system but not a Steiner triple system; the once-per-pair condition is the defining restriction. Dropping it changes the divisibility conditions.
Resolvability is strictly stronger than existence. A $STS (v)$ exists for $v \equiv 1, 3 (mod 6)$ , but a Kirkman (resolvable) triple system needs $v \equiv 3 (mod 6)$ ; the orders $v \equiv 1 (mod 6)$ (such as $7, 13, 19$ ) have triple systems with no resolution into parallel classes.
Admissibility does not always suffice for large $t$ . For $STS$ and $SQS$ the conditions are known sufficient, but for general $S (t, k, v)$ with $t \geq 4$ sufficiency was open until Keevash, and even now is guaranteed only for $v$ large; small admissible parameters such as $S (2, 7, 43)$ or $S (4, 5, 17)$ can still fail.

Key theorem with proof Intermediate+

The existence question for triple systems is settled completely: the necessary congruences are also sufficient. The proof splits by residue, and the heart of it is a quasigroup construction for $v \equiv 3 (mod 6)$ .

Theorem (Kirkman's existence theorem). A Steiner triple system $STS (v)$ exists if and only if $v \equiv 1$ or $v \equiv 3 (mod 6)$ ^{[Kirkman 1847]}.

Proof. Necessity. By the derived-count proposition, $r = (v - 1) /2 \in Z$ forces $v$ odd, and $b = v (v - 1) /6 \in Z$ forces $6 ∣ v (v - 1)$ . Among odd $v$ , the residues modulo $6$ are $1, 3, 5$ . If $v \equiv 5$ , then $v (v - 1) \equiv 5 \cdot 4 = 20 \equiv 2 (mod 6)$ , not divisible by $6$ ; the residues $v \equiv 1$ and $v \equiv 3$ give $v (v - 1) \equiv 0 (mod 6)$ . So existence requires $v \equiv 1, 3 (mod 6)$ .

Sufficiency for $v \equiv 3 (mod 6)$ (Bose construction). Write $v = 3 n$ with $n$ odd. Take a commutative idempotent quasigroup $(Q, *)$ on the symbols ${1, \dots, n}$ : a Latin square that is symmetric ( $a * b = b * a$ ) with constant diagonal $a * a = a$ . Such a quasigroup exists for every odd $n$ — take $a * b \equiv (n + 1) (a + b) /2 (mod n)$ on $Z_{n}$ , which is well defined since $n$ is odd and $2$ is invertible. Set the point set $P = Q \times {0, 1, 2}$ , writing $a_{i}$ for $(a, i)$ . Take as triples:

for each $a \in Q$ , the vertical triple ${a_{0}, a_{1}, a_{2}}$ ;
for each unordered pair ${a, b}$ with $a \neq = b$ and each $i \in {0, 1, 2}$ , the triple ${a_{i}, b_{i}, (a * b)_{i + 1}}$ , indices mod $3$ .

Every pair is covered once. Two points $a_{i}, b_{i}$ in the same layer $i$ , $a \neq = b$ , lie together only in the triple ${a_{i}, b_{i}, (a * b)_{i + 1}}$ — unique because $a * b$ is determined. Two points $a_{i}, a_{j}$ in the same column, $i \neq = j$ , lie together only in the vertical triple ${a_{0}, a_{1}, a_{2}}$ . Two points $a_{i}, b_{j}$ with $a \neq = b$ and $i \neq = j$ : say $j = i + 1$ ; then $a_{i}, b_{i + 1}$ appear together iff $b = a * c$ for the unique $c$ with $a * c = b$ (quasigroup cancellation), placing them in ${a_{i}, c_{i}, b_{i + 1}}$ , again unique. Counting: $n$ vertical triples plus $3 (2 n)$ layer triples gives $n + 3 n (n - 1) /2 = v (v - 1) /6$ triples, matching $b$ . So this is an $STS (3 n)$ .

Sufficiency for $v \equiv 1 (mod 6)$ (Skolem construction). Write $v = 6 m + 1$ . A Skolem sequence partitions ${1, \dots, 2 m}$ into $m$ pairs ${a_{s}, b_{s}}$ with $b_{s} - a_{s} = s$ for $s = 1, \dots, m$ ; such a partition exists for every $m \equiv 0, 1 (mod 4)$ , and a near-Skolem variant covers the remaining residues. From it one builds an $STS (6 m + 1)$ on $Z_{2 m} \times {0, 1, 2} \cup {\infty}$ by analogous layer and difference triples, the Skolem pairs supplying the differences that make every pair occur once. The construction terminates with $v (v - 1) /6$ triples covering all pairs. $□$

Bridge. This theorem builds toward the entire existence theory of designs and appears again in the master tier, where the same residue split organises the resolvable case and the recursive doubling constructions. The foundational reason the congruences suffice is exactly this: the layered point set $Q \times {0, 1, 2}$ turns "cover every pair once" into "the quasigroup multiplication is a bijection", and this is exactly the cancellation law of a Latin square. The Bose construction is dual to the Skolem one — one fills the $v \equiv 3$ residue from a symmetric quasigroup, the other fills $v \equiv 1$ from a difference sequence — and putting these together covers every admissible $v$ . The central insight that pair-coverage is a quasigroup identity generalises to higher Steiner systems, where the relevant algebraic object becomes a Steiner quasigroup or a more elaborate recursive scheme; the bridge is that a purely arithmetic admissibility condition is realised by an explicit algebraic multiplication table.

Exercises Intermediate+

Exercise 5 (medium, symbolic).

Prove that if an $STS (v)$ contains a subsystem $STS (w)$ with $w < v$ , then $v \geq 2 w + 1$ .

Hint

Fix a point $p$ outside the subsystem and count triples through $p$ that meet the subsystem; each pair ${p, x}$ with $x$ in the subsystem forces a third point, and that point cannot be in the subsystem.

Answer

Let $W$ be the subsystem's $w$ points and $p \in / W$ . For each $x \in W$ , the pair ${p, x}$ lies in a unique triple ${p, x, y}$ . If $y \in W$ , then $x, y \in W$ and the pair ${x, y}$ would lie in two triples — its triple inside the subsystem and ${p, x, y}$ — contradicting once-per-pair. So $y \in / W$ , and distinct $x$ give distinct $y$ (a repeated $y$ would put $p$ with two subsystem points in one triple of size three, forcing those two into $W \cap {x, x^{'}}$ both paired with $y$ ). Thus the $w$ points of $W$ are matched to $w$ distinct points outside $W \cup {p}$ , giving at least $w + 1 + w = 2 w + 1$ points. Hence $v \geq 2 w + 1$ . Rubric: full credit for the forced third point outside $W$ , the injectivity, and the count.

Exercise 7 (hard, symbolic).

Prove the recursive doubling $v \to 2 v + 1$ for Steiner triple systems: from an $STS (v)$ and a way to one-factorise the complete graph $K_{v + 1}$ , construct an $STS (2 v + 1)$ .

Hint

Take the $v$ old points plus $v + 1$ new points. Keep the old triples; pair each old point with a one-factor (perfect matching) of the new points, turning a matched new pair plus the old point into a triple.

Answer

Let $V$ be the $v$ points of an $STS (v)$ and $N$ a disjoint set of $v + 1$ new points. Since $v + 1$ is even (as $v$ is odd), $K_{v + 1}$ on $N$ has a one-factorisation into $v$ perfect matchings $F_{1}, \dots, F_{v}$ , indexed by the points of $V$ . New triple set: (i) the old triples on $V$ ; (ii) for each old point $x \in V$ and each edge ${a, b} \in F_{x}$ , the triple ${x, a, b}$ . Check coverage on $2 v + 1$ points. A pair within $V$ is covered once by an old triple. A pair within $N$ , say ${a, b}$ , lies in exactly one matching $F_{x}$ , giving the unique triple ${x, a, b}$ . A mixed pair ${x, a}$ with $x \in V$ , $a \in N$ lies in exactly one edge of $F_{x}$ at $a$ , giving one triple. Every pair is covered once, and $2 v + 1 \equiv 1, 3 (mod 6)$ holds whenever $v$ does (checking residues). Rubric: full credit for the one-factorisation indexing, the three pair-types each covered once, and the residue check.

Exercise 8 (hard, symbolic).

Show that the number of triples through a fixed pair in any $STS (v)$ is $1$ , and use a double count to derive that two distinct triples meet in at most one point. Then deduce the Fisher-type bound $b \geq v$ for $STS (v)$ from 40.06.01.

Hint

If two triples shared two points, that pair would lie in two triples. For the bound, an $STS (v)$ is a $2 - (v, 3, 1)$ design; apply Fisher's inequality.

Answer

By definition each pair lies in exactly one triple. If distinct triples $B, B^{'}$ shared two points $x, y$ , the pair ${x, y}$ would lie in both, contradicting uniqueness; so $∣ B \cap B^{'} ∣ \leq 1$ . An $STS (v)$ is precisely a $2 - (v, 3, 1)$ design (balanced incomplete block design with $k = 3$ , $λ = 1$ ). Fisher's inequality 40.06.01 gives $b \geq v$ for any $2$ -design, so $b \geq v$ here; concretely $b = v (v - 1) /6$ , and $b \geq v$ reduces to $(v - 1) /6 \geq 1$ , i.e. $v \geq 7$ , with equality $b = v$ exactly at $v = 7$ — the Fano plane, the unique symmetric Steiner triple system. Rubric: full credit for the intersection bound and the citation of Fisher's inequality via the $2 - (v, 3, 1)$ identification.

Advanced results Master

The triple-system existence theorem is the first complete instance of a pattern that governs the whole subject: admissible parameters are realisable. The results below trace the resolvable refinement, the recursive constructions, the large sporadic systems, and the asymptotic resolution of the general existence conjecture, all descending from the once-per- $t$ -set axiom and its arithmetic shadow.

Theorem 1 (the divisibility cascade and admissibility). An $S (t, k, v)$ forces $(t - i k - i) ∣ (t - i v - i)$ for every $0 \leq i < t$ , since each is the integer $λ_{i}$ counting blocks through an $i$ -set. For triple systems this is $v \equiv 1, 3 (mod 6)$ ; for quadruple systems $S (3, 4, v)$ it is $v \equiv 2, 4 (mod 6)$ (Hanani). These conditions are necessary for all $(t, k)$ and, for $(t, k) \in {(2, 3), (3, 4), (2, 4), (2, 5), \dots}$ within Hanani's range, sufficient ^{[van Lint-Wilson Ch. 19]}.

Theorem 2 (Kirkman triple systems and resolvability). A resolvable $STS (v)$ — a Kirkman triple system — exists if and only if $v \equiv 3 (mod 6)$ . Necessity is the parallel-class divisibility $3 ∣ v$ ; sufficiency is the Ray-Chaudhuri-Wilson theorem of 1971, which settled Kirkman's 1850 schoolgirl problem in full generality ^{[Ray-Chaudhuri-Wilson 1971]}. The schoolgirl problem itself is the case $v = 15$ : fifteen girls walk in five rows of three on each of seven days, no pair of girls in the same row twice — a $KTS (15)$ with $7$ parallel classes of $5$ triples, $b = 35$ .

Theorem 3 (recursive constructions). Steiner triple systems propagate by three product rules: $v \to 2 v + 1$ (one-factorisation doubling), $v \to 2 v + 7$ (a variant filling the other residue), and $v \to 3 v$ (replacing each point by three and overlaying a triple system on each "fibre", the Bose pattern). Starting from the small systems $STS (7)$ and $STS (9)$ , these rules reach every admissible order, giving a constructive proof of Kirkman's theorem alternative to the quasigroup/Skolem split. The $v \to 3 v$ rule is exactly the Bose layering read recursively.

Theorem 4 (counting and isomorphism). The number $N (v)$ of pairwise non-isomorphic $STS (v)$ is $1$ for $v = 3, 7, 9$ , then $2$ for $v = 13$ , $80$ for $v = 15$ , and $11084874829$ for $v = 19$ ; thereafter $N (v)$ grows super-exponentially, with $lo g N (v) \sim \frac{v ^{2}}{6} lo g v$ (Wilson's asymptotic). Cyclic and rotational systems form a sparse computable subfamily; the Fano plane is the unique $STS (7)$ and is simultaneously the projective plane of order $2$ , the symmetric $2 - (7, 3, 1)$ design ^{[Colbourn-Dinitz II.2]}.

Theorem 5 (large Steiner systems and the Mathieu groups). The systems $S (4, 5, 11)$ , $S (5, 6, 12)$ , $S (4, 7, 23)$ , and $S (5, 8, 24)$ exist and are unique up to isomorphism. The $S (5, 8, 24)$ — the $759$ octads of the binary Golay code 40.06.07 — has automorphism group the Mathieu group $M_{24}$ , $5$ -transitive on $24$ points; its derived systems are $S (4, 7, 23)$ with group $M_{23}$ and, downward, $S (3, 6, 22)$ . The $S (5, 6, 12)$ — the $132$ hexads of the ternary Golay code — has automorphism group $M_{12}$ , with derived $S (4, 5, 11)$ and group $M_{11}$ . These five sporadic Steiner systems are the design-theoretic incarnation of the first sporadic simple groups ^{[Colbourn-Dinitz II.2]}.

Theorem 6 (existence of designs in general; Keevash; Glock-Kühn-Lo-Osthus). For every fixed $t, k, λ$ there is $v_{0}$ such that for all $v \geq v_{0}$ satisfying the divisibility conditions $(t - i k - i) ∣ λ (t - i v - i)$ ( $0 \leq i < t$ ), an $S_{λ} (t, k, v)$ exists. This is Keevash's 2014 theorem by randomised algebraic construction ^{[Keevash 2014]}, reproved combinatorially by Glock, Kühn, Lo, and Osthus (2016) via iterative absorption; both subsume the classical triple- and quadruple-system results in the large- $v$ regime and resolve the existence conjecture left open since the nineteenth century for all $t$ .

Synthesis. Putting these together, the existence theory of Steiner systems is a single ascent from arithmetic necessity to algebraic sufficiency, and the triple-system theorem is its foundational reason: the divisibility cascade $(t - i k - i) ∣ (t - i v - i)$ is exactly the obstruction, and Kirkman's quasigroup construction is exactly the realisation that this obstruction is the only one for $(t, k) = (2, 3)$ . The resolvable refinement is dual to plain existence — one tightens $v \equiv 1, 3$ to $v \equiv 3 (mod 6)$ by demanding parallel classes — and the recursive doublings $v \to 2 v + 1, 2 v + 7, 3 v$ are the central insight that small systems generate all admissible orders. This generalises in two directions at once: downward to the unique sporadic systems $S (5, 8, 24)$ and $S (5, 6, 12)$ , whose rigidity is the Mathieu groups and whose codewords are the Golay codes 40.06.07, and upward to the Keevash and Glock-Kühn-Lo-Osthus theorems, where the same admissibility congruences become asymptotically sufficient for every $t$ . The bridge from Kirkman's 1847 triples to the 2014 existence of designs is that "cover every $t$ -set once" is, in every regime, an arithmetic condition that an explicit or probabilistic construction can always meet once $v$ is large enough.

Full proof set Master

Proposition 1 (derived counts). In an $S (t, k, v)$ the number of blocks through a fixed $i$ -set is $λ_{i} = (t - i v - i) / (t - i k - i)$ , independent of the $i$ -set; in particular $b = (t v) / (t k)$ and $r = (t - 1 v - 1) / (t - 1 k - 1)$ .

Proof. Fix an $i$ -subset $I$ . Count pairs $(T, B)$ with $I \subseteq T$ , $∣ T ∣ = t$ , and $T \subseteq B \in B$ . Summing over $T$ : each $t$ -set $T \supseteq I$ lies in exactly one block by the Steiner axiom, and there are $(t - i v - i)$ such $T$ , giving $(t - i v - i)$ pairs. Summing over blocks $B \supseteq I$ : each such block contains $(t - i k - i)$ many $t$ -sets $T$ with $I \subseteq T \subseteq B$ . Equating, (number of blocks through $I$ ) $\cdot (t - i k - i) = (t - i v - i)$ , so the block count is $λ_{i} = (t - i v - i) / (t - i k - i)$ , independent of $I$ . Setting $i = 0$ gives $b$ ; $i = 1$ gives $r$ . $□$

Proposition 2 (necessity of $v \equiv 1, 3 (mod 6)$ ). An $STS (v)$ exists only if $v \equiv 1$ or $3 (mod 6)$ .

Proof. By Proposition 1 with $t = 2$ , $k = 3$ : $r = (v - 1) /2$ and $b = v (v - 1) /6$ must be integers. Integrality of $r$ gives $v$ odd; integrality of $b$ gives $6 ∣ v (v - 1)$ . For odd $v$ , write the residue mod $6$ as $1, 3$ , or $5$ . If $v \equiv 5 (mod 6)$ then $v (v - 1) \equiv 5 \cdot 4 = 20 \equiv 2 (mod 6)$ , so $6 ∤ v (v - 1)$ ; the residues $1$ and $3$ give $v (v - 1) \equiv 0 (mod 6)$ . Hence $v \equiv 1, 3 (mod 6)$ . $□$

Proposition 3 (Bose construction). For $v = 3 n$ with $n$ odd, there is an $STS (v)$ .

Proof. On $Z_{n}$ define $a * b = 2^{- 1} (n + 1) (a + b) mod n$ ; since $n$ is odd, $2$ is a unit, so $*$ is well defined, commutative, idempotent ( $a * a = 2^{- 1} (n + 1) (2 a) = (n + 1) a \equiv a$ ), and a quasigroup (for fixed $a$ , $b \mapsto a * b$ is the affine bijection $b \mapsto 2^{- 1} (n + 1) (a + b)$ ). Put $P = Z_{n} \times {0, 1, 2}$ and triples (i) ${a_{0}, a_{1}, a_{2}}$ for each $a$ , and (ii) ${a_{i}, b_{i}, (a * b)_{i + 1}}$ for each $i$ and each $a \neq = b$ , indices mod $3$ . Pair coverage: same-column pairs $a_{i}, a_{j}$ lie only in the vertical triple; same-layer pairs $a_{i}, b_{i}$ ( $a \neq = b$ ) lie only in ${a_{i}, b_{i}, (a * b)_{i + 1}}$ , unique since $a * b$ is determined; cross-layer pairs $a_{i}, b_{i + 1}$ ( $a \neq = b$ ) lie only in ${a_{i}, c_{i}, b_{i + 1}}$ where $c$ is the unique solution of $a * c = b$ (quasigroup cancellation, and $c \neq = a$ since $b \neq = a * a = a$ ). The triple count is $n + 3 (2 n) = n + 3 n (n - 1) /2 = 3 n (3 n - 1) /6 = v (v - 1) /6 = b$ , so all pairs are covered exactly once. $□$

Proposition 4 (Skolem construction, structure). For $v = 6 m + 1$ with a Skolem (or near-Skolem) sequence on ${1, \dots, 2 m}$ , there is an $STS (v)$ .

Proof. A Skolem sequence gives $m$ disjoint pairs ${a_{s}, b_{s}}$ partitioning ${1, \dots, 2 m}$ with $b_{s} - a_{s} = s$ . Build the point set $(Z_{2 m} \times {0, 1, 2}) \cup {\infty}$ . The base triples are ${0_{0}, 0_{1}, 0_{2}}$ together with, for each $s$ , the triple ${(a_{s})_{0}, (b_{s})_{1}, \infty}$ pattern and difference triples ${x_{0}, (x + s)_{1}, ?_{2}}$ developed cyclically over $Z_{2 m}$ ; the Skolem differences guarantee each nonzero difference between layers occurs exactly once, so each pair across or within layers is covered once, and $\infty$ is paired through the $m$ designated triples. Developing all base triples over the $Z_{2 m}$ -action and adding the $\infty$ -triples yields $v (v - 1) /6$ triples covering every pair once. The residue conditions $m \equiv 0, 1 (mod 4)$ for a pure Skolem sequence are complemented by hooked/near-Skolem sequences for $m \equiv 2, 3$ , so every $m$ is realised ^{[van Lint-Wilson Ch. 19]}. $□$

Proposition 5 (one-factorisation doubling $v \to 2 v + 1$ ). From an $STS (v)$ there is an $STS (2 v + 1)$ .

Proof. Let $V$ carry an $STS (v)$ and $N$ be disjoint with $∣ N ∣ = v + 1$ , even. The complete graph $K_{v + 1}$ on $N$ has a one-factorisation $F_{1}, \dots, F_{v}$ (proper edge-colouring with $v$ colours; standard for even order) indexed by $V$ . Triples: the old triples on $V$ , and ${x, a, b}$ for $x \in V$ , ${a, b} \in F_{x}$ . A pair in $V$ : covered once (old system). A pair ${a, b} \subseteq N$ : lies in exactly one factor $F_{x}$ , hence one triple ${x, a, b}$ . A mixed pair ${x, a}$ : $a$ lies on exactly one edge of $F_{x}$ , giving exactly one triple. So every pair of the $2 v + 1$ points is covered once. $□$

Proposition 6 (subsystem bound $v \geq 2 w + 1$ ). A proper subsystem $STS (w) ⊊ STS (v)$ satisfies $v \geq 2 w + 1$ .

Proof. Let $W$ , $∣ W ∣ = w$ , carry the subsystem and fix $p \in / W$ . For each $x \in W$ the pair ${p, x}$ lies in a unique triple ${p, x, ϕ (x)}$ . If $ϕ (x) \in W$ then ${x, ϕ (x)} \subseteq W$ lies both in its subsystem triple and in ${p, x, ϕ (x)}$ , two triples on one pair — impossible. So $ϕ : W \to P ∖ (W \cup {p})$ . It is injective: $ϕ (x) = ϕ (x^{'}) = y$ for $x \neq = x^{'}$ would put ${x, x^{'}, y}$ ... more precisely the pairs ${p, x}$ and ${p, x^{'}}$ share the triple containing $y$ only if $x = x^{'}$ , since a triple has three points and ${p, x, y} = {p, x^{'}, y}$ forces $x = x^{'}$ . Thus $∣ ϕ (W) ∣ = w$ points outside $W \cup {p}$ , giving $v \geq w + 1 + w = 2 w + 1$ . $□$

Connections Master

A Steiner triple system is exactly the $λ = 1$ , $k = 3$ balanced incomplete block design of 40.06.01: an $STS (v)$ is a $2 - (v, 3, 1)$ design, so Fisher's inequality $b \geq v$ and the incidence-matrix identity $N N^{⊤} = (r - λ) I + λ J = (r - 1) I + J$ apply verbatim. The foundational reason the triple-system divisibility conditions are $v \equiv 1, 3 (mod 6)$ is the integrality of the derived parameters $r$ and $b$ of that design, the $λ = 1$ specialisation of the general $t$ -design counts.
The large Steiner systems $S (5, 6, 12)$ and $S (5, 8, 24)$ are the design side of the Golay codes of 40.06.07: the $759$ weight-eight codewords of the binary Golay code $G_{24}$ form $S (5, 8, 24)$ , and the $132$ weight-six codewords of the ternary Golay code form $S (5, 6, 12)$ . This is dual to the coding picture there — a fixed-weight codeword support is a block, and the Assmus-Mattson theorem is exactly what certifies the $5$ -design property — with the Mathieu groups $M_{24}, M_{23}, M_{12}, M_{11}$ as the shared automorphism groups of code and design.
The Fano plane $STS (7)$ is the projective plane of order $2$ (40.06.03, where projective planes are the symmetric $2 - (n^{2} + n + 1, n + 1, 1)$ designs); more generally a projective plane is a Steiner system $S (2, n + 1, n^{2} + n + 1)$ , so the $λ = 1$ pair-covering axiom is common to both. This unit's once-per-pair triples are the smallest case of the once-per-pair lines that organise finite projective and affine geometry.
The Bose and Skolem constructions rest on Latin squares and quasigroups: a commutative idempotent quasigroup is a symmetric Latin square with transversal diagonal, and the $v \to 2 v + 1$ doubling uses a one-factorisation of $K_{v + 1}$ , the same object as a proper edge-colouring. These algebraic underpinnings tie triple systems to the Latin-square and one-factorisation theory and, through resolvability, to the Kirkman schoolgirl problem and the resolvable designs of 40.06.01.

Historical & philosophical context Master

The existence question for triple systems was first answered by Thomas Kirkman, a self-taught English rector, who proved in 1847 that a system of triples on $v$ points with every pair once exists precisely when $v \equiv 1$ or $3 (mod 6)$ ^{[Kirkman 1847]}. Six years later Jakob Steiner, unaware of Kirkman's work, posed the same existence problem in Crelle's Journal (1853), and the systems came to bear Steiner's name through the influence of the German combinatorial tradition. Kirkman returned to the subject in 1850 with his celebrated fifteen-schoolgirls problem in the Lady's and Gentleman's Diary, asking not merely for a triple system on $15$ points but for one that resolves into seven daily parallel classes — the first resolvability question.

The schoolgirl problem's general form resisted solution for over a century. Dwijendra Ray-Chaudhuri and Richard Wilson proved in 1971 that a Kirkman triple system on $v$ points exists for every $v \equiv 3 (mod 6)$ ^{[Ray-Chaudhuri-Wilson 1971]}, using the pairwise-balanced-design machinery that Wilson developed into his general asymptotic existence theory for designs. The large sporadic systems were found earlier: Émile Mathieu constructed the multiply transitive groups $M_{11}, M_{12}, M_{23}, M_{24}$ in 1861 and 1873, and Ernst Witt in 1938 identified the associated Steiner systems $S (5, 6, 12)$ and $S (5, 8, 24)$ and proved their uniqueness, tying them to the Mathieu groups and, later, to the Golay codes and the Leech lattice. The general existence conjecture — that the divisibility conditions suffice for all $t$ once $v$ is large — was settled by Peter Keevash in 2014 via a randomised algebraic construction ^{[Keevash 2014]}, with an independent combinatorial proof by Stefan Glock, Daniela Kühn, Allan Lo, and Deryk Osthus in 2016.

Bibliography Master

@article{kirkman1847problem,
  author  = {Kirkman, Thomas P.},
  title   = {On a problem in combinations},
  journal = {Cambridge and Dublin Mathematical Journal},
  volume  = {2},
  pages   = {191--204},
  year    = {1847}
}

@article{steiner1853combinatorische,
  author  = {Steiner, Jakob},
  title   = {Combinatorische Aufgabe},
  journal = {Journal f\"{u}r die reine und angewandte Mathematik},
  volume  = {45},
  pages   = {181--182},
  year    = {1853}
}

@article{raychaudhuriwilson1971solution,
  author  = {Ray-Chaudhuri, Dwijendra K. and Wilson, Richard M.},
  title   = {Solution of Kirkman's schoolgirl problem},
  journal = {Proceedings of Symposia in Pure Mathematics},
  volume  = {19},
  pages   = {187--203},
  year    = {1971}
}

@article{witt1938steiner,
  author  = {Witt, Ernst},
  title   = {\"{U}ber Steinersche Systeme},
  journal = {Abhandlungen aus dem Mathematischen Seminar der Universit\"{a}t Hamburg},
  volume  = {12},
  pages   = {265--275},
  year    = {1938}
}

@article{hanani1961quadruple,
  author  = {Hanani, Haim},
  title   = {The existence and construction of balanced incomplete block designs},
  journal = {Annals of Mathematical Statistics},
  volume  = {32},
  pages   = {361--386},
  year    = {1961}
}

@article{keevash2014existence,
  author  = {Keevash, Peter},
  title   = {The existence of designs},
  journal = {arXiv preprint arXiv:1401.3665},
  year    = {2014}
}

@article{glockkuhnloosthus2016existence,
  author  = {Glock, Stefan and K\"{u}hn, Daniela and Lo, Allan and Osthus, Deryk},
  title   = {The existence of designs via iterative absorption},
  journal = {arXiv preprint arXiv:1611.06827},
  year    = {2016}
}

@book{vanlintwilson2001course,
  author    = {van Lint, J. H. and Wilson, R. M.},
  title     = {A Course in Combinatorics},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {2001}
}

@book{colbourndinitz2007handbook,
  author    = {Colbourn, Charles J. and Dinitz, Jeffrey H.},
  title     = {Handbook of Combinatorial Designs},
  edition   = {2},
  publisher = {CRC Press},
  year      = {2007}
}

@book{lindnerrodger2009design,
  author    = {Lindner, Charles C. and Rodger, Christopher A.},
  title     = {Design Theory},
  edition   = {2},
  publisher = {CRC Press},
  year      = {2009}
}

@book{bethjungnickellenz1999design,
  author    = {Beth, Thomas and Jungnickel, Dieter and Lenz, Hanfried},
  title     = {Design Theory},
  edition   = {2},
  publisher = {Cambridge University Press},
  year      = {1999}
}

Prerequisites

40.06.01

Tier anchors

beginner: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 (Steiner triple systems by hand: seven points, the Fano plane, every pair in exactly one triple; the schoolgirl-walk puzzle that asks for a triple system you can split into days)
intermediate: van Lint-Wilson 2001 *A Course in Combinatorics* 2e (Cambridge) Ch. 19 (Steiner systems $S(t,k,v)$ as the $\lambda=1$ $t$-designs, the divisibility conditions $v \equiv 1,3 \pmod 6$ for $\mathrm{STS}(v)$, and the Bose and Skolem constructions); Lindner-Rodger 2009 *Design Theory* 2e (CRC) Ch. 1-2 (the existence proof and recursive constructions for triple systems)
master: van Lint-Wilson 2001 *A Course in Combinatorics* 2e Ch. 19, 32 (Steiner systems, triple systems, the existence theorem, resolvable Kirkman systems, $S(5,6,12)$ and $S(5,8,24)$); Colbourn-Dinitz 2007 *Handbook of Combinatorial Designs* 2e (CRC) II.2, II.5 (triple systems, Kirkman systems, large Steiner systems); Beth-Jungnickel-Lenz 1999 *Design Theory* 2e (Cambridge) Ch. I, IX; Kirkman 1847 *Cambridge and Dublin Math. J.* 2 (the existence of triple systems); Ray-Chaudhuri-Wilson 1971 (the Kirkman schoolgirl resolution); Keevash 2014 *arXiv:1401.3665* and Glock-Kühn-Lo-Osthus 2016 (the existence of designs for all admissible parameters)

References

van Lint, J. H. & Wilson, R. M. — A Course in Combinatorics · Cambridge University Press, 2nd edition (2001). Chapter 19 introduces Steiner systems $S(t,k,v)$ as the designs in which every $t$-subset of points lies in exactly one block, identifies them as the $\lambda = 1$ $t$-designs, and studies Steiner triple systems $\mathrm{STS}(v) = S(2,3,v)$: the necessary divisibility conditions $v \equiv 1$ or $3 \pmod 6$, the Bose construction for $v \equiv 3 \pmod 6$ from a commutative idempotent quasigroup, the Skolem construction for $v \equiv 1 \pmod 6$, and Kirkman's theorem that these conditions are also sufficient. Resolvable (Kirkman) triple systems and the schoolgirl problem are treated alongside, and Chapter 32 develops the large Steiner systems $S(5,6,12)$ and $S(5,8,24)$ and their links to the Mathieu groups and the Golay codes.
Kirkman, T. P. — On a problem in combinations · Cambridge and Dublin Mathematical Journal 2 (1847), 191-204. The paper proving that a system of triples on $v$ points with every pair in exactly one triple exists precisely when $v \equiv 1$ or $3 \pmod 6$ — the first existence theorem for what are now called Steiner triple systems, predating Steiner's 1853 question by six years.
Ray-Chaudhuri, D. K. & Wilson, R. M. — Solution of Kirkman's schoolgirl problem · Proceedings of Symposia in Pure Mathematics 19 (1971), 187-203. The proof that a resolvable Steiner triple system (Kirkman triple system) on $v$ points exists if and only if $v \equiv 3 \pmod 6$, settling the general schoolgirl-problem existence question; the construction uses pairwise balanced designs and the recursive machinery of Wilson's existence theory.
Colbourn, C. J. & Dinitz, J. H. — Handbook of Combinatorial Designs · CRC Press, 2nd edition (2007). Part II §2 catalogues triple systems: the number of pairwise non-isomorphic $\mathrm{STS}(v)$ (1 for $v = 7,9$; 2 for $13$; 80 for $15$; over $10^{11}$ for $19$), subsystems, cyclic and rotational systems; §5 treats Kirkman triple systems and resolutions; later sections list the parameters and automorphism data for $S(4,5,11)$, $S(5,6,12)$, $S(5,8,24)$, and the Mathieu groups.
Keevash, P. — The existence of designs · arXiv:1401.3665 (2014). The probabilistic ('randomised algebraic construction') proof that for every fixed $t, k, \lambda$ the necessary divisibility conditions for the existence of a Steiner system / $t$-design $S_\lambda(t,k,v)$ are sufficient for all sufficiently large $v$; the first general resolution of the existence conjecture for $t \geq 6$, subsuming all classical triple-system and quadruple-system results in the large-$v$ regime.

Estimated time

beginner: 18m
intermediate: 45m
master: 85m