Resolvable Balanced Incomplete Block Design (RBIBD)#
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.
Return a resolvable BIBD of parameters \(v,k\). |
|
Return a Kirkman Triple System on \(v\) points. |
|
Return a \((v,4,1)\)-RBIBD |
|
Return a \((v,\{4,7\})\)-PBD |
|
Return a \((3v+1,\{4,7\})\)-PBD from a \((v,\{4,5,7\},\NN-\{3,6,10\})\)-GDD. |
References:
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, doi:10.1016/0012-365X(91)90294-C
D. K. Ray-Chaudhuri, R. M. Wilson, Solution of Kirkman’s schoolgirl problem, Volume 19, Pages 187-203, Proceedings of Symposia in Pure Mathematics
Functions#
- sage.combinat.designs.resolvable_bibd.PBD_4_7(v, check=True, existence=False)#
Return a \((v,\{4,7\})\)-PBD
For all \(v\) such that \(n\equiv 1\pmod{3}\) and \(n\neq 10,19, 31\) there exists a \((v,\{4,7\})\)-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.
EXAMPLES:
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 [4, 7]
- sage.combinat.designs.resolvable_bibd.PBD_4_7_from_Y(gdd, check=True)#
Return a \((3v+1,\{4,7\})\)-PBD from a \((v,\{4,5,7\},\NN-\{3,6,10\})\)-GDD.
This implements Lemma IX.3.11 from [BJL99] (p.625). All points of the GDD are tripled, and a \(+\infty\) point is added to the design.
A group of size \(s\in Y=\NN-\{3,6,10\}\) becomes a set of size \(3s\). Adding \(\infty\) to it gives it size \(3s+1\), and this set is then replaced by a \((3s+1,\{4,7\})\)-PBD.
A block of size \(s\in\{4,5,7\}\) becomes a \((3s,\{4,7\},\{3\})\)-GDD.
This lemma is part of the existence proof of \((v,\{4,7\})\)-PBD as explained in IX.4.5 from [BJL99]).
INPUT:
gdd
– a \((v,\{4,5,7\},Y)\)-GDD where \(Y=\NN-\{3,6,10\}\).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.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 [4, 7]
- sage.combinat.designs.resolvable_bibd.kirkman_triple_system(v, existence=False)#
Return a Kirkman Triple System on \(v\) points.
A Kirkman Triple System \(KTS(v)\) is a resolvable Steiner Triple System. It exists if and only if \(v\equiv 3\pmod{6}\).
INPUT:
\(n\) (integer)
existence
(boolean;False
by default) – whether to build the \(KTS(n)\) or only answer whether it exists.
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: def to_name(r_s_t): ....: r, s, t = r_s_t ....: return ' ' + 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('\n'.join(rows)) 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
- sage.combinat.designs.resolvable_bibd.resolvable_balanced_incomplete_block_design(v, k, existence=False)#
Return a resolvable BIBD of parameters \(v,k\).
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 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.
EXAMPLES:
sage: KTS15 = designs.resolvable_balanced_incomplete_block_design(15,3); KTS15 (15,3,1)-Balanced Incomplete Block Design sage: KTS15.is_resolvable() True
- sage.combinat.designs.resolvable_bibd.v_4_1_rbibd(v, existence=False)#
Return a \((v,4,1)\)-RBIBD.
INPUT:
\(n\) (integer)
existence
(boolean;False
by default) – whether to build the design or only answer whether it exists.
Note
A resolvable \((v,4,1)\)-BIBD exists whenever \(1\equiv 4\pmod(12)\). This function, however, only implements a construction of \((v,4,1)\)-BIBD such that \(v=3q+1\equiv 1\pmod{3}\) where \(q\) is a prime power (see VII.7.5.a from [BJL99]).
EXAMPLES:
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))