Covering designs: coverings of \(t\)element subsets of a \(v\)set by \(k\)sets¶
A \((v, k, t)\) covering design \(C\) is an incidence structure consisting of a set of points \(P\) of order \(v\), and a set of blocks \(B\), where each block contains \(k\) points of \(P\). Every \(t\)element subset of \(P\) must be contained in at least one block.
If every \(t\)set is contained in exactly one block of \(C\), then we have a block design. Following the block design implementation, the standard representation of a covering design uses \(P = [0, 1, ..., v1]\).
In addition to the parameters and incidence structure for a covering design from this database, we include extra information:
Best known lower bound on the size of a \((v, k, t)\)covering design
Name of the person(s) who produced the design
Method of construction used
Date when the design was added to the database
REFERENCES:
 1
La Jolla Covering Repository, https://ljcr.dmgordon.org/cover.html
 2
Daniel M. Gordon and Douglas R. Stinson, Coverings, Chapter 1 in: Charles J. Colbourn and Jeffrey H. Dinitz, Handbook of Combinatorial Designs, 2nd Edition, 2006. https://www.dmgordon.org/papers/hcd.pdf
AUTHORS:
Daniel M. Gordon (20081222): initial version
Classes and methods¶

class
sage.combinat.designs.covering_design.
CoveringDesign
(v=0, k=0, t=0, size=0, points=None, blocks=None, low_bd=0, method='', creator='', timestamp='')¶ Bases:
sage.structure.sage_object.SageObject
Covering design.
INPUT:
v
,k
,t
– integer parameters of the covering designsize
(integer)points
– list of points (default points are \([0, ..., v1]\))blocks
low_bd
(integer) – lower bound for such a designmethod
,creator
,timestamp
– database information

creator
()¶ Return the creator of the covering design
This field is optional, and is used in a database to give attribution for the covering design It can refer to the person who submitted it, or who originally gave a construction
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], ....: [2, 4, 5]],0, 'Projective Plane', 'Gino Fano') sage: C.creator() 'Gino Fano'

incidence_structure
()¶ Return the incidence structure of this design, without extra parameters.
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: D = C.incidence_structure() sage: D.ground_set() [0, 1, 2, 3, 4, 5, 6] sage: D.blocks() [[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]

is_covering
()¶ Check all \(t\)sets are in fact covered by the blocks of
self
.Note
This is very slow and wasteful of memory.
EXAMPLES:
sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.is_covering() True sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], ....: [2, 4, 6]], 0, 'not a covering') # last block altered sage: C.is_covering() False

k
()¶ Return \(k\), the size of blocks of the covering design
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.k() 3

low_bd
()¶ Return a lower bound for the number of blocks a covering design with these parameters could have.
Typically this is the Schonheim bound, but for some parameters better bounds have been shown.
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.low_bd() 7

method
()¶ Return the method used to create the covering design.
This field is optional, and is used in a database to give information about how coverings were constructed.
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.method() 'Projective Plane'

size
()¶ Return the number of blocks in the covering design
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.size() 7

t
()¶ Return \(t\), the size of sets which must be covered by the blocks of the covering design
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.t() 2

timestamp
()¶ Return the time that the covering was submitted to the database
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]],0, 'Projective Plane', ....: 'Gino Fano', '18920101 00:00:00') sage: C.timestamp() # No exact date known; in Fano's 1892 article '18920101 00:00:00'

v
()¶ Return \(v\), the number of points in the covering design.
EXAMPLES:
sage: from sage.combinat.designs.covering_design import CoveringDesign sage: C = CoveringDesign(7, 3, 2, 7, range(7), [[0, 1, 2], ....: [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], ....: [2, 3, 6], [2, 4, 5]], 0, 'Projective Plane') sage: C.v() 7

sage.combinat.designs.covering_design.
best_known_covering_design_www
(v, k, t, verbose=False)¶ Return the best known \((v, k, t)\) covering design from an online database.
This uses the La Jolla Covering Repository, a database available at https://ljcr.dmgordon.org/cover.html
INPUT:
v
– integer, the size of the point set for the designk
– integer, the number of points per blockt
– integer, the size of sets covered by the blocksverbose
– bool (default:False
), print verbose message
OUTPUT:
A
CoveringDesign
object representing the(v, k, t)
covering design with smallest number of blocks available in the database.EXAMPLES:
sage: from sage.combinat.designs.covering_design import ( # optional  internet ....: best_known_covering_design_www) sage: C = best_known_covering_design_www(7, 3, 2) # optional  internet sage: print(C) # optional  internet C(7, 3, 2) = 7 Method: lex covering Submitted on: 19961201 00:00:00 0 1 2 0 3 4 0 5 6 1 3 5 1 4 6 2 3 6 2 4 5
A ValueError is raised if the
(v, k, t)
parameters are not found in the database.

sage.combinat.designs.covering_design.
schonheim
(v, k, t)¶ Return the Schonheim lower bound for the size of such a covering design.
INPUT:
v
– integer, size of point setk
– integer, cardinality of each blockt
– integer, cardinality of sets being covered
OUTPUT:
The Schonheim lower bound for such a covering design’s size: \(C(v, k, t) \leq \lceil(\frac{v}{k} \lceil \frac{v1}{k1} \cdots \lceil \frac{vt+1}{kt+1} \rceil \cdots \rceil \rceil\)
EXAMPLES:
sage: from sage.combinat.designs.covering_design import schonheim sage: schonheim(10, 3, 2) 17 sage: schonheim(32, 16, 8) 930

sage.combinat.designs.covering_design.
trivial_covering_design
(v, k, t)¶ Construct a trivial covering design.
INPUT:
v
– integer, size of point setk
– integer, cardinality of each blockt
– integer, cardinality of sets being covered
OUTPUT:
A trivial \((v, k, t)\) covering design
EXAMPLES:
sage: C = trivial_covering_design(8, 3, 1) sage: print(C) C(8, 3, 1) = 3 Method: Trivial 0 1 2 0 6 7 3 4 5 sage: C = trivial_covering_design(5, 3, 2) sage: print(C) 4 <= C(5, 3, 2) <= 10 Method: Trivial 0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 4
NOTES:
Cases are:
\(t=0\): This could be empty, but it’s a useful convention to have one block (which is empty if $k=0$).
\(t=1\) : This contains \(\lceil v/k \rceil\) blocks: \([0, ..., k1], [k, ..., 2k1], ...\). The last block wraps around if \(k\) does not divide \(v\).
anything else: Just use every \(k\)subset of \([0, 1,..., v1]\).