Extremal combinatorics · Definition

Steiner triple system

enumerative combinatoricsextremal combinatorics

Steiner triple systems are the simplest case of Steiner block designs, with blocks of size 3. They appear in coding theory, experimental design, and the theory of Latin squares.

Definition

A Steiner triple system \(\mathrm{STS}(v)\) is a block design in which \(v\) points are grouped into triples so that every pair of distinct points lies in exactly one triple.

\[b=\frac{v(v-1)}{6},\quad r=\frac{v-1}{2}\]

If \(\mathrm{STS}(v)\) exists, each point \(x\) lies in exactly \(r=\frac{v-1}{2}\) blocks, since the other \(v-1\) points must pair with \(x\) in blocks of 2 points each. Hence \(v\) must be odd, and the number of blocks \(b=\frac{v(v-1)}{6}\) must be an integer. The condition \(v\equiv 1,3 \pmod 6\) is necessary and, by the Kirkman-Netto theorem, also sufficient.

For \(v=7\) the Fano plane is an \(\mathrm{STS}(7)\) with \(b=7\) blocks and \(r=3\). The blocks \(\{1,2,4\},\{2,3,5\},\{3,4,6\},\{4,5,7\},\{5,6,1\},\{6,7,2\},\{7,1,3\}\) cover each of the 21 pairs exactly once, which can be checked by counting pairs per block: \(7\cdot 3=21=\binom{7}{2}\).

A typical error is assuming any odd \(v\) works, for example \(v=5\): here \(b=\frac{5\cdot 4}{6}\) is not an integer, so no triple system exists. It is also wrong to confuse the condition of pairs covered exactly once with pairs covered at least once, which describes a covering rather than a design.

Think about it

Why does requiring each pair to appear exactly once, rather than at least once, fix the number of blocks?

Because the b blocks then cover the pairs without repetition, so \(3b=\binom{v}{2}\) determines b; with at least once, pairs can repeat and the count only gives an inequality.

Exercises 10

  1. How many pairs of distinct points does a set of \(v\) points contain?
  2. How many pairs does a block of size 3 cover in a Steiner triple system?
  3. If \(v=7\), how many blocks does an \(\mathrm{STS}(7)\) have?
  4. How many blocks contain each point in an \(\mathrm{STS}(9)\)?
  5. Which value of \(v\) is required for a Steiner triple system to exist?
  6. An \(\mathrm{STS}(v)\) has \(b=35\) blocks. What is the value of \(v\)?
  7. In an \(\mathrm{STS}(v)\), how many blocks pass through a fixed point if \(v=13\)?
  8. How many blocks does an \(\mathrm{STS}(13)\) have?
  9. An \(\mathrm{STS}(v)\) has \(r=6\) and \(b=26\). Is \(v=13\) the only possible value, and what about \(v=12\)? Justify using the bounds on \(r\) and \(b\).
  10. Let \(v=19\). How many blocks does an \(\mathrm{STS}(19)\) have, how many blocks pass through each point, and does \(v\equiv 1,3 \pmod 6\) hold?

References

  • Richard P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2012.
  • Herbert S. Wilf, generatingfunctionology, 3rd edition, A K Peters, 2006.