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:
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
Bases: sage.structure.sage_object.SageObject
Covering design.
INPUT:
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'
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]]
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
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
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
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'
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
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
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'
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
Gives the best known \((v,k,t)\) covering design, using the database available at http://www.ccrwest.org/
INPUeT:
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.
Schonheim lower bound for size of covering design
INPUT:
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
Construct a trivial covering design.
INPUT:
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: