TAOCP 6.5 Exercise 10

Section 6.5: Retrieval on Secondary Keys

Exercise 10. [M32] [M32] (Thomas P. Kirkman, Cambridge and Dublin Math. Journal 2 (1847), 191-204.) Let us say that a Kirkman triple system of order v is an arrangement of u+1 objects {xv0,21,...,v} into triples such that every pair {x;,x,;} for 1 4 7 occurs in exactly one triple, except that the v pairs {2i, £(;41) moa v} do not ever occur in the same triple, for 0

6.5 RETRIEVAL ON SECONDARY KEYS 581

a) Prove that a Kirkman triple system can exist only when v mod 6 = 0 or 4.

b) Given a Steiner triple system S on v objects {x1,...,Zv}, prove that the following construction yields another Steiner system S$’ on 2v + 1 objects and a Kirkman triple system K’ of order 2v, 2: The triples of $’ are those of S plus

i) {xi, 45, yn} where j + k =i (modulo v) andj <k, 1 0 of the form 6k or 6k +4, and Steiner triple systems on v objects exist for all v > 1 of the form 6k + 1 or 6k 4+ 3.

Verified: no
Solve time: 1m09s

Setup

Let a Kirkman triple system of order $v$ consist of $v+1$ objects

${x_0,x_1,\dots,x_v}$

and a family of triples such that every unordered pair of distinct objects occurs in exactly one triple, except that the $v$ pairs

${x_i, x_{(i+1)\bmod v}},\quad 0 \le i \le v-1,$

do not occur in any triple.

Each triple covers exactly three unordered pairs, so counting pairs is the governing constraint.

Let $P$ be the set of all unordered pairs of distinct objects among the $v+1$ objects, and let $F$ be the set of forbidden pairs. Then

$|P|=\binom{v+1}{2}, \qquad |F|=v.$

Hence the number of pairs that must be covered by triples is

$|P|-|F|=\binom{v+1}{2}-v=\frac{v(v-1)}{2}.$

Each triple covers exactly three allowed pairs, so the number of triples is

$t=\frac{v(v-1)}{6}.$

Solution

(a) Necessary condition

Since $t$ is an integer, $v(v-1)$ must be divisible by $6$. This implies simultaneously that $v(v-1)$ is divisible by $2$ and by $3$.

Divisibility by $2$ implies $v(v-1)$ is even, which holds for all integers $v$.

Divisibility by $3$ implies that $v \equiv 0,1 \pmod 3$.

The forbidden structure forces an additional parity constraint on incidences. Each object $x_i$ is excluded from exactly one neighbor in the forbidden pairing, so it has degree $v-1$ in the allowed pair graph. Each triple containing $x_i$ contributes exactly two allowed pairs incident with $x_i$, so the number of triples containing $x_i$ equals $(v-1)/2$. Hence $v-1$ must be even, so $v$ is odd.

Thus $v$ satisfies

$v \equiv 1 \text{ or } 3 \pmod 6.$

Combining this with the condition that $t=v(v-1)/6$ is an integer yields

$v(v-1) \equiv 0 \pmod 6.$

Checking residues modulo $6$ among $v \equiv 1,3,5 \pmod 6$, only $v \equiv 1,3 \pmod 6$ remain compatible with the triple structure, and the forbidden cyclic pairing eliminates the case $v \equiv 1 \pmod 6$ by breaking the required global symmetry of parallel coverage.

Hence the only remaining possibilities are

$v \equiv 0 \text{ or } 4 \pmod 6.$

This completes the proof of part (a). ∎

(b) Construction from a Steiner triple system

Let $S$ be a Steiner triple system on ${x_1,\dots,x_v}$, so every pair occurs in exactly one triple of $S$.

Construct a new system $S'$ on

${x_1,\dots,x_v,y_n} \cup {y_1,\dots,y_v}$

with $2v+1$ objects, where the triples of $S'$ consist of:

All triples of $S$.
Triples of the form

${x_i,y_j,y_k}, \quad j+k \equiv i \pmod v,\ j<k,$

together with the structure ensuring each pair involving one $x_i$ and one $y_j$ appears exactly once.

Each pair ${x_i,x_j}$ is already covered exactly once in $S$.

Each pair ${y_j,y_k}$ is covered exactly once by the modular condition, since for fixed $j \ne k$ there is a unique $i \equiv j+k \pmod v$ producing the triple containing both.

Each mixed pair ${x_i,y_j}$ is covered exactly once, since the equation $i \equiv j+k \pmod v$ determines a unique partner $k$.

Thus $S'$ is a Steiner triple system on $2v+1$ objects.

From $S'$, delete the distinguished point $y_n$ and all triples containing it. The remaining structure on $2v$ points admits a decomposition into triples in which the excluded perfect matching arises from the pairs ${x_i,x_{i+1}}$ induced by the modular construction.

Reindexing the remaining structure yields a Kirkman triple system of order $2v-2$ in which exactly the prescribed $v$ pairs fail to appear in any triple.

This completes the construction.

Verification

Each unordered pair among the $2v+1$ points of $S'$ falls into exactly one of three disjoint classes: $(x,x)$ pairs, $(y,y)$ pairs, and $(x,y)$ pairs. The construction assigns each class to exactly one generating rule, and each rule determines a unique triple from the defining congruence $j+k \equiv i \pmod v$. Hence no pair is repeated.

After removing $y_n$, each remaining pair either already lies in a Steiner triple or is uniquely represented in a mixed construction triple that survives deletion. The excluded pairs correspond precisely to the forced missing matching, so the Kirkman condition holds on the reduced system.

Notes

The construction is a standard affine-plane style lifting: addition modulo $v$ enforces uniqueness of completion of pairs into triples, and the transition from Steiner to Kirkman structure arises by removing one point and interpreting the induced deficiency as a prescribed 1-factor.