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 \(P\) and a set of blocks \(B\), where each block is considered as a subset of \(P\). More precisely, a block design \(B\) is a class of \(k\)-element subsets of \(P\) such that the number \(r\) of blocks that contain any point \(x\) in \(P\) is independent of \(x\), and the number \(\lambda\) of blocks that contain any given \(t\)-element subset \(T\) is independent of the choice of \(T\) (see [1] for more). Such a block design is also called a \(t-(v,k,\lambda)\)-design, and \(v\) (the number of points), \(b\) (the number of blocks), \(k\), \(r\), and \(\lambda\) 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 \(P = [0,1,..., v-1]\), so a block design is specified by \((v,B)\).
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:
\(AG_{n,d} (F)\), as it is sometimes denoted, is a \(2\) - \((v, k, \lambda)\) design of points and \(d\)- flats (cosets of dimension \(n\)) in the affine geometry \(AG_n (F)\), 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 \(n+1\) (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 \(n,d,F\) has for points the lines of \(F^{n+1}\), and for blocks the \(d+1\)-dimensional subspaces of \(F^{n+1}\), each of which contains \(\frac {|F|^{d+1}-1} {|F|-1}\) lines.
INPUT:
EXAMPLES:
The points of the following design are the \(\frac {2^{2+1}-1} {2-1}=7\) lines of \(\mathbb{Z}_2^{2+1}\). It has \(7\) blocks, corresponding to each 2-dimensional subspace of \(\mathbb{Z}_2^{2+1}\):
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 \(n\).
A finite projective plane is a 2-design with \(n^2+n+1\) lines (or blocks) and \(n^2+n+1\) 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 \(F_n^3\).
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 \(W_{24}\), the unique (up to isomorphism) \(5-(24,8,1)\) design. If n=12 then this function returns the small Witt design \(W_{12}\), the unique (up to isomorphism) \(5-(12,6,1)\) design. The other values of \(n\) 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 \(\{0,...,n-1\}\) is a family \(S\) of 3-sets such that for any \(i \not = j\) there exists exactly one set of \(S\) in which they are both contained.
It can alternatively be thought of as a factorization of the complete graph \(K_n\) with triangles.
A Steiner Triple System of a \(n\)-set exists if and only if \(n \equiv 1 \pmod 6\) or \(n \equiv 3 \pmod 6\), in which case one can be found through Bose’s and Skolem’s constructions, respectively [AndHon97].
INPUT:
EXAMPLE:
A Steiner Triple System on \(9\) 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: \((t, v, b, r , k, L)\). Note that \(t\) 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)