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:

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

  \(t=1\) \(t=2\) \(t=3\) \(t=4\) \(t=5\) \(t=6\)
\(v=1\) - - - - - -
\(v=2\) Trivial - - - - -
\(v=3\) Trivial - - - -
\(v=4\) Pairs Trivial - - -
\(v=5\)   Trivial - -
\(v=6\) Pairs     Trivial -
\(v=7\) Fano       Trivial
\(v=8\) Pairs        
\(v=9\)          
\(v=10\) Pairs        
\(v=11\)        
\(v=12\) Pairs        
\(v=13\)          
\(v=14\) Pairs