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 -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 ![]() |
Functions¶
-
sage.combinat.designs.bibd.
BIBD_5q_5_for_q_prime_power
(q)¶ Return a
-BIBD with
a prime power.
See Theorem 24 [ClaytonSmith].
INPUT:
q
(integer) – a prime power such that.
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
-BIBD from a
-PBD where
.
This is Theorem 7.20 from [Stinson2004].
INPUT:
v,k
– integers.PBD
– A PBD onpoints, such that for any block of
PBD
of sizethere must exist a
-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 toTrue
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 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])
-
sage.combinat.designs.bibd.
BIBD_from_TD
(v, k, existence=False)¶ 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 designUnknown
– meaning that Sage does not know how to build the design, but that the design may exist (seesage.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!
-
sage.combinat.designs.bibd.
BIBD_from_difference_family
(G, D, lambd=None, check=True)¶ Return the BIBD associated to the difference family
D
on the groupG
.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 groupD
- a difference family onG
(short blocks are allowed).lambd
- theparameter (optional, only used if
check
isTrue
)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]]
-
class
sage.combinat.designs.bibd.
BalancedIncompleteBlockDesign
(points, blocks, k=None, lambd=1, check=True, copy=True, **kwds)¶ Bases:
sage.combinat.designs.bibd.PairwiseBalancedDesign
” Balanced Incomplete Block Design (BIBD)
INPUT:
points
– the underlying set. Ifpoints
is an integer, then the set is considered to be
.
blocks
– collection of blocksk
(integer) – size of the blocks. Set toNone
(automatic guess) by default.lambd
(integer) – value of, set to
by default.
check
(boolean) – whether to check that the design is awith the right parameters.
copy
– (use with caution) if set toFalse
thenblocks
must be a list of lists of integers. The list will not be copied but will be modified in place (each block is sorted, and the whole list is sorted). Yourblocks
object will become the instance’s internal data.
EXAMPLES:
sage: b=designs.balanced_incomplete_block_design(9,3); b (9,3,1)-Balanced Incomplete Block Design
-
sage.combinat.designs.bibd.
PBD_4_5_8_9_12
(v, check=True)¶ Return a
-PBD on
elements.
A
-PBD exists if and only if
. The construction implemented here appears page 168 in [Stinson2004].
INPUT:
v
– an integer congruent toor
modulo
.
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 toTrue
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
-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:
k,t,u
– integers such that.
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
-
class
sage.combinat.designs.bibd.
PairwiseBalancedDesign
(points, blocks, K=None, lambd=1, check=True, copy=True, **kwds)¶ Bases:
sage.combinat.designs.group_divisible_designs.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:
points
– the underlying set. Ifpoints
is an integer, then the set is considered to be
.
blocks
– collection of blocksK
– list of integers of which the sizes of the blocks must be elements. Set toNone
(automatic guess) by default.lambd
(integer) – value of, set to
by default.
check
(boolean) – whether to check that the design is awith the right parameters.
copy
– (use with caution) if set toFalse
thenblocks
must be a list of lists of integers. The list will not be copied but will be modified in place (each block is sorted, and the whole list is sorted). Yourblocks
object will become the instance’s internal data.
-
sage.combinat.designs.bibd.
balanced_incomplete_block_design
(v, k, existence=False, use_LJCR=False)¶ 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 designUnknown
– meaning that Sage does not know how to build the design, but that the design may exist (seesage.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 (seebest_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, 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, 81, 96, 106, 111, 126, 136, 141]
Here are some constructions with
and
a prime power:
sage: designs.balanced_incomplete_block_design(169,7) (169,7,1)-Balanced Incomplete Block Design sage: designs.balanced_incomplete_block_design(617,8) (617,8,1)-Balanced Incomplete Block Design sage: designs.balanced_incomplete_block_design(433,9) (433,9,1)-Balanced Incomplete Block Design sage: designs.balanced_incomplete_block_design(1171,10) (1171,10,1)-Balanced Incomplete Block Design
And 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
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:
n
return a Steiner Triple System of
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
-
sage.combinat.designs.bibd.
v_4_1_BIBD
(v, check=True)¶ 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:
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 toTrue
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
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)
Check some larger
-BIBD (see trac ticket #17557):
sage: for v in range(400): # long time ....: if v%12 in [1,4]: # long time ....: _ = designs.balanced_incomplete_block_design(v,4) # long time
-
sage.combinat.designs.bibd.
v_5_1_BIBD
(v, check=True)¶ Return a
-BIBD.
This method follows the constuction from [ClaytonSmith].
INPUT:
v
(integer)
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)