A module to help with constructions and computations of block designs and other incidence structures.
A block design is an incidence structure consisting of a set of points and a
set of blocks
, where each block is considered as a subset of
. More
precisely, a block design
is a class of
-element subsets of
such
that the number
of blocks that contain any point
in
is independent
of
, and the number
of blocks that contain any given
-element
subset
is independent of the choice of
(see [1] for more). Such a block
design is also called a
-design, and
(the number of
points),
(the number of blocks),
,
, and
are the parameters
of the design. (In Python, lambda is reserved, so we sometimes use lmbda
or L instead.)
In Sage, sets are replaced by (ordered) lists and the standard representation of
a block design uses , so a block design is specified by
.
REFERENCES:
[1] | Block design from wikipedia, Wikipedia article Block_design |
[2] | What is a block design?, http://designtheory.org/library/extrep/extrep-1.1-html/node4.html (in ‘The External Representation of Block Designs’ by Peter J. Cameron, Peter Dobcsanyi, John P. Morgan, Leonard H. Soicher) |
AUTHORS:
Peter Dobcsanyi and David Joyner (2007-2008)
This is a significantly modified form of the module block_design.py (version 0.6) written by Peter Dobcsanyi peter@designtheory.org. Thanks go to Robert Miller for lots of good design suggestions.
Returns an Affine Geometry Design.
INPUT:
, as it is sometimes denoted, is a
-
design of points and
- flats (cosets of dimension
) in the affine
geometry
, where
Wraps some functions used in GAP Design’s PGPointFlatBlockDesign. Does not require GAP’s Design package.
EXAMPLES:
sage: BD = designs.AffineGeometryDesign(3, 1, GF(2))
sage: BD.parameters()
(2, 8, 2, 1)
sage: BD.is_block_design()
(True, [2, 8, 2, 1])
sage: BD = designs.AffineGeometryDesign(3, 2, GF(2))
sage: BD.parameters()
(2, 8, 4, 3)
sage: BD.is_block_design()
(True, [3, 8, 4, 1])
With an integer instead of a Finite Field:
sage: BD = designs.AffineGeometryDesign(3, 2, 4)
sage: BD.parameters()
(2, 64, 16, 5)
Returns an instance of the IncidenceStructure class.
Requires each B in blks to be contained in range(max_pt). Does not test if the result is a block design.
EXAMPLES:
sage: BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]], name="Fano plane")
Incidence structure with 7 points and 7 blocks
sage: print BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]], name="Fano plane")
Fano plane<points=[0, 1, 2, 3, 4, 5, 6], blocks=[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]>
As described in Section 1, p. 10, in [CvL]. The input n must have the
property that there is a Hadamard matrix of order (and that a
construction of that Hadamard matrix has been implemented...).
EXAMPLES:
sage: designs.HadamardDesign(7)
Incidence structure with 7 points and 7 blocks
sage: print designs.HadamardDesign(7)
HadamardDesign<points=[0, 1, 2, 3, 4, 5, 6], blocks=[[0, 1, 2], [0, 3, 4], [0, 5, 6], [1, 3, 5], [1, 4, 6], [2, 3, 6], [2, 4, 5]]>
REFERENCES:
Returns a projective geometry design.
A projective geometry design of parameters has for points the lines
of
, and for blocks the
-dimensional subspaces of
,
each of which contains
lines.
INPUT:
EXAMPLES:
The points of the following design are the
lines of
. It has
blocks, corresponding to each
2-dimensional subspace of
:
sage: designs.ProjectiveGeometryDesign(2, 1, GF(2))
Incidence structure with 7 points and 7 blocks
sage: BD = designs.ProjectiveGeometryDesign(2, 1, GF(2), algorithm="gap") # optional - gap_packages (design package)
sage: BD.is_block_design() # optional - gap_packages (design package)
(True, [2, 7, 3, 1])
Returns a projective plane of order .
A finite projective plane is a 2-design with lines (or blocks) and
points. For more information on finite projective planes, see the
Wikipedia article Projective_plane#Finite_projective_planes.
INPUT:
n – the finite projective plane’s order
type – When set to "Desarguesian", the method returns
Desarguesian projective planes, i.e. a finite projective plane obtained by
considering the 1- and 2- dimensional spaces of .
For the moment, no other value is available for this parameter.
See also
EXAMPLES:
sage: designs.ProjectivePlaneDesign(2)
Incidence structure with 7 points and 7 blocks
Non-existent ones:
sage: designs.ProjectivePlaneDesign(10)
Traceback (most recent call last):
...
ValueError: No projective plane design of order 10 exists.
sage: designs.ProjectivePlaneDesign(14)
Traceback (most recent call last):
...
ValueError: By the Bruck-Ryser-Chowla theorem, no projective plane of order 14 exists.
An unknown one:
sage: designs.ProjectivePlaneDesign(12)
Traceback (most recent call last):
...
ValueError: If such a projective plane exists, we do not know how to build it.
TESTS:
sage: designs.ProjectivePlaneDesign(10, type="AnyThingElse")
Traceback (most recent call last):
...
ValueError: The value of 'type' must be 'Desarguesian'.
INPUT:
Wraps GAP Design’s WittDesign. If n=24 then this function returns the
large Witt design , the unique (up to isomorphism)
design. If n=12 then this function returns the small Witt design
, the unique (up to isomorphism)
design. The other
values of
return a block design derived from these.
EXAMPLES:
sage: BD = designs.WittDesign(9) # optional - gap_packages (design package)
sage: BD.parameters() # optional - gap_packages (design package)
(2, 9, 3, 1)
sage: BD # optional - gap_packages (design package)
Incidence structure with 9 points and 12 blocks
sage: print BD # optional - gap_packages (design package)
WittDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8], blocks=[[0, 1, 7], [0, 2, 5], [0, 3, 4], [0, 6, 8], [1, 2, 6], [1, 3, 5], [1, 4, 8], [2, 3, 8], [2, 4, 7], [3, 6, 7], [4, 5, 6], [5, 7, 8]]>
sage: BD = designs.WittDesign(12) # optional - gap_packages (design package)
sage: BD.parameters(t=5) # optional - gap_packages (design package)
(5, 12, 6, 1)
Returns a Steiner Triple System
A Steiner Triple System (STS) of a set
is a family
of 3-sets such that for any
there exists exactly one set of
in which they are
both contained.
It can alternatively be thought of as a factorization of
the complete graph with triangles.
A Steiner Triple System of a -set exists if and only if
or
, in which case
one can be found through Bose’s and Skolem’s constructions,
respectively [AndHon97].
INPUT:
EXAMPLE:
A Steiner Triple System on elements
sage: sts = designs.steiner_triple_system(9)
sage: sts
Incidence structure with 9 points and 12 blocks
sage: list(sts)
[[0, 1, 5], [0, 2, 4], [0, 3, 6], [0, 7, 8], [1, 2, 3], [1, 4, 7], [1, 6, 8], [2, 5, 8], [2, 6, 7], [3, 4, 8], [3, 5, 7], [4, 5, 6]]
As any pair of vertices is covered once, its parameters are
sage: sts.parameters()
(2, 9, 3, 1)
An exception is raised for invalid values of n
sage: designs.steiner_triple_system(10)
Traceback (most recent call last):
...
ValueError: Steiner triple systems only exist for n = 1 mod 6 or n = 3 mod 6
REFERENCE:
[AndHon97] | A short course in Combinatorial Designs, Ian Anderson, Iiro Honkala, Internet Editions, Spring 1997, http://www.utu.fi/~honkala/designs.ps |
Return the design’s parameters: . Note that
must be
given.
EXAMPLES:
sage: BD = BlockDesign(7,[[0,1,2],[0,3,4],[0,5,6],[1,3,5],[1,4,6],[2,3,6],[2,4,5]])
sage: from sage.combinat.designs.block_design import tdesign_params
sage: tdesign_params(2,7,3,1)
(2, 7, 7, 3, 3, 1)