Steiner systems exist

A Steiner system S(t,k,n) is a collection of k-subsets (called “blocks”) of an n-set of “points” with the property that any t-set of points is contained in a unique block. To avoid trivial cases, we assume that t<k<n.

Since the existence question was first posed, apparently by Woolhouse in 1844, and solved in the special case t=2, k=3 (Steiner triple systems) by Kirkman in 1847, the existence problem (for which values of the parameters do they exist) has been regarded as one of the most difficult in combinatorial design theory. In particular, only finitely many were known with t≥4, and none with t≥6.

There are necessary conditions known as the “divisibility conditions”. For each number i between 0 and t−1, the number of blocks containing a set of i points can be counted: it is


So all these numbers must be integers.

My former colleague Peter Keevash put a 56-page preprint on the arXiv last month proving that, for given k and t, if n is sufficiently large and the divisibility conditions are satisfied, then a Steiner system exists. Even though it is not clear how large “sufficiently large” is, this is a stunning result.

But he has done more. If “exactly one” is replaced by “exactly λ” in the definition, we have a t-design. There are divisibility conditions similar to the above: just put λ in the numerator. Peter shows that these exist for all sufficiently large n satisfying the divisibility conditions as well, though this is a bit harder.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in mathematics and tagged , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.