This module implements two constructions of Balanced Incomplete Block Designs:
These BIBD can be obtained through the BalancedIncompleteBlockDesign() method, available in Sage as designs.BalancedIncompleteBlockDesign.
EXAMPLES:
sage: designs.BalancedIncompleteBlockDesign(7,3)
Incidence structure with 7 points and 7 blocks
sage: designs.BalancedIncompleteBlockDesign(7,3).blocks()
[[0, 1, 3], [0, 2, 4], [0, 5, 6], [1, 2, 6], [1, 4, 5], [2, 3, 5], [3, 4, 6]]
sage: designs.BalancedIncompleteBlockDesign(13,4).blocks()
[[0, 1, 2, 12], [0, 3, 6, 9], [0, 4, 8, 11], [0, 5, 7, 10], [1, 3, 8, 10],
[1, 4, 7, 9], [1, 5, 6, 11], [2, 3, 7, 11], [2, 4, 6, 10], [2, 5, 8, 9],
[3, 4, 5, 12], [6, 7, 8, 12], [9, 10, 11, 12]]
Decompositions of \(K_v\) into \(K_4\) (i.e. \((v,4,1)\)-BIBD) are built following Douglas Stinson’s construction as presented in [Stinson2004] page 167. It is based upon the construction of \((v\{4,5,8,9,12\})\)-PBD (see the doc of PBD_4_5_8_9_12()), knowing that a \((v\{4,5,8,9,12\})\)-PBD on \(v\) points can always be transformed into a \(((k-1)v+1,4,1)\)-BIBD, which covers all possible cases of \((v,4,1)\)-BIBD.
Returns a \((v,k,1)\)-BIBD from a \((r,K)\)-PBD where \(r=(v-1)/(k-1)\).
This is Theorem 7.20 from [Stinson2004].
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.bibd import PBD_4_5_8_9_12
sage: from sage.combinat.designs.bibd import BIBD_from_PBD
sage: from sage.combinat.designs.bibd import _check_pbd
sage: PBD = PBD_4_5_8_9_12(17)
sage: bibd = _check_pbd(BIBD_from_PBD(PBD,52,4),52,[4])
Returns a BIBD of parameters \(v,k\).
A Balanced Incomplete Block Design of parameters \(v,k\) is a collection \(\mathcal C\) of \(k\)-subsets of \(V=\{0,\dots,v-1\}\) such that for any two distinct elements \(x,y\in V\) there is a unique element \(S\in \mathcal C\) such that \(x,y\in S\).
More general definitions sometimes involve a \(\lambda\) parameter, and we assume here that \(\lambda=1\).
For more information on BIBD, see the corresponding Wikipedia entry.
INPUT:
See also
TODO:
- Implement \((v,5,1)\)-BIBD using this text.
- Implement other constructions from the Handbook of Combinatorial Designs.
EXAMPLES:
sage: designs.BalancedIncompleteBlockDesign(7,3).blocks()
[[0, 1, 3], [0, 2, 4], [0, 5, 6], [1, 2, 6], [1, 4, 5], [2, 3, 5], [3, 4, 6]]
sage: B = designs.BalancedIncompleteBlockDesign(21,5, use_LJCR=True) # optional - internet
sage: B # optional - internet
Incidence structure with 21 points and 21 blocks
sage: B.blocks() # optional - internet
[[0, 1, 2, 3, 20], [0, 4, 8, 12, 16], [0, 5, 10, 15, 19],
[0, 6, 11, 13, 17], [0, 7, 9, 14, 18], [1, 4, 11, 14, 19],
[1, 5, 9, 13, 16], [1, 6, 8, 15, 18], [1, 7, 10, 12, 17],
[2, 4, 9, 15, 17], [2, 5, 11, 12, 18], [2, 6, 10, 14, 16],
[2, 7, 8, 13, 19], [3, 4, 10, 13, 18], [3, 5, 8, 14, 17],
[3, 6, 9, 12, 19], [3, 7, 11, 15, 16], [4, 5, 6, 7, 20],
[8, 9, 10, 11, 20], [12, 13, 14, 15, 20], [16, 17, 18, 19, 20]]
sage: designs.BalancedIncompleteBlockDesign(20,5, use_LJCR=True) # optional - internet
Traceback (most recent call last):
...
ValueError: No such design exists !
TESTS:
A BIBD from a Finite Projective Plane:
sage: _ = designs.BalancedIncompleteBlockDesign(21,5)
Returns a \((v,\{4,5,8,9,12\})-PBD\) on \(v\) elements.
A \((v,\{4,5,8,9,12\})\)-PBD exists if and only if \(v\equiv 0,1 \pmod 4\). The construction implemented here appears page 168 in [Stinson2004].
INPUT:
EXAMPLES:
sage: designs.BalancedIncompleteBlockDesign(40,4).blocks() # indirect doctest
[[0, 1, 2, 12], [0, 3, 6, 9], [0, 4, 8, 11], [0, 5, 7, 10],
[0, 13, 26, 39], [0, 14, 28, 38], [0, 15, 25, 27],
[0, 16, 32, 35], [0, 17, 34, 37], [0, 18, 33, 36],
...
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 [AndHonk97].
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(t=2)
(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:
[AndHonk97] | A short course in Combinatorial Designs, Ian Anderson, Iiro Honkala, Internet Editions, Spring 1997, http://www.utu.fi/~honkala/designs.ps |
Returns a \((v,4,1)\)-BIBD.
A \((v,4,1)\)-BIBD is an edge-decomposition of the complete graph \(K_v\) into copies of \(K_4\). For more information, see BalancedIncompleteBlockDesign(). It exists if and only if \(v\equiv 1,4 \pmod {12}\).
See page 167 of [Stinson2004] for the construction details.
See also
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.bibd import v_4_1_BIBD # long time
sage: for n in range(13,100): # long time
....: if n%12 in [1,4]: # long time
....: _ = v_4_1_BIBD(n, check = True) # long time