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)[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

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]

Python

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

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]

Python

>>> 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 – integer
existence – boolean (default: False); 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

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

Python

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