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)[source]¶
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]
>>> from sage.all import * >>> from sage.combinat.designs.resolvable_bibd import PBD_4_7 >>> PBD_4_7(Integer(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)[source]¶
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 (default:True
); whether to check that output is correct before returning it. As this is expected to be useless, you may want to disable it whenever you want speed.
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)) # needs sage.schemes Pairwise Balanced Design on 169 points with sets of sizes in [4, 7]
>>> from sage.all import * >>> from sage.combinat.designs.resolvable_bibd import PBD_4_7_from_Y >>> PBD_4_7_from_Y(designs.transversal_design(Integer(7),Integer(8))) # needs sage.schemes Pairwise Balanced Design on 169 points with sets of sizes in [4, 7]
- sage.combinat.designs.resolvable_bibd.kirkman_triple_system(v, existence=False)[source]¶
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
– integerexistence
– boolean (default:False
); 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
>>> from sage.all import * >>> kts = designs.kirkman_triple_system(Integer(15)) >>> classes = kts.is_resolvable(Integer(1))[Integer(1)] >>> names = '0123456789abcde' >>> def to_name(r_s_t): ... r, s, t = r_s_t ... return ' ' + names[r] + names[s] + names[t] + ' ' >>> rows = [' '.join(('Day {}'.format(i) for i in range(Integer(1),Integer(8))))] >>> rows.extend(' '.join(map(to_name,row)) for row in zip(*classes)) >>> 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)[source]¶
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
– integersexistence
– 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) sage: KTS15 (15,3,1)-Balanced Incomplete Block Design sage: KTS15.is_resolvable() True
>>> from sage.all import * >>> KTS15 = designs.resolvable_balanced_incomplete_block_design(Integer(15),Integer(3)) >>> KTS15 (15,3,1)-Balanced Incomplete Block Design >>> KTS15.is_resolvable() True
- sage.combinat.designs.resolvable_bibd.v_4_1_rbibd(v, existence=False)[source]¶
Return a \((v,4,1)\)-RBIBD.
INPUT:
n
– integerexistence
– boolean (default:False
); 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))
>>> from sage.all import * >>> rBIBD = designs.resolvable_balanced_incomplete_block_design(Integer(28),Integer(4)) >>> rBIBD.is_resolvable() True >>> rBIBD.is_t_design(return_parameters=True) (True, (2, 28, 4, 1))