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
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.
The size of F is the number of sets in F.
We say that F is an optimum (n,k,t)-covering design if no
other (n,k,t)-covering design has smaller size.
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
Klas Markström Turan graphs for 3-uniform complete graphs of small order
Klas Markström Extremal graphs and bounds for the Turan density of the
4-uniform K5
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.
A file named "covdes-n=x-k=y-t=z" contains all
non-isomorphic covering designs with the given parameters.
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.
Each block is described as a sequence of integers separated by
a white space, each integer represents an element of the block.
Update 13/01/04 Major update of the page for double covering designs.
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
Update 11/08/30 Fixed typo on the number of (8,5,3) designs
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).
Update: 08/01/28: Added the (12,5,3)-designs.
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.