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://math.ccrwest.org/cover.html 
[2]  Coverings, Daniel Gordon and Douglas Stinson, https://math.ccrwest.org/gordon/hcd.pdf from the Handbook of Combinatorial Designs 
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=[], blocks=[], low_bd=0, method='', creator='', timestamp='')¶ Bases:
sage.structure.sage_object.SageObject
Covering design.
INPUT:
v,k,t
– integer parameters of the covering design.size
(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 a covering design, without all the 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
()¶ Checks that 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() #Fano had an article in 1892, I don't know the date it appeared '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)¶ Gives the best known \((v,k,t)\) covering design, using the database available at https://math.ccrwest.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 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
This function raises a ValueError if the
(v,k,t)
parameters are not found in the database.

sage.combinat.designs.covering_design.
schonheim
(v, k, t)¶ Schonheim lower bound for size of 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:
\((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]\).