Steiner Systems

A Steiner system \(S(t,k,v)\) is a collection of k-sized subsets (“blocks”) of the numbers 1 to \(v\). These collections are special because every t-sized subset of the numbers 1 to \(v\) are in exactly one block.

For example, here is a \(S(2,3,7)\) system (also known as the Fano plane):

{1,2,3}
{1,4,5}
{1,6,7}
{2,4,6}
{2,5,7}
{3,4,7}
{3,5,6}

I was introduced to Steiner systems from this review article. There is also good information on Dan Gordon’s page.

Some cool facts about Steiner systems:

• If you have a Steiner system \(S(t,k,v)\), you can make a Steiner system \(S(t-1, k-1, v-1)\) by choosing all blocks with a certain number, and deleting that number.
• Steiner systems follow divisibility rules: \(S(t,k,v)\) only can exist if \({k-i \choose t-i}\) divides \({v-i \choose t-i}\) for all \(i \in \{0,\cdots,t-1\}\).

Table of \(S(t, t+1, v)\)

Here are the divisibility rules for small \(t\) when \(k = t+1\):

I’ve listed a table below of small values of \(t\) and \(v\).

• Some values of \((t, t+1, v)\) have no associated Steiner system:
  • “☠️”, “❌”, “❎”, “✖”: No Steiner system can exist because of divisibility rules.
  • ”-“: These values do not form a valid Steiner system; \(t\) must be smaller than \(v\).
  • “DNE”: There are no Steiner systems S(4, 5, 15) or S(4, 5, 17), as computationally verified here.
• Some values do have a Steiner system:
  • “Trivial”: There is always a Steiner system \(S(t,k,k)\) with one block including all numbers from 1 to k.
  • “Pairs”: If \(v\) is even, then pairing all numbers from 1 to v forms a Steiner system \(S(1, 2, v)\).
  • “✔️”: There are Steiner systems at each \(v\) that satisfies the divisibility rules, as shown for t=2 and for t=3.
  • “M\(_{12}\)”, “M\(_{11}\)”: The Steiner system S(5, 6, 12) corresponds to the Mathieu group M\(_{12}\), which induces S(4, 5, 11) and Mathieu group M\(_{11}\).
  • “PSL\(_2\)(23)”: There is a known Steiner system S(5, 6, 24), as described here and here, which induces S(4, 5, 23).
• For the entries marked “???”, we simply don’t know if there’s a Steiner system here!