# Block designs.¶

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.

## Functions and methods¶

sage.combinat.designs.block_design.AffineGeometryDesign(n, d, F)

Returns an Affine Geometry Design.

INPUT:

• $$n$$ (integer) – the Euclidean dimension. The number of points is $$v=|F^n|$$.
• $$d$$ (integer) – the dimension of the (affine) subspaces of $$P = GF(q)^n$$ which make up the blocks.
• $$F$$ – a Finite Field (i.e. FiniteField(17)), or a prime power (i.e. an integer)

$$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

$v = q^n,\ k = q^d , \lambda =\frac{(q^{n-1}-1) \cdots (q^{n+1-d}-1)}{(q^{n-1}-1) \cdots (q-1)}.$

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)

sage.combinat.designs.block_design.BlockDesign(max_pt, blks, name=None, test=True)

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
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:

• [CvL] P. Cameron, J. H. van Lint, Designs, graphs, codes and their links, London Math. Soc., 1991.
sage.combinat.designs.block_design.ProjectiveGeometryDesign(n, d, F, algorithm=None)

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:

• n is the projective dimension
• d is the dimension of the subspaces of $$P = PPn(F)$$ which make up the blocks.
• F is a finite field.
• algorithm – set to None by default, which results in using Sage’s own implementation. In order to use GAP’s implementation instead (i.e. its PGPointFlatBlockDesign function) set algorithm="gap". Note that GAP’s “design” package must be available in this case.

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])

sage.combinat.designs.block_design.ProjectivePlaneDesign(n, type='Desarguesian')

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.

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'.

sage.combinat.designs.block_design.WittDesign(n)

INPUT:

• n is in $$9,10,11,12,21,22,23,24$$.

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)

sage.combinat.designs.block_design.steiner_triple_system(n)

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:

• n returns a Steiner Triple System of $$\{0,...,n-1\}$$

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
sage.combinat.designs.block_design.tdesign_params(t, v, k, L)

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)


Covering designs: coverings of $$t$$-element subsets of a $$v$$-set by $$k$$-sets