Steiner Quadruple Systems#

A Steiner Quadruple System on \(n\) points is a family \(SQS_n \subset \binom {[n]} 4\) of \(4\)-sets, such that any set \(S\subset [n]\) of size three is a subset of exactly one member of \(SQS_n\).

This module implements Haim Hanani’s constructive proof that a Steiner Quadruple System exists if and only if \(n\equiv 2,4 \pmod 6\). Hanani’s proof consists in 6 different constructions that build a large Steiner Quadruple System from a smaller one, and though it does not give a very clear understanding of why it works (to say the least)… it does !

The constructions have been implemented while reading two papers simultaneously, for one of them sometimes provides the informations that the other one does not. The first one is Haim Hanani’s original paper [Han1960], and the other one is a paper from Horan and Hurlbert which goes through all constructions [HH2012].

It can be used through the designs object:

Sage

sage: designs.steiner_quadruple_system(8)
Incidence structure with 8 points and 14 blocks

Python

>>> from sage.all import *
>>> designs.steiner_quadruple_system(Integer(8))
Incidence structure with 8 points and 14 blocks

AUTHORS:

Nathann Cohen (May 2013, while listening to “Le Blues Du Pauvre Delahaye”)

Index#

This module’s main function is the following:

steiner_quadruple_system()

Return a Steiner Quadruple System on \(n\) points

This function redistributes its work among 6 constructions:

Construction \(1\)	`two_n()`	Return a Steiner Quadruple System on \(2n\) points
Construction \(2\)	`three_n_minus_two()`	Return a Steiner Quadruple System on \(3n-2\) points
Construction \(3\)	`three_n_minus_eight()`	Return a Steiner Quadruple System on \(3n-8\) points
Construction \(4\)	`three_n_minus_four()`	Return a Steiner Quadruple System on \(3n-4\) points
Construction \(5\)	`four_n_minus_six()`	Return a Steiner Quadruple System on \(4n-6\) points
Construction \(6\)	`twelve_n_minus_ten()`	Return a Steiner Quadruple System on \(12n-10\) points

It also defines two specific Steiner Quadruple Systems that the constructions require, i.e. \(SQS_{14}\) and \(SQS_{38}\) as well as the systems of pairs \(P_{\alpha}(m)\) and \(\overline P_{\alpha}(m)\) (see [Han1960]).

Functions#

sage.combinat.designs.steiner_quadruple_systems.P(alpha, m)[source]#

Return the collection of pairs \(P_{\alpha}(m)\)

For more information on this system, see [Han1960].

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import P
sage: P(3,4)
[(0, 5), (2, 7), (4, 1), (6, 3)]

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import P
>>> P(Integer(3),Integer(4))
[(0, 5), (2, 7), (4, 1), (6, 3)]

sage.combinat.designs.steiner_quadruple_systems.barP(eps, m)[source]#

Return the collection of pairs \(\overline P_{\alpha}(m)\)

For more information on this system, see [Han1960].

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import barP
sage: barP(3,4)
[(0, 4), (3, 5), (1, 2)]

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import barP
>>> barP(Integer(3),Integer(4))
[(0, 4), (3, 5), (1, 2)]

sage.combinat.designs.steiner_quadruple_systems.barP_system()[source]#

Return the 1-factorization of \(K_{2m}\) \(\overline P(m)\)

For more information on this system, see [Han1960].

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import barP_system
sage: barP_system(3)
[[(4, 3), (2, 5)],
[(0, 5), (4, 1)],
[(0, 2), (1, 3)],
[(1, 5), (4, 2), (0, 3)],
[(0, 4), (3, 5), (1, 2)],
[(0, 1), (2, 3), (4, 5)]]

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import barP_system
>>> barP_system(Integer(3))
[[(4, 3), (2, 5)],
[(0, 5), (4, 1)],
[(0, 2), (1, 3)],
[(1, 5), (4, 2), (0, 3)],
[(0, 4), (3, 5), (1, 2)],
[(0, 1), (2, 3), (4, 5)]]

sage.combinat.designs.steiner_quadruple_systems.four_n_minus_six(B)[source]#

Return a Steiner Quadruple System on \(4n-6\) points.

INPUT:

B – A Steiner Quadruple System on \(n\) points.

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import four_n_minus_six
sage: for n in range(4, 20):
....:     if (n%6) in [2,4]:
....:         sqs = designs.steiner_quadruple_system(n)
....:         if not four_n_minus_six(sqs).is_t_design(3,4*n-6,4,1):
....:             print("Something is wrong !")

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import four_n_minus_six
>>> for n in range(Integer(4), Integer(20)):
...     if (n%Integer(6)) in [Integer(2),Integer(4)]:
...         sqs = designs.steiner_quadruple_system(n)
...         if not four_n_minus_six(sqs).is_t_design(Integer(3),Integer(4)*n-Integer(6),Integer(4),Integer(1)):
...             print("Something is wrong !")

sage.combinat.designs.steiner_quadruple_systems.relabel_system(B)[source]#

Relabels the set so that \(\{n-4, n-3, n-2, n-1\}\) is in \(B\).

INPUT:

B – a list of 4-uples on \(0,...,n-1\).

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import relabel_system
sage: SQS8 = designs.steiner_quadruple_system(8)
sage: relabel_system(SQS8)
Incidence structure with 8 points and 14 blocks

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import relabel_system
>>> SQS8 = designs.steiner_quadruple_system(Integer(8))
>>> relabel_system(SQS8)
Incidence structure with 8 points and 14 blocks

sage.combinat.designs.steiner_quadruple_systems.steiner_quadruple_system(check=False)[source]#

Return a Steiner Quadruple System on \(n\) points.

INPUT:

