This module gathers everything related to Balanced Incomplete Block Designs. One can build a BIBD (or check that it can be built) with balanced_incomplete_block_design():
sage: BIBD = designs.balanced_incomplete_block_design(7,3)
In particular, Sage can build a \((v,k,1)\)-BIBD when one exists for all \(k\leq 5\). The following functions are available:
It defines the following functions:
balanced_incomplete_block_design() | Return a BIBD of parameters \(v,k\). |
BIBD_from_TD() | Return a BIBD through TD-based constructions. |
BIBD_from_difference_family() | Return the BIBD associated to the difference family D on the group G. |
BIBD_from_PBD() | Return a \((v,k,1)\)-BIBD from a \((r,K)\)-PBD where \(r=(v-1)/(k-1)\). |
PBD_from_TD() | Return a \((kt,\{k,t\})\)-PBD if \(u=0\) and a \((kt+u,\{k,k+1,t,u\})\)-PBD otherwise. |
steiner_triple_system() | Return a Steiner Triple System. |
v_5_1_BIBD() | Return a \((v,5,1)\)-BIBD. |
v_4_1_BIBD() | Return a \((v,4,1)\)-BIBD. |
PBD_4_5_8_9_12() | Return a \((v,\{4,5,8,9,12\})\)-PBD on \(v\) elements. |
BIBD_5q_5_for_q_prime_power() | Return a \((5q,5,1)\)-BIBD with \(q\equiv 1\pmod 4\) a prime power. |
Construction of BIBD when \(k=4\)
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.
Construction of BIBD when \(k=5\)
Decompositions of \(K_v\) into \(K_4\) (i.e. \((v,4,1)\)-BIBD) are built following Clayton Smith’s construction [ClaytonSmith].
[ClaytonSmith] | (1, 2, 3, 4) On the existence of \((v,5,1)\)-BIBD. http://www.argilo.net/files/bibd.pdf Clayton Smith |
Return a \((5q,5,1)\)-BIBD with \(q\equiv 1\pmod 4\) a prime power.
See Theorem 24 [ClaytonSmith].
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.bibd import BIBD_5q_5_for_q_prime_power
sage: for q in [25, 45, 65, 85, 125, 145, 185, 205, 305, 405, 605]: # long time
....: _ = BIBD_5q_5_for_q_prime_power(q/5) # long time
Return 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])
Return a BIBD through TD-based constructions.
INPUT:
v,k (integers) – computes a \((v,k,1)\)-BIBD.
existence (boolean) – instead of building the design, return:
- True – meaning that Sage knows how to build the design
- Unknown – meaning that Sage does not know how to build the design, but that the design may exist (see sage.misc.unknown).
- False – meaning that the design does not exist.
This method implements three constructions:
If there exists a \(TD(k,v)\) and a \((v,k,1)\)-BIBD then there exists a \((kv,k,1)\)-BIBD.
The BIBD is obtained from all blocks of the \(TD\), and from the blocks of the \((v,k,1)\)-BIBDs defined over the \(k\) groups of the \(TD\).
If there exists a \(TD(k,v)\) and a \((v+1,k,1)\)-BIBD then there exists a \((kv+1,k,1)\)-BIBD.
The BIBD is obtained from all blocks of the \(TD\), and from the blocks of the \((v+1,k,1)\)-BIBDs defined over the sets \(V_1\cup \infty,\dots,V_k\cup \infty\) where the \(V_1,\dots,V_k\) are the groups of the TD.
If there exists a \(TD(k,v)\) and a \((v+k,k,1)\)-BIBD then there exists a \((kv+k,k,1)\)-BIBD.
The BIBD is obtained from all blocks of the \(TD\), and from the blocks of the \((v+k,k,1)\)-BIBDs defined over the sets \(V_1\cup \{\infty_1,\dots,\infty_k\},\dots,V_k\cup \{\infty_1,\dots,\infty_k\}\) where the \(V_1,\dots,V_k\) are the groups of the TD. By making sure that all copies of the \((v+k,k,1)\)-BIBD contain the block \(\{\infty_1,\dots,\infty_k\}\), the result is also a BIBD.
These constructions can be found in http://www.argilo.net/files/bibd.pdf.
EXAMPLES:
First construction:
sage: from sage.combinat.designs.bibd import BIBD_from_TD
sage: BIBD_from_TD(25,5,existence=True)
True
sage: _ = designs.BlockDesign(25,BIBD_from_TD(25,5))
Second construction:
sage: from sage.combinat.designs.bibd import BIBD_from_TD
sage: BIBD_from_TD(21,5,existence=True)
True
sage: _ = designs.BlockDesign(21,BIBD_from_TD(21,5))
Third construction:
sage: from sage.combinat.designs.bibd import BIBD_from_TD
sage: BIBD_from_TD(85,5,existence=True)
True
sage: _ = designs.BlockDesign(85,BIBD_from_TD(85,5))
No idea:
sage: from sage.combinat.designs.bibd import BIBD_from_TD
sage: BIBD_from_TD(20,5,existence=True)
Unknown
sage: BIBD_from_TD(20,5)
Traceback (most recent call last):
...
NotImplementedError: I do not know how to build a (20,5,1)-BIBD!
Return the BIBD associated to the difference family D on the group G.
Let \(G\) be a finite Abelian group. A simple `(G,k)`-difference family (or a `(G,k,1)`-difference family) is a family \(B = \{B_1,B_2,\ldots,B_b\}\) of \(k\)-subsets of \(G\) such that for each element of \(G \backslash \{0\}\) there exists a unique \(s \in \{1,\ldots,b\}\) and a unique pair of distinct elements \(x,y \in B_s\) such that \(x - y = g\).
If \(\{B_1, B_2, \ldots, B_b\}\) is a simple \((G,k)\)-difference family then its set of translates \(\{B_i + g; i \in \{1,\ldots,b\}, g \in G\}\) is a \((v,k,1)\)-BIBD where \(v\) is the cardinality of \(G\).
INPUT:
- ``G`` - a finite additive Abelian group
EXAMPLES:
sage: G = Zmod(21)
sage: D = [[0,1,4,14,16]]
sage: print sorted(G(x-y) for x in D[0] for y in D[0] if x != y)
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
sage: from sage.combinat.designs.bibd import BIBD_from_difference_family
sage: BIBD_from_difference_family(G, D)
[[0, 1, 4, 14, 16],
[1, 2, 5, 15, 17],
[2, 3, 6, 16, 18],
[3, 4, 7, 17, 19],
[4, 5, 8, 18, 20],
[5, 6, 9, 19, 0],
[6, 7, 10, 20, 1],
[7, 8, 11, 0, 2],
[8, 9, 12, 1, 3],
[9, 10, 13, 2, 4],
[10, 11, 14, 3, 5],
[11, 12, 15, 4, 6],
[12, 13, 16, 5, 7],
[13, 14, 17, 6, 8],
[14, 15, 18, 7, 9],
[15, 16, 19, 8, 10],
[16, 17, 20, 9, 11],
[17, 18, 0, 10, 12],
[18, 19, 1, 11, 13],
[19, 20, 2, 12, 14],
[20, 0, 3, 13, 15]]
Return 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.balanced_incomplete_block_design(40,4).blocks() # indirect doctest
[[0, 1, 2, 12], [0, 3, 6, 9], [0, 4, 8, 10],
[0, 5, 7, 11], [0, 13, 26, 39], [0, 14, 25, 28],
[0, 15, 27, 38], [0, 16, 22, 32], [0, 17, 23, 34],
...
Check that trac ticket #16476 is fixed:
sage: from sage.combinat.designs.bibd import PBD_4_5_8_9_12
sage: for v in (0,1,4,5,8,9,12,13,16,17,20,21,24,25):
....: _ = PBD_4_5_8_9_12(v)
Return a \((kt,\{k,t\})\)-PBD if \(u=0\) and a \((kt+u,\{k,k+1,t,u\})\)-PBD otherwise.
This is theorem 23 from [ClaytonSmith]. The PBD is obtained from the blocks a truncated \(TD(k+1,t)\), to which are added the blocks corresponding to the groups of the TD. When \(u=0\), a \(TD(k,t)\) is used instead.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.bibd import PBD_from_TD
sage: from sage.combinat.designs.bibd import _check_pbd
sage: PBD = PBD_from_TD(2,2,1); PBD
[[0, 2, 4], [0, 3], [1, 2], [1, 3, 4], [0, 1], [2, 3]]
sage: _check_pbd(PBD,2*2+1,[2,3])
[[0, 2, 4], [0, 3], [1, 2], [1, 3, 4], [0, 1], [2, 3]]
Return 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:
v,k (integers)
existence (boolean) – instead of building the design, return:
- True – meaning that Sage knows how to build the design
- Unknown – meaning that Sage does not know how to build the design, but that the design may exist (see sage.misc.unknown).
- False – meaning that the design does not exist.
use_LJCR (boolean) – whether to query the La Jolla Covering Repository for the design when Sage does not know how to build it (see best_known_covering_design_www()). This requires internet.
TODO:
- Implement other constructions from the Handbook of Combinatorial Designs.
EXAMPLES:
sage: designs.balanced_incomplete_block_design(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.balanced_incomplete_block_design(66, 6, use_LJCR=True) # optional - internet
sage: B # optional - internet
Incidence structure with 66 points and 143 blocks
sage: B.blocks() # optional - internet
[[0, 1, 2, 3, 4, 65], [0, 5, 24, 25, 39, 57], [0, 6, 27, 38, 44, 55], ...
sage: designs.balanced_incomplete_block_design(66, 6, use_LJCR=True) # optional - internet
Incidence structure with 66 points and 143 blocks
sage: designs.balanced_incomplete_block_design(141, 6)
Traceback (most recent call last):
...
NotImplementedError: I don't know how to build a (141,6,1)-BIBD!
TESTS:
sage: designs.balanced_incomplete_block_design(85,5,existence=True)
True
sage: _ = designs.balanced_incomplete_block_design(85,5)
A BIBD from a Finite Projective Plane:
sage: _ = designs.balanced_incomplete_block_design(21,5)
Some trivial BIBD:
sage: designs.balanced_incomplete_block_design(10,10)
Incidence structure with 10 points and 1 blocks
sage: designs.balanced_incomplete_block_design(1,10)
Incidence structure with 1 points and 0 blocks
Existence of BIBD with \(k=3,4,5\):
sage: [v for v in xrange(50) if designs.balanced_incomplete_block_design(v,3,existence=True)]
[1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, 49]
sage: [v for v in xrange(100) if designs.balanced_incomplete_block_design(v,4,existence=True)]
[1, 4, 13, 16, 25, 28, 37, 40, 49, 52, 61, 64, 73, 76, 85, 88, 97]
sage: [v for v in xrange(150) if designs.balanced_incomplete_block_design(v,5,existence=True)]
[1, 5, 21, 25, 41, 45, 61, 65, 81, 85, 101, 105, 121, 125, 141, 145]
For \(k > 5\) there are currently very few constructions:
sage: [v for v in xrange(150) if designs.balanced_incomplete_block_design(v,6,existence=True) is True]
[1, 6, 31, 91]
sage: [v for v in xrange(150) if designs.balanced_incomplete_block_design(v,6,existence=True) is Unknown]
[51, 61, 66, 76, 81, 96, 106, 111, 121, 126, 136, 141]
But we know some inexistence results:
sage: designs.balanced_incomplete_block_design(21,6,existence=True)
False
Return 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.is_t_design(return_parameters=True)
(True, (2, 9, 3, 1))
An exception is raised for invalid values of n
sage: designs.steiner_triple_system(10)
Traceback (most recent call last):
...
EmptySetError: 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 |
Return 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 balanced_incomplete_block_design(). 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
TESTS:
Check that the \((25,4)\) and \((37,4)\)-difference family are available:
sage: assert designs.difference_family(25,4,existence=True)
sage: _ = designs.difference_family(25,4)
sage: assert designs.difference_family(37,4,existence=True)
sage: _ = designs.difference_family(37,4)
Return a \((v,5,1)\)-BIBD.
This method follows the constuction from [ClaytonSmith].
INPUT:
See also
EXAMPLES:
sage: from sage.combinat.designs.bibd import v_5_1_BIBD
sage: i = 0
sage: while i<200:
....: i += 20
....: _ = v_5_1_BIBD(i+1)
....: _ = v_5_1_BIBD(i+5)
TESTS:
Check that the needed difference families are there:
sage: for v in [21,41,61,81,141,161,281]:
....: assert designs.difference_family(v,5,existence=True)
....: _ = designs.difference_family(v,5)