Balanced Incomplete Block Designs (BIBD)

This module implements two constructions of Balanced Incomplete Block Designs:

  • Steiner Triple Systems, i.e. \((v,3,1)\)-BIBD.
  • \(K_4\)-decompositions of \(K_v\), i.e. \((v,4,1)\)-BIBD.

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

\(K_4\)-decompositions of \(K_v\)

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.

Functions

sage.combinat.designs.bibd.BIBD_from_PBD(PBD, v, k, check=True, base_cases={})

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:

  • v,k – integers.
  • PBD – A PBD on \(r=(v-1)/(k-1)\) points, such that for any block of PBD of size \(s\) there must exist a \(((k-1)s+1,k,1)\)-BIBD.
  • check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.
  • base_cases – caching system, for internal use.

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])
sage.combinat.designs.bibd.BalancedIncompleteBlockDesign(v, k, use_LJCR=False)

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:

  • v,k (integers)
  • 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 \((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)
sage.combinat.designs.bibd.PBD_4_5_8_9_12(v, check=True)

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:

  • v (integer)
  • check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

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],
...
sage.combinat.designs.bibd.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 [AndHonk97].

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(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
sage.combinat.designs.bibd.v_4_1_BIBD(v, check=True)

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.

INPUT:

  • v (integer) – number of points.
  • check (boolean) – whether to check that output is correct before returning it. As this is expected to be useless (but we are cautious guys), you may want to disable it whenever you want speed. Set to True by default.

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

Table Of Contents

Previous topic

Block designs.

Next topic

Steiner Quadruple Systems

This Page