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

This software is released under the terms of the GNU General Public License, version 2 or above (your choice). For details on licensing, see the accompanying documentation.

REFERENCES:

[1] Block design from wikipedia, http://en.wikipedia.org/wiki/Block_design
[2] What is a block design?, http://designtheory.org/library/extrep/html/node4.html (in ‘The External Representation of Block Designs’ by Peter J. Cameron, Peter Dobcsanyi, John P. Morgan, Leonard H. Soicher)

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.

TODO: Implement DerivedDesign, ComplementaryDesign, Hadamard3Design

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

Input: n is the Euclidean dimension, so the number of points is $v = |F^n|$ (F = GF(q), some q) d is the dimension of the (affine) subspaces of $P = GF(q)^n$ which make up the blocks.

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

EXAMPLES:

sage: BD = AffineGeometryDesign(3, 1, GF(2))
sage: BD.parameters()
(2, 8, 2, 2)
sage: BD.is_block_design()
(True, [2, 8, 2, 2])
sage: BD = AffineGeometryDesign(3, 2, GF(2))
sage: BD.parameters()
(2, 8, 4, 12)
sage: BD.is_block_design()
(True, [3, 8, 4, 4])

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

sage.combinat.designs.block_design.HadamardDesign(n)¶

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: HadamardDesign(7)
Incidence structure with 7 points and 7 blocks
sage: print 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:

[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, method=None)¶

Input: n is the projective dimension, so the number of points is v = PPn(GF(q)) d is the dimension of the subspaces of P = PPn(GF(q)) which make up the blocks, so b is the number of d-dimensional subspaces of P

Wraps GAP Design’s PGPointFlatBlockDesign. Does not require GAP’s Design.

EXAMPLES:

sage: ProjectiveGeometryDesign(2, 1, GF(2))
Incidence structure with 7 points and 7 blocks
sage: BD = ProjectiveGeometryDesign(2, 1, GF(2), method="gap") # requires optional gap package 'design'
sage: BD.is_block_design()                                     # requires optional gap package 'design'
(True, [2, 7, 3, 1])

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 W24, the unique (up to isomorphism) 5-(24,8,1) design. If n=12 then this function returns the small Witt design W12, the unique (up to isomorphism) 5-(12,6,1) design. The other values of n return a block design derived from these.

REQUIRES: GAP’s Design package.

EXAMPLES:

sage: BD = WittDesign(9)   # requires optional gap package 'design'
sage: BD.parameters()      # requires optional gap package 'design'
(2, 9, 3, 1)
sage: BD                   # requires optional gap package 'design'
Incidence structure with 9 points and 12 blocks
sage: print BD             # requires optional gap package 'design'
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 = WittDesign(12)  # requires optional gap package 'design'
sage: BD.parameters(t=5)   # requires optional gap package 'design'
(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 mod 6$ or $n \equiv 3 mod 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: from sage.combinat.designs.block_design import steiner_triple_system
sage: sts = 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: steiner_triple_system(10)
...
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 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)

Block designs.¶

Previous topic

Next topic

This Page

Navigation

Block designs.¶

Previous topic

Next topic

This Page

Quick search

Navigation