Steiner Quadruple Systems¶
A Steiner Quadruple System on points is a family
of
-sets, such that any set
of size three is a subset of
exactly one member of
.
This module implements Haim Hanani’s constructive proof that a Steiner Quadruple
System exists if and only if . 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)
Incidence structure with 8 points and 14 blocks
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 ![]() |
This function redistributes its work among 6 constructions :
Construction ![]() |
two_n() |
Return a Steiner Quadruple System on ![]() |
Construction ![]() |
three_n_minus_two() |
Return a Steiner Quadruple System on ![]() |
Construction ![]() |
three_n_minus_eight() |
Return a Steiner Quadruple System on ![]() |
Construction ![]() |
three_n_minus_four() |
Return a Steiner Quadruple System on ![]() |
Construction ![]() |
four_n_minus_six() |
Return a Steiner Quadruple System on ![]() |
Construction ![]() |
twelve_n_minus_ten() |
Return a Steiner Quadruple System on ![]() |
It also defines two specific Steiner Quadruple Systems that the constructions
require, i.e. and
as well as the systems of pairs
and
(see [Hanani60]).
Functions¶
-
sage.combinat.designs.steiner_quadruple_systems.
P
(alpha, m)¶ Return the collection of pairs
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
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
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
(B)¶ Return a Steiner Quadruple System on
points.
INPUT:
B
– A Steiner Quadruple System onpoints.
EXAMPLES:
sage: from sage.combinat.designs.steiner_quadruple_systems import four_n_minus_six sage: for n in xrange(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 !"
-
sage.combinat.designs.steiner_quadruple_systems.
relabel_system
(B)¶ Relabels the set so that
is in
.
INPUT:
B
– a list of 4-uples on.
EXAMPLE:
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
-
sage.combinat.designs.steiner_quadruple_systems.
steiner_quadruple_system
(n, check=False)¶ Return a Steiner Quadruple System on
points.
INPUT:
n
– an integer such thatcheck
(boolean) – whether to check that the system is a Steiner Quadruple System before returning it (by default)
EXAMPLES:
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
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
(B)¶ Return a Steiner Quadruple System on
points.
INPUT:
B
– A Steiner Quadruple System onpoints.
EXAMPLES:
sage: from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_eight sage: for n in xrange(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 !"
-
sage.combinat.designs.steiner_quadruple_systems.
three_n_minus_four
(B)¶ Return a Steiner Quadruple System on
points.
INPUT:
B
– A Steiner Quadruple System onpoints where
.
EXAMPLES:
sage: from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_four sage: for n in xrange(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 !"
-
sage.combinat.designs.steiner_quadruple_systems.
three_n_minus_two
(B)¶ Return a Steiner Quadruple System on
points.
INPUT:
B
– A Steiner Quadruple System onpoints.
EXAMPLES:
sage: from sage.combinat.designs.steiner_quadruple_systems import three_n_minus_two sage: for n in xrange(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 !"
-
sage.combinat.designs.steiner_quadruple_systems.
twelve_n_minus_ten
(B)¶ Return a Steiner Quadruple System on
points.
INPUT:
B
– A Steiner Quadruple System onpoints.
EXAMPLES:
sage: from sage.combinat.designs.steiner_quadruple_systems import twelve_n_minus_ten sage: for n in xrange(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 !"
-
sage.combinat.designs.steiner_quadruple_systems.
two_n
(B)¶ Return a Steiner Quadruple System on
points.
INPUT:
B
– A Steiner Quadruple System onpoints.
EXAMPLES:
sage: from sage.combinat.designs.steiner_quadruple_systems import two_n sage: for n in xrange(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 !"