Balanced Incomplete Block Designs (BIBD)

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

Functions

sage.combinat.designs.bibd.BIBD_5q_5_for_q_prime_power(q)

Return a \((5q,5,1)\)-BIBD with \(q\equiv 1\pmod 4\) a prime power.

See Theorem 24 [ClaytonSmith].

INPUT:

  • q (integer) – a prime power such that \(q\equiv 1\pmod 4\).

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
sage.combinat.designs.bibd.BIBD_from_PBD(PBD, v, k, check=True, base_cases={})

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:

  • 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.BIBD_from_TD(v, k, existence=False)

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!
sage.combinat.designs.bibd.BIBD_from_difference_family(G, D, check=True)

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
  • D - a difference family on G.
  • check - whether or not we check the output (default: True)

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

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:

  • v – an integer congruent to \(0\) or \(1\) modulo \(4\).
  • 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.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)
sage.combinat.designs.bibd.PBD_from_TD(k, t, u)

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:

  • k,t,u – integers such that \(0\leq u \leq t\).

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

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
sage.combinat.designs.bibd.steiner_triple_system(n)

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:

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

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.

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

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

Return a \((v,5,1)\)-BIBD.

This method follows the constuction from [ClaytonSmith].

INPUT:

  • v (integer)

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)

Table Of Contents

Previous topic

Block designs

Next topic

Mutually Orthogonal Latin Squares (MOLS)

This Page