Covering designs

On this page I have collected all non-isomorphic (n,k,t)-covering designs. The designs were generated using integer programming, mainly using glpk, and isomorphism reduction was done using Brendan McKay's Nauty. The generation program is complete so unless there has been an undetected computer error this list should be complete.
Generating these designs requires large amounts of computer time and I am grateful for having been given access to the resources of, among others, the computing centra :C3SE, HPC2N, NSCand PDC.


Definition
  1. An (n,k,t)-covering design is a family F of k-subsets of 1...n such that every t-subset of 1...n is a subset of some member of F.
  2. The size of F is the number of sets in F.
  3. We say that F is an optimum (n,k,t)-covering design if no other (n,k,t)-covering design has smaller size.
  4. We say that two designs F and H are isomorphic if F can be mapped to H by a permutation of 1...n

Dan Gordon maintains a webpage with the latest results on covering designs. La Jolla Covering Repository
I also have page with double covering designs where each t-set is covered by at least 2 of the k-sets.

References

These are some of my papers relating to covering designs. For abstracts and actual papers visit my publications page
  1. Klas Markström
    Turan graphs for 3-uniform complete graphs of small order
  2. Klas Markström
    Extremal graphs and bounds for the Turan density of the 4-uniform K5
  3. Klas Markström, John Talbot
    On the density of 2-colourable 3-graphs in which any four points span at most two edges

The designs

The format for the files is as follows.
  1. A file named "covdes-n=x-k=y-t=z" contains all non-isomorphic covering designs with the given parameters.
  2. Every design consists of a sequence of lines, each representing a block in the design, followed by a line with "---" marking the end of the design.
  3. Each block is described as a sequence of integers separated by a white space, each integer represents an element of the block.

The design archive

  1. Update 13/01/04 Major update of the page for double covering designs.
  2. Update 12/06/26 Added: (12,7,4), added size of (14,3,2) and incomplete list of such designs, (15,10,2), (16,10,2). (16,11,3), (16,11,2), (17,12,2), (18,12,2), (18,13,2), (18,13,3), (19,14,3), added incomplete list of (13,5,2) designs
  3. Update 11/08/30 Fixed typo on the number of (8,5,3) designs
  4. Update 10/01/05 Added: (20,16,6), (20,16,7)
  5. Update 09/09/10 Added: (16,12,2), (17,13,3), (18,14,4), (19,15,5), size of (20,16,6), (14,9,2), (15,10,3)
  6. Update 09/09/09 Added: (14,10,2), (15,11,3), (16,12,4), (17,13,5), size of (18,14,6), (15,11,2), (16,12,3), (17,13,4), (18,14,5), (19,15,6)
  7. Update 09/09/08 Added: (18,15,11), (19,16,12), (20,17,13), (18,15,10), (13,7,2), (13,4,2), (13,3,2)
  8. Update 08/09/23 Added: (20,17,11), size of (19,16,11), (16,13,10), (17,14,11), size of (18,15,12), (17,14,12), (16,13,11), (17,14,13), (18,15,14)
  9. Update 08/03/03 Added: (18,14,2), (19,15,3), (20,16,4), (19,15,2), (20,16,3), (21,17,4), (22,18.5), (20,16,2), (21,17,3), (22,18,4), (23,19,5)
  10. Update 08/02/10: Added (17,14,2), (18,15,3), (19,16,4), (20,17,5), (21,18,6), (18,15,2), (19,16,3), (20,17,4), (21,18,5), (22,19,6), (23,20,7), (19,16,2), (20,17,3), (21,18,4), (22,19,5), (23,20,6), (24,21,7), (20,17,2), (21,18,3), (22,19,4), (23,20,5), (24,21,6), (25,22,7), (26,23,8)
  11. Update: 08/01/30: Added the following designs: (15,12,2), (16,13,3), (17,14,4), (18,15,5), (19,16,6), (20,17,7), (21,18,8), (22,19,9), (23,20,10).
  12. Update: 08/01/28: Added the (12,5,3)-designs.
  13. Update: 07/10/19: Added the (11,4,3)-designs.

The size and number of non-isomorphic covering designs

These tables only contain designs on at most 20 points but the archive contains larger designs as well. The size and numbers of of the larger designs can be found on my page for Turan Hypergraphs.

