Combinatorial Designs - Applications

The existence theorem for Steiner Triple Systems provides conditions for when these fundamental designs can be constructed.

Proof of Necessity:

For an $STS(v)$, we have a $2$-$(v,3,1)$ design. Using the parameter relations: $r = \frac{\lambda(v-1)}{k-1} = \frac{v-1}{2}$

For $r$ to be an integer, $v$ must be odd.

Also: $b = \frac{\lambda v(v-1)}{k(k-1)} = \frac{v(v-1)}{6}$

For $b$ to be an integer, $6$ must divide $v(v-1)$.

Since $v$ is odd, we have $v(v-1) = (\text{odd})(\text{even})$, so 2 divides $v(v-1)$.

For 3 to divide $v(v-1)$: since $v$ and $v-1$ are consecutive integers, at most one is divisible by 3. Thus:

• If $v \equiv 0 \pmod{3}$, then $3 | v$
• If $v \equiv 1 \pmod{3}$, then $v-1 \equiv 0 \pmod{3}$, so $3 | (v-1)$
• If $v \equiv 2 \pmod{3}$, neither $v$ nor $v-1$ is divisible by 3, so $3 \nmid v(v-1)$ ✗

Combined with $v$ odd:

• $v$ odd and $v \equiv 0 \pmod{3}$: $v \equiv 3 \pmod{6}$
• $v$ odd and $v \equiv 1 \pmod{3}$: $v \equiv 1$ or $4 \pmod{6}$, but $v$ odd means $v \equiv 1 \pmod{6}$

Therefore, necessary: $v \equiv 1$ or $3 \pmod{6}$. $\square$

Proof of Sufficiency (Sketch):

For small values ($v = 1, 3, 7, 9, \ldots$), explicit constructions exist.

For general $v \equiv 1$ or $3 \pmod{6}$, the existence was proven through various constructions:

• Direct constructions for small $v$
• Recursive constructions combining smaller designs
• Bose's construction (1939) for $v = 6n + 3$
• Skolem's construction for certain values

The complete proof of sufficiency was achieved through the collective work of many mathematicians over decades, culminating in general existence proofs by the 1970s.