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.

`resolvable_balanced_incomplete_block_design()`	Return a resolvable BIBD of parameters \(v,k\).
`kirkman_triple_system()`	Return a Kirkman Triple System on \(v\) points.
`v_4_1_rbibd()`	Return a \((v,4,1)\)-RBIBD
`PBD_4_7()`	Return a \((v,\{4,7\})\)-PBD
`PBD_4_7_from_Y()`	Return a \((3v+1,\{4,7\})\)-PBD from a \((v,\{4,5,7\},\NN-\{3,6,10\})\)-GDD.

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, doi: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

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 to True 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

IncidenceStructure.is_resolvable()

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 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.