This module contains everything related to resolvable Balanced Incomplete Block Designs. The constructions implemented here can be obtained through the designs.<tab> object:
designs.resolvable_balanced_incomplete_block_design(15,3)
For Balanced Incomplete Block Design (BIBD) see the module bibd. A BIBD is said to be resolvable if its blocks can be partitionned into parallel classes, i.e. partitions of its ground set.
The main function of this module is resolvable_balanced_incomplete_block_design(), which calls all others.
resolvable_balanced_incomplete_block_design() | Return a resolvable BIBD of parameters ![]() |
kirkman_triple_system() | Return a Kirkman Triple System on ![]() |
v_4_1_rbibd() | Return a ![]() |
PBD_4_7() | Return a ![]() |
PBD_4_7_from_Y() | Return a ![]() ![]() |
References:
[Stinson91] | D.R. Stinson, A survey of Kirkman triple systems and related designs, Volume 92, Issues 1-3, 17 November 1991, Pages 371-393, Discrete Mathematics, http://dx.doi.org/10.1016/0012-365X(91)90294-C. |
[RCW71] | D. K. Ray-Chaudhuri, R. M. Wilson, Solution of Kirkman’s schoolgirl problem, Volume 19, Pages 187-203, Proceedings of Symposia in Pure Mathematics |
[BJL99] | (1, 2, 3, 4) T. Beth, D. Jungnickel, H. Lenz, Design Theory 2ed. Cambridge University Press 1999 |
Return a -PBD
For all such that
and
there exists
a
-PBD. This is proved in Proposition IX.4.5 from [BJL99],
which this method implements.
This construction of PBD is used by the construction of Kirkman Triple Systems.
EXAMPLE:
sage: from sage.combinat.designs.resolvable_bibd import PBD_4_7
sage: PBD_4_7(22)
Pairwise Balanced Design on 22 points with sets of sizes in set([4, 7])
TESTS:
All values :
sage: for i in range(1,300,3):
....: if i not in [10,19,31]:
....: assert PBD_4_7(i,existence=True)
....: _ = PBD_4_7(i,check=True)
Return a -PBD from a
-GDD.
This implements Lemma IX.3.11 from [BJL99] (p.625). All points of the GDD
are tripled, and a point is added to the design.
This lemma is part of the existence proof of -PBD as explained
in IX.4.5 from [BJL99]).
INPUT:
EXAMPLE:
sage: from sage.combinat.designs.resolvable_bibd import PBD_4_7_from_Y
sage: PBD_4_7_from_Y(designs.transversal_design(7,8))
Pairwise Balanced Design on 169 points with sets of sizes in set([4, 7])
TESTS:
sage: PBD_4_7_from_Y(designs.balanced_incomplete_block_design(10,10))
Traceback (most recent call last):
...
ValueError: The GDD should only contain blocks of size {4,5,7} but there are other: set([10])
sage: PBD_4_7_from_Y(designs.transversal_design(4,3))
Traceback (most recent call last):
...
RuntimeError: A group has size 3 but I do not know how to build a (10,[4,7])-PBD
Return a Kirkman Triple System on points.
A Kirkman Triple System is a resolvable Steiner Triple System. It
exists if and only if
.
INPUT:
See also
EXAMPLES:
A solution to Kirkmman’s original problem:
sage: kts = designs.kirkman_triple_system(15)
sage: classes = kts.is_resolvable(1)[1]
sage: names = '0123456789abcde'
sage: to_name = lambda (r,s,t): ' '+names[r]+names[s]+names[t]+' '
sage: rows = [join(('Day {}'.format(i) for i in range(1,8)), ' ')]
sage: rows.extend(join(map(to_name,row), ' ') for row in zip(*classes))
sage: print join(rows,'\n')
Day 1 Day 2 Day 3 Day 4 Day 5 Day 6 Day 7
07e 18e 29e 3ae 4be 5ce 6de
139 24a 35b 46c 05d 167 028
26b 03c 14d 257 368 049 15a
458 569 06a 01b 12c 23d 347
acd 7bd 78c 89d 79a 8ab 9bc
TESTS:
sage: for i in range(3,300,6):
....: _ = designs.kirkman_triple_system(i)
Return a resolvable BIBD of parameters .
A BIBD is said to be resolvable if its blocks can be partitionned into parallel classes, i.e. partitions of the ground set.
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.
EXAMPLE:
sage: KTS15 = designs.resolvable_balanced_incomplete_block_design(15,3); KTS15
(15,3,1)-Balanced Incomplete Block Design
sage: KTS15.is_resolvable()
True
TESTS:
sage: for v in range(40):
....: for k in range(v):
....: if designs.resolvable_balanced_incomplete_block_design(v,k,existence=True):
....: _ = designs.resolvable_balanced_incomplete_block_design(v,k)
Return a -RBIBD.
INPUT:
Note
A resolvable -BIBD exists whenever
. This
function, however, only implements a construction of
-BIBD such
that
where
is a prime power (see VII.7.5.a
from [BJL99]).
EXAMPLE:
sage: rBIBD = designs.resolvable_balanced_incomplete_block_design(28,4)
sage: rBIBD.is_resolvable()
True
sage: rBIBD.is_t_design(return_parameters=True)
(True, (2, 28, 4, 1))
TESTS:
sage: for q in prime_powers(2,30):
....: if (3*q+1)%12 == 4:
....: _ = designs.resolvable_balanced_incomplete_block_design(3*q+1,4) # indirect doctest