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 -BIBD when one exists for all
. The following functions are available:
balanced_incomplete_block_design() | Return a BIBD of parameters ![]() |
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 ![]() ![]() ![]() |
PBD_from_TD() | Return a ![]() ![]() ![]() |
steiner_triple_system() | Return a Steiner Triple System. |
v_5_1_BIBD() | Return a ![]() |
v_4_1_BIBD() | Return a ![]() |
PBD_4_5_8_9_12() | Return a ![]() ![]() |
BIBD_5q_5_for_q_prime_power() | Return a ![]() ![]() |
Construction of BIBD when
Decompositions of into
(i.e.
-BIBD) are built following
Douglas Stinson’s construction as presented in [Stinson2004] page 167. It is
based upon the construction of
-PBD (see the doc of
PBD_4_5_8_9_12()), knowing that a
-PBD on
points
can always be transformed into a
-BIBD, which covers all
possible cases of
-BIBD.
Construction of BIBD when
Decompositions of into
(i.e.
-BIBD) are built following
Clayton Smith’s construction [ClaytonSmith].
[ClaytonSmith] | (1, 2, 3, 4) On the existence of ![]() |
Return a -BIBD with
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 -BIBD from a
-PBD where
.
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 is_pairwise_balanced_design
sage: PBD = PBD_4_5_8_9_12(17)
sage: bibd = is_pairwise_balanced_design(BIBD_from_PBD(PBD,52,4),52,[4])
Return a BIBD through TD-based constructions.
INPUT:
v,k (integers) – computes a -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 and a
-BIBD then there exists a
-BIBD.
The BIBD is obtained from all blocks of the , and from the blocks of
the
-BIBDs defined over the
groups of the
.
If there exists a and a
-BIBD then there exists a
-BIBD.
The BIBD is obtained from all blocks of the , and from the blocks of
the
-BIBDs defined over the sets
where the
are the groups of the TD.
If there exists a and a
-BIBD then there exists a
-BIBD.
The BIBD is obtained from all blocks of the , and from the blocks of
the
-BIBDs defined over the sets
where the
are the groups of the TD. By making sure that
all copies of the
-BIBD contain the block
, 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 be a group. A
-difference family is a family
of
-subsets of
such that for each element of
there exists exactly
pairs of elements
,
and
belonging to the same block, such that
(or
x y^{-1} = g` in multiplicative notation).
If is a
-difference family then
its set of translates
is a
-BIBD where
is the cardinality of
.
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]]
Bases: sage.combinat.designs.bibd.PairwiseBalancedDesign
” Balanced Incomplete Block Design (BIBD)
INPUT:
EXAMPLES:
sage: b=designs.balanced_incomplete_block_design(9,3); b
(9,3,1)-Balanced Incomplete Block Design
Return a -PBD on
elements.
A -PBD exists if and only if
. 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 -PBD if
and a
-PBD otherwise.
This is theorem 23 from [ClaytonSmith]. The PBD is obtained from the blocks
a truncated , to which are added the blocks corresponding to the
groups of the TD. When
, a
is used instead.
INPUT:
EXAMPLES:
sage: from sage.combinat.designs.bibd import PBD_from_TD
sage: from sage.combinat.designs.bibd import is_pairwise_balanced_design
sage: PBD = PBD_from_TD(2,2,1); PBD
[[0, 2, 4], [0, 3], [1, 2], [1, 3, 4], [0, 1], [2, 3]]
sage: is_pairwise_balanced_design(PBD,2*2+1,[2,3])
True
Bases: sage.combinat.designs.incidence_structures.GroupDivisibleDesign
Pairwise Balanced Design (PBD)
A Pairwise Balanced Design, or -PBD, is a collection
of blocks defined on a set
of size
, such that any block
pair of points
occurs in exactly
blocks of
. Besides, for every block
we must have
.
INPUT:
Return a BIBD of parameters .
A Balanced Incomplete Block Design of parameters is a collection
of
-subsets of
such that for any two
distinct elements
there is a unique element
such that
.
More general definitions sometimes involve a parameter, and we
assume here that
.
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)
(10,10,1)-Balanced Incomplete Block Design
sage: designs.balanced_incomplete_block_design(1,10)
(1,0,1)-Balanced Incomplete Block Design
Existence of BIBD with :
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 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, 81, 91, 121]
sage: [v for v in xrange(150) if designs.balanced_incomplete_block_design(v,6,existence=True) is Unknown]
[51, 61, 66, 76, 96, 106, 111, 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
is a family
of 3-sets such that for any
there exists exactly one set of
in which they are
both contained.
It can alternatively be thought of as a factorization of
the complete graph with triangles.
A Steiner Triple System of a -set exists if and only if
or
, in which case
one can be found through Bose’s and Skolem’s constructions,
respectively [AndHonk97].
INPUT:
EXAMPLE:
A Steiner Triple System on elements
sage: sts = designs.steiner_triple_system(9)
sage: sts
(9,3,1)-Balanced Incomplete Block Design
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 -BIBD.
A -BIBD is an edge-decomposition of the complete graph
into
copies of
. For more information, see
balanced_incomplete_block_design(). It exists if and only if
.
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 and
-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 -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)