n – an integer such that \(n\equiv 2,4\pmod 6\)
check (boolean) – whether to check that the system is a Steiner Quadruple System before returning it (\(False\) by default)

EXAMPLES:

Sage

sage: sqs4 = designs.steiner_quadruple_system(4)
sage: sqs4
Incidence structure with 4 points and 1 blocks
sage: sqs4.is_t_design(3,4,4,1)
True

sage: sqs8 = designs.steiner_quadruple_system(8)
sage: sqs8
Incidence structure with 8 points and 14 blocks
sage: sqs8.is_t_design(3,8,4,1)
True

Python

>>> from sage.all import *
>>> sqs4 = designs.steiner_quadruple_system(Integer(4))
>>> sqs4
Incidence structure with 4 points and 1 blocks
>>> sqs4.is_t_design(Integer(3),Integer(4),Integer(4),Integer(1))
True

>>> sqs8 = designs.steiner_quadruple_system(Integer(8))
>>> sqs8
Incidence structure with 8 points and 14 blocks
>>> sqs8.is_t_design(Integer(3),Integer(8),Integer(4),Integer(1))
True

sage.combinat.designs.steiner_quadruple_systems.three_n_minus_eight(B)[source]#

Return a Steiner Quadruple System on \(3n-8\) points.

INPUT:

B – A Steiner Quadruple System on \(n\) points.

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_eight
sage: for n in range(4, 30):
....:     if (n%12) == 2:
....:         sqs = designs.steiner_quadruple_system(n)
....:         if not three_n_minus_eight(sqs).is_t_design(3,3*n-8,4,1):
....:             print("Something is wrong !")

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_eight
>>> for n in range(Integer(4), Integer(30)):
...     if (n%Integer(12)) == Integer(2):
...         sqs = designs.steiner_quadruple_system(n)
...         if not three_n_minus_eight(sqs).is_t_design(Integer(3),Integer(3)*n-Integer(8),Integer(4),Integer(1)):
...             print("Something is wrong !")

sage.combinat.designs.steiner_quadruple_systems.three_n_minus_four(B)[source]#

Return a Steiner Quadruple System on \(3n-4\) points.

INPUT:

B – A Steiner Quadruple System on \(n\) points where \(n\equiv 10\pmod{12}\).

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_four
sage: for n in range(4, 30):
....:     if n%12 == 10:
....:         sqs = designs.steiner_quadruple_system(n)
....:         if not three_n_minus_four(sqs).is_t_design(3,3*n-4,4,1):
....:             print("Something is wrong !")

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_four
>>> for n in range(Integer(4), Integer(30)):
...     if n%Integer(12) == Integer(10):
...         sqs = designs.steiner_quadruple_system(n)
...         if not three_n_minus_four(sqs).is_t_design(Integer(3),Integer(3)*n-Integer(4),Integer(4),Integer(1)):
...             print("Something is wrong !")

sage.combinat.designs.steiner_quadruple_systems.three_n_minus_two(B)[source]#

Return a Steiner Quadruple System on \(3n-2\) points.

INPUT:

B – A Steiner Quadruple System on \(n\) points.

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_two
sage: for n in range(4, 30):
....:     if (n%6) in [2,4]:
....:         sqs = designs.steiner_quadruple_system(n)
....:         if not three_n_minus_two(sqs).is_t_design(3,3*n-2,4,1):
....:             print("Something is wrong !")

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_two
>>> for n in range(Integer(4), Integer(30)):
...     if (n%Integer(6)) in [Integer(2),Integer(4)]:
...         sqs = designs.steiner_quadruple_system(n)
...         if not three_n_minus_two(sqs).is_t_design(Integer(3),Integer(3)*n-Integer(2),Integer(4),Integer(1)):
...             print("Something is wrong !")

sage.combinat.designs.steiner_quadruple_systems.twelve_n_minus_ten(B)[source]#

Return a Steiner Quadruple System on \(12n-6\) points.

INPUT:

B – A Steiner Quadruple System on \(n\) points.

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import twelve_n_minus_ten
sage: for n in range(4, 15):
....:     if (n%6) in [2,4]:
....:         sqs = designs.steiner_quadruple_system(n)
....:         if not twelve_n_minus_ten(sqs).is_t_design(3,12*n-10,4,1):
....:             print("Something is wrong !")

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import twelve_n_minus_ten
>>> for n in range(Integer(4), Integer(15)):
...     if (n%Integer(6)) in [Integer(2),Integer(4)]:
...         sqs = designs.steiner_quadruple_system(n)
...         if not twelve_n_minus_ten(sqs).is_t_design(Integer(3),Integer(12)*n-Integer(10),Integer(4),Integer(1)):
...             print("Something is wrong !")

sage.combinat.designs.steiner_quadruple_systems.two_n(B)[source]#

Return a Steiner Quadruple System on \(2n\) points.

INPUT:

B – A Steiner Quadruple System on \(n\) points.

EXAMPLES:

Sage

sage: from sage.combinat.designs.steiner_quadruple_systems import two_n
sage: for n in range(4, 30):
....:     if (n%6) in [2,4]:
....:         sqs = designs.steiner_quadruple_system(n)
....:         if not two_n(sqs).is_t_design(3,2*n,4,1):
....:             print("Something is wrong !")

Python

>>> from sage.all import *
>>> from sage.combinat.designs.steiner_quadruple_systems import two_n
>>> for n in range(Integer(4), Integer(30)):
...     if (n%Integer(6)) in [Integer(2),Integer(4)]:
...         sqs = designs.steiner_quadruple_system(n)
...         if not two_n(sqs).is_t_design(Integer(3),Integer(2)*n,Integer(4),Integer(1)):
...             print("Something is wrong !")