Steiner design S(2, 4, 28)

TL;DR

Some considerations on the block design $S(2, 4, 28)$.

Which does not indeed tell us much. OK, let’s restart:

TL;DR

Arranging a tournament for 28 participant, playing games with 4 participants per table, avoiding that any two participants face each other more than once.

Better now?

Where did it start

By now, you are probably quite tired by the series Allocating games in tournaments. I don’t blame you. But let’s recap what I mean with tournament of 4 players per match here:

A number $n$ of participants play a game where each match has $k$ participants at the table. Matches are arranged so that each player competes against each other exactly once. Moreover, matches are arranged in rounds, so that all participants can play almost at the same time.

We already saw that this is indeed possible many times, leading to a number of participants that is the square of the number of players at each table/match. As an example, games with 4 players at the table imply 16 participants.

Can I have more players?

Sure we can do more?

Sure we can.

An example is the Kirkman Schoolgirls Problem, where we are asked to arrange 15 schoolgirls in groups of three each for seven consecutive days, so that each schoolgirl is in the same group as any other one exactly once. Sounds familiar? It’s the same as our definition of tournament above, with three players at the table and 15 overall participants.

So yes, we can organize tournaments for three-players tables with both 9 and 15 participants. It turns out that also 21, 27, … participants are possible.

Four game tournaments

Another interesting configuration is for four-players tables. There are a few designs of type $S(2, 4, 28)$, most of which are present in a file that can be downloaded from this page: Steiner 2-designs.

The different columns of each blocks of 1 and 0 represent a match, while rows represent participants. In this case, each block has 28 rows and 63 columns.

One nice property of tournaments is that matches are scheduled so that players are active in all rounds. A little search over all the designs in the download link ended up finding that only six designs allow for packing all matches in exactly 9 rounds of 7 matches each (which is the maximum that can be done, because there are 28 participants divided in groups of 4 at each round). They are number 484, 503, 912, 913, 977, and 1002.

For our tournament purposes, one suffices - let’s take 1002:

100000011111111000000000000000000000000000000000000000000000000
100000000000000111111110000000000000000000000000000000000000000
100000000000000000000001111111100000000000000000000000000000000
100000000000000000000000000000011111111000000000000000000000000
010000010000000100000001000000010000000101010100000000000000000
010000001000000010000000100000001000000010101010000000000000000
010000000100000001000000010000000100000000000001010101000000000
010000000010000000100000001000000010000000000000101010100000000
001000010000000001000000000100000001000010000000100000010100000
001000001000000000100000000010000000100100000001000000001010000
001000000100000010000000000001000000010001000000001000000001010
001000000010000100000000000000100000001000100000010000000000101
000100010000000000010000001000000000010000001000000100001000100
000100001000000000001000010000000000001000010000000010010001000
000100000100000000000101000000000000100000000010000000100100001
000100000010000000000010100000000001000000000100000001000010010
000010000001000100000000000010000100000000001000000010000100010
000010000000100010000000000100000010000000010000000100000010001
000010000000010001000000000000101000000000000100000000101001000
000010000000001000100000000001010000000000000010000001010000100
000001000001000000001000000001000001000100100000000100100000000
000001000000100000010000000000100000100011000000000011000000000
000001000000010000000010000010000000010000010010110000000000000
000001000000001000000100000100000000001000001101001000000000000
000000100001000000000100001000001000000001000000010000010010000
000000100000100000000010010000010000000000100000001000001100000
000000100000010000001001000000000010000010000001000000000000110
000000100000001000010000100000000100000100000000100000000001001

The arrangement of matches into rounds is as follows (actually, this is an isomorphic arrangement obtained by first re-arranging the incidence matrix above by re-sorting columns and rows):

1,2,3,4:5,12,19,20:6,15,25,26:7,10,13,16:8,14,18,22:9,11,24,28:17,21,23,27
1,5,6,7:2,9,15,27:3,10,11,22:4,8,19,23:12,16,17,24:13,14,21,26:18,20,25,28
1,8,9,10:2,5,14,17:3,6,21,28:4,7,12,25:11,16,20,27:13,15,18,23:19,22,24,26
1,11,12,13:2,16,22,25:3,14,20,23:4,15,21,24:5,9,18,26:6,10,19,27:7,8,17,28
1,14,15,16:2,13,19,28:3,9,17,25:4,5,22,27:6,8,20,24:7,11,18,21:10,12,23,26
1,17,18,19:2,6,11,23:3,8,16,26:4,9,13,20:5,10,21,25:7,14,24,27:12,15,22,28
1,20,21,22:2,10,18,24:3,7,15,19:4,11,17,26:5,16,23,28:6,9,12,14:8,13,25,27
1,23,24,25:2,7,20,26:3,12,18,27:4,10,14,28:5,8,11,15:6,13,17,22:9,16,19,21
1,26,27,28:2,8,12,21:3,5,13,24:4,6,16,18:7,9,22,23:10,15,17,20:11,14,19,25

Goodbye for now!


Comments? Octodon, , GitHub, Reddit, or drop me a line!