Covering designs: coverings of
-element subsets of a
-set by
-sets¶
A covering design
is an incidence structure consisting of a
set of points
of order
, and a set of blocks
, where each
block contains
points of
. Every
-element subset of
must be contained in at least one block.
If every -set is contained in exactly one block of
, then we
have a block design. Following the block design implementation, the
standard representation of a covering design uses
.
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
-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='')¶ 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).
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
-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
, 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
, 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
, 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
covering design, using the database available at http://www.ccrwest.org/
INPUeT:
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: 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 setk
– integer, cardinality of each blockt
– integer, cardinality of sets being covered
OUTPUT:
The Schonheim lower bound for such a covering design’s size:
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:
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:
: This could be empty, but it’s a useful convention to have one block (which is empty if $k=0$).
: This contains
blocks:
. The last block wraps around if
does not divide
.
- anything else: Just use every
-subset of
.