A table entry of the form "S, N" means that an optimal covering design with the given parameters has size S and there exists N non-isomorphic such designs.
N=6
k/t 4 3 2
4 15, 1 6, 1 3, 1
3 20, 1 6, 1
2 15, 1
N=7
k/t 5 4 3 2
5 21, 1 9, 1 5, 1 3, 1
4 35, 1 12, 4 5, 4
3 35, 1 7, 1
2 21, 1
N=8
k/t 6 5 4 3 2
6 , 1
5 , 1 20, 6 8, 3 4, 1
4 , 1 14, 1 6, 3
3 , 1 11, 5
2 , 1
N=9
k/t 7 6 5 4 3 2
7 , 1
6 , 1 30, 2 12, 1 7, 4 3, 1
5 , 1 30, 3 12, 16 5, 1
4 , 1 25, 77 8, 17
3 , 1 12, 1
2 , 1
N=10
k/t 8 7 6 5 4 3 2
8 , 1
7 , 1 45, 20 20, 5 10, 2 6, 5 3, 1
6 , 1 50, 1 20, 1 10, 72 4, 1
5 , 1 51, 40 17, 218 6, 2
4 , 1 30, 1 9, 4
3 , 1 17, 58
2 , 1
N=11
k/t 9 8 7 6 5 4 3 2
9 , 1
8 , 1 63, 40 29, 1 16, 38 9, 10 5, 1 3, 1
7 , 1 84, 3 34, 8 17, 136 8, 9 4, 3
6 , 1 >=98, >=1 32, 1 11, 1 6, 277
5 , 1 66, 1 20, 1 7, 2
4 , 1 47, 121500 11, 2
3 , 1 19, 2
2 , 1
N=12
k/t 10 9 8 7 6 5 4 3 2
10 , 1
9 , 1 84, 4 40, 16 22, 29 12, 5 8, 5 4, 1 3, 1
8 , 1 126, 3 51, 7 26, 7 12, 1 6, 1 3, 1
7 , 1 24, 356 11, 2217 5, 17
6 , 1 132, 1 41, 1 15, 68 6, 7
5 , 1 113, ? 29, 216 9, 107
4 , 1 57, 13 12, 1
3 , 1 24, 412
2 , 1
N=13
k/t 11 10 9 8 7 6 5 4 3 2
11 , 1
10 , 1 112, 138 52, 1 30, 109 16, 1 11, 11 7, 4 4, 1 3, 1
9 , 1 185, 1 19, 1 10, 1 6, 4 3, 1
8 , 1 18, 1 4, 1
7 , 1 78, 1 6, ? 6, 8260
6 , 1 7, 6
5 , 1 34, 29 10, >=30
4 , 1 13, 1
3 , 1 26, 2
2 , 1
N=14
k/t 12 11 10 9 8 7 6 5 4 3 2
12 , 1
11 , 1 144, 286 70. 31 40, 1343 22, 1 14, 4 10, 18 6, 1 4, 1 3, 1
10 , 1 259, 1 29, 1 14, 1 9, 3 5, 1 3, 1
9 , 1 8, 14 4, 4
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1 33, >= 323571
2 , 1
N=15
k/t 13 12 11 10 9 8 7 6 5 4 3 2
13 , 1
12 , 1 180, 8 89, 3 50, 21 30, 18 18, 1 13, 24 9, 8 5, 1 4, 1 3, 1
11 , 1 357, 1 42, 1 21, 1 13, 3 8, 1 5, 3 3, 1
10 , 1 7, 10 3, 1
9 , 1
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1
2 , 1
N=16
k/t 14 13 12 11 10 9 8 7 6 5 4 3 2
14 , 1
13 , 1 225, 958 112, 90 65, 20788 39, 6 24, 4 16, 9 12, 26 8, 5 5, 1 4, 1 3, 1
12 , 1 476, 1 28, 1 19, 16 12, 7 7, 1 4, 1 3, 1
11 , 1 6,1 3,1
10 , 1 4,3
9 , 1
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1
2 , 1
N=17
k/t 15 14 13 12 11 10 9 8 7 6 5 4 3 2
15 , 1
14 , 1 275, 2028 136, 1 80 , 7863 49, 4 31, 4 20, 3 15, 32 11, 22 7, 1 5, 1 4, 1 3, 1
13 , 1 26, 16 11, 13 7, 4 4, 1 3, 1
12 , 1 3, 1
11 , 1
10 , 1
9 , 1
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1
2 , 1
N=18
k/t 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
16 , 1
15 , 1 330, 16 ? 98, ? 60, 145 40, 1749 24, 1 18, 10 14, 54 10, 8 6, 1 5, 1 4, 1 3, 1
14 , 1 34,1 15, ? 9, 1 6, 1 4, 1 3, 1
13 , 1 5,1 3,1
12 , 1 3,1
11 , 1
10 , 1
9 , 1
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1
2 , 1
N=19
k/t 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
17 , 1
16 , 1 ? ? ? 72, 1 49, 50+ 32, 5 22, 2 17, 55 13, 35 9, 5 6, 1 5, 1 4, 1 3, 1
15 ,1 13, 1 9, 4 6, 3 4, 1 3, 1
14 , 1 5,4
13 , 1
12 , 1
11 , 1
10 , 1
9 , 1
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1
2 , 1
N=20
k/t 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2
18 , 1
17 , 1 ? ? ? 87, 1 ? 40, 97 28, 38 20, 17 16, 79 12, 23 8, 1 6, 1 5, 1 4, 1 3, 1
16 , 1 17, 1 12, 3 8, 1 5, 1 4, 1 3, 1
15 ,1
14 , 1
13 , 1
12 , 1
11 , 1
10 , 1
9 , 1
8 , 1
7 , 1
6 , 1
5 , 1
4 , 1
3 , 1
2 , 1