Combinatorial designs

The last several posts have been building up to this one, moving from tangible to more abstract.

The posts on finite geometry gave examples of Steiner triples and more generally Steiner systems, introduced in the previous post. Combinatorial designs take this one step further.

The previous post gave the following definition:

A Steiner triple system, written STS(n), is a collection of three-element subsets, called blocks, of a set X with n elements, such that every two-element subset ofX belongs to exactly one block.

The post pointed out that the smallest projective plane is STS(7) and the smallest affine plane is STS(9).

The post then defined a general Steiner system:

A Steiner systemS(t,k,n) is a collection of k-element subsets, called blocks, of a set X with n elements, such that every t-element subset of X belongs to exactly one block.

Moving from Steiner triples to Steiner systems we generalized the size of the blocks from 3 to k, and generalized the size of sets contained in a unique block from 2 tot.

Combinatorial designs take this one step further by generalizing the number of blocks that a set oft elements falls in from 1 to .

Unfortunately when we go from Steiner systems to combinatorial designs the notation changes and the order of the parameters changes.

A design with parameters (n,q,r, ) is a collection ofq-element subsets of ann-element setX such that everyr-element subset ofX is contained in exactly blocks.

So a Steiner systemS(t,k,n) corresponds to a (n,k,t, 1) design.

Existence of designs

Given a set of parameters (n,q,r, ) there may or may not exist a design with these parameters. It's easy to show that a few consistency conditions are necessary. It was long conjectured that these conditions were sufficient, except possibly for a finite number of values ofn. Peter Keevash proved in 2024 that the conjecture is correct.

Theorem [1]: Fix q > r >= 1 and >= 1. There is anN, depending on q, r, and , such that for every n > N with

for all 0 i r, a design with parameters (n, q, r, ) exists.

[1] Peter Keevash. The existence of designs. https://arxiv.org/abs/1401.3665v4

The post Combinatorial designs first appeared on John D. Cook.