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 [Hanani60], and the other one is a paper from Horan and Hurlbert which goes through all constructions [HH12].

It can be used through the designs object:

sage: designs.steiner_quadruple_system(8)
((0, 1, 2, 3), (0, 1, 6, 7), (0, 5, 2, 7), (0, 5, 6, 3), (4, 1, 2, 7),
(4, 1, 6, 3), (4, 5, 2, 3), (4, 5, 6, 7), (0, 1, 4, 5), (0, 2, 4, 6),
(0, 3, 4, 7), (1, 2, 5, 6), (1, 3, 5, 7), (2, 3, 6, 7))

REFERENCES:

[Hanani60](1, 2, 3, 4, 5) Haim Hanani, On quadruple systems, pages 145–157, vol. 12, Canadadian Journal of Mathematics, 1960 http://cms.math.ca/cjm/v12/cjm1960v12.0145-0157.pdf
[HH12]Victoria Horan and Glenn Hurlbert, Overlap Cycles for Steiner Quadruple Systems, 2012, http://arxiv.org/abs/1204.3215

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 [Hanani60]).

Functions

sage.combinat.designs.steiner_quadruple_systems.P(alpha, m)

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

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

EXAMPLE:

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

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

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

EXAMPLE:

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

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

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

EXAMPLE:

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)]]
sage.combinat.designs.steiner_quadruple_systems.four_n_minus_six(n, B)

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

INPUT:

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

EXAMPLES:

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

Tests if B is a Steiner Quadruple System on 0,...,n-1.

INPUT:

  • n (integer)
  • B – a list of quadruples.

EXAMPLES:

sage: from sage.combinat.designs.steiner_quadruple_systems import is_steiner_quadruple_system
sage: is_steiner_quadruple_system(8,designs.steiner_quadruple_system(8))
True
sage.combinat.designs.steiner_quadruple_systems.relabel_system(n, B)

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

INPUT:

  • n – an integer
  • B – a list of 4-uples on 0,...,n-1.

EXAMPLE:

sage: from sage.combinat.designs.steiner_quadruple_systems import relabel_system
sage: designs.steiner_quadruple_system(8)
((0, 1, 2, 3), (0, 1, 6, 7), (0, 5, 2, 7), (0, 5, 6, 3), (4, 1, 2, 7),
(4, 1, 6, 3), (4, 5, 2, 3), (4, 5, 6, 7), (0, 1, 4, 5), (0, 2, 4, 6),
(0, 3, 4, 7), (1, 2, 5, 6), (1, 3, 5, 7), (2, 3, 6, 7))
sage: relabel_system(8,designs.steiner_quadruple_system(8))
((4, 5, 6, 7), (0, 1, 4, 5), (1, 2, 4, 6), (0, 2, 4, 7), (1, 3, 5, 6),
(0, 3, 5, 7), (2, 3, 6, 7), (0, 1, 2, 3), (2, 3, 4, 5), (0, 3, 4, 6),
(1, 3, 4, 7), (0, 2, 5, 6), (1, 2, 5, 7), (0, 1, 6, 7))
sage.combinat.designs.steiner_quadruple_systems.steiner_quadruple_system(n, check=False)

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: designs.steiner_quadruple_system(4)
((0, 1, 2, 3),)
sage: designs.steiner_quadruple_system(8)
((0, 1, 2, 3), (0, 1, 6, 7), (0, 5, 2, 7), (0, 5, 6, 3), (4, 1, 2, 7),
(4, 1, 6, 3), (4, 5, 2, 3), (4, 5, 6, 7), (0, 1, 4, 5), (0, 2, 4, 6),
(0, 3, 4, 7), (1, 2, 5, 6), (1, 3, 5, 7), (2, 3, 6, 7))

TESTS:

sage: for n in xrange(4, 100):                                      # long time
....:     if (n%6) in [2,4]:                                        # long time
....:         sqs = designs.steiner_quadruple_system(n, check=True) # long time
sage.combinat.designs.steiner_quadruple_systems.three_n_minus_eight(n, B)

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

INPUT:

  • n – an integer such that n\equiv 2 \pmod{12}.
  • B – A Steiner Quadruple System on n points.

EXAMPLES:

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

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

INPUT:

  • n – an integer such that n\equiv 10\pmod{12}
  • B – A Steiner Quadruple System on n points.

EXAMPLES:

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

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

INPUT:

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

EXAMPLES:

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

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

INPUT:

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

EXAMPLES:

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

Return a Steiner Quadruple System on 2n points.

INPUT:

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

EXAMPLES:

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

Table Of Contents

Previous topic

Difference Matrices

Next topic

Database of small combinatorial designs

This Page