Combinatorics – How to Construct a Steiner System

combinatorial-designscombinatorics

I am looking for a way to construct the blocks for the Steiner system $S(2, 6, 96)$. For example, a valid construction of the Steiner system $S(2, 3, 7)$ would be the following:

[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[2, 4, 7]
[2, 5, 6]
[3, 4, 6]
[3, 5, 7]

I am trying to determine a method producing a valid construction for $S(2, 6, 96)$.

The first question is whether the system $S(2, 6, 96)$ exists. The two major rules for admissibility that I am aware of are:

  1. If there exists an $S(t, k, n)$ then there also exists an $S(t-1, k-1, n-1)$
  2. If there exists an $S(t, k, n)$ then $C(k, t)$ divides $C(n, t)$

For the first rule this means that $S(1, 5, 95)$ should also exist. This is simple enough and can even be written out by hand. This is simply 19 groups of 5 unique numbers.

[1, 2, 3, 4, 5]
[6, 7, 8, 9, 10]
[11, 12, 13, 14, 15]
[...]

The second rule also appears to be true as well.

  • $C(n, t) = C(96, 2) = 4560$
  • $C(k, t) = C(6, 2) = 15$
  • $4560/15 = 304$

This implies that there should be 304 blocks of length 6 that contain all 4560 unique pairs of 1 through 96.

  • Is there a way to construct the Steiner system $S(2,6,96)$?
  • More generally, is there a method to construct any valid Steiner system of $S(2, k, n)$?

Outside of the Witt Design, I was unable to find any literature regarding Steiner systems for $k$ values above 3 or 4 (Steiner Triple Systems and Steiner Quadruple Systems). With that in mind, any help on breaking down the problem into smaller chunks to help direct me would also be appreciated.

Thanks in advance!

Best Answer

This is probably not the answer you are looking for, but it is the best I can do.

The La Jolla covering repository is a database of the best known covering designs. A Steiner system with parameters $(t,k,n)$ is just a perfect covering design, where every $t$-set is covered exactly once. Therefore, if an $S(t,k,n)$ exists, and the parameters are small enough, you can find it in the database.

Here is the entry for $C(2,6,96)$, which shows how to construct the specific Steiner system you asked about: https://ljcr.dmgordon.org/cover/show_cover.php?v=96&k=6&t=2

Related Question