# 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,..., v-1]$$.

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, http://www.ccrwest.org/cover.html
 [2] Coverings, Daniel Gordon and Douglas Stinson, http://www.ccrwest.org/gordon/hcd.pdf from the Handbook of Combinatorial Designs

AUTHORS:

– Daniel M. Gordon (2008-12-22): 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='')

Covering design.

INPUT:

• v,k,t – integer parameters of the covering design.
• size (integer)
• points – list of points (default points are $$[0,...v-1]$$).
• blocks
• low_bd (integer) – lower bound for such a design
• method, 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.points()
[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','1892-01-01 00:00:00')
sage: C.timestamp()  #Fano had an article in 1892, I don't know the date it appeared
'1892-01-01 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 http://www.ccrwest.org/

INPUeT:

• v – integer, the size of the point set for the design
• k – integer, the number of points per block
• t – integer, the size of sets covered by the blocks
• verbose – 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: 1996-12-01 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 set
• k – integer, cardinality of each block
• t – 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{v-1}{k-1} \cdots \lceil \frac{v-t+1}{k-t+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 set
• k – integer, cardinality of each block
• t – integer, cardinality of sets being covered

OUTPUT:

$$(v,k,t)$$ covering design

EXAMPLE:

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,...,k-1],[k,...,2k-1],...$$. The last block wraps around if $$k$$ does not divide $$v$$.
• anything else: Just use every $$k$$-subset of $$[0,1,...,v-1]$$.