Page 58 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 58
2.4 Steiner triple systems
solving two problems posed by Heffter in 1896. An ordered 3-element subset {a ,b, c } of
the set {1, 2, . . . , (v − 1)/2} is called a difference triple if either a + b = c or a + b + c = v .
Heffter’s difference problems.
(1) Let v = 6k + 1. Is it possible to partition the set {1, 2, . . . , 3k } into k difference triples?
(2) Let v = 6k + 3. Is it possible to partition the set {1, 2, . . . , 3k + 1} \ {2k + 1} into k
difference triples?
In 1939, Peltesohn solved both Heffter’s difference problems in the affirmative except
for v = 9 (for which no solution exists).
Example 14. A solution to the second Heffer’s difference problem for v = 27 is:
{{1, 2, 3}, {4, 10, 13}, {5, 6, 11}, {7, 8, 12}}.
The base blocks corresponding to the difference triples are:
{0, 1, 3}, {0, 4, 14},{0, 5, 11},{0, 7, 15}.
Given a solution to the first Heffter’s difference problem, i.e. the collection of k or-
dered triples, each triple {a ,b, c } forms the base triple {0, a i , a i + bi } of a cyclic STS(6k +
1). Similarly, given a solution to the second Heffter’s difference problem, each triple
{a ,b, c } forms the base triple {0, a i , a i + bi } of a cyclic STS(6k + 3); one more base triple
(for short orbit) is {0, 2k + 1, 4k + 2}.
Solutions to both Heffter’s difference problems may be reduced to finding certain
integer sequences.
A Skolem sequence of order n is a sequence S = (s1, s2, . . . , s2n ) of 2n integers satisfy-
ing:
(1) for every k ∈ {1, 2, . . . , n } there exist exactly two elements si , s j ∈ S such that si = s j =
k,
(2) if si = s j = k with i < j , then j − i = k .
Example 15. A Skolem sequence of order 5:
S = (2, 4, 2, 3, 5, 4, 3, 1, 1, 5).
A Skolem sequence of order n exists if and only if n ≡ 0, 1 (mod 4). Given a Skolem
sequence S of order n , the collection of triples {{k , n +i , n + j } : si = s j = k , k = 1, 2, . . . , n }
is a solution to the first Heffter’s problem.
When n ≡ 2, 3 (mod 4) we use an extension of a Skolem sequence. A hooked Skolem
sequence of order n is a sequence HS = (s1, s2, . . . , s2n+1) of 2n + 1 integers satisfying:
(1) for every k ∈ {1, 2, . . . , n } there exist exactly two elements si , s j ∈ S such that si = s j =
k,
(2) if si = s j = k with i < j , then j − i = k ,
(3) s2n = 0.
Example 16. A hooked Skolem sequence of order 6:
S = (6, 3, 5, 2, 3, 2, 6, 5, 4, 1, 1, 0, 4).
A hooked Skolem sequence of order n exists if and only if n ≡ 2, 3 (mod 4). Given a
hooked Skolem sequence S of order n , the collection of triples {{k , n + i , n + j } : si = s j =
k , k = 1, 2, . . . , n } is a solution to the first Heffter’s problem.
Extensions of Skolem and hooked Skolem sequences, called split and split hooked
Skolem sequences, with zero on the position n + 1 and two zeros on the positions n + 1,
2n + 1, respectively, can be used is similar way in order to obtain solutions to the second
solving two problems posed by Heffter in 1896. An ordered 3-element subset {a ,b, c } of
the set {1, 2, . . . , (v − 1)/2} is called a difference triple if either a + b = c or a + b + c = v .
Heffter’s difference problems.
(1) Let v = 6k + 1. Is it possible to partition the set {1, 2, . . . , 3k } into k difference triples?
(2) Let v = 6k + 3. Is it possible to partition the set {1, 2, . . . , 3k + 1} \ {2k + 1} into k
difference triples?
In 1939, Peltesohn solved both Heffter’s difference problems in the affirmative except
for v = 9 (for which no solution exists).
Example 14. A solution to the second Heffer’s difference problem for v = 27 is:
{{1, 2, 3}, {4, 10, 13}, {5, 6, 11}, {7, 8, 12}}.
The base blocks corresponding to the difference triples are:
{0, 1, 3}, {0, 4, 14},{0, 5, 11},{0, 7, 15}.
Given a solution to the first Heffter’s difference problem, i.e. the collection of k or-
dered triples, each triple {a ,b, c } forms the base triple {0, a i , a i + bi } of a cyclic STS(6k +
1). Similarly, given a solution to the second Heffter’s difference problem, each triple
{a ,b, c } forms the base triple {0, a i , a i + bi } of a cyclic STS(6k + 3); one more base triple
(for short orbit) is {0, 2k + 1, 4k + 2}.
Solutions to both Heffter’s difference problems may be reduced to finding certain
integer sequences.
A Skolem sequence of order n is a sequence S = (s1, s2, . . . , s2n ) of 2n integers satisfy-
ing:
(1) for every k ∈ {1, 2, . . . , n } there exist exactly two elements si , s j ∈ S such that si = s j =
k,
(2) if si = s j = k with i < j , then j − i = k .
Example 15. A Skolem sequence of order 5:
S = (2, 4, 2, 3, 5, 4, 3, 1, 1, 5).
A Skolem sequence of order n exists if and only if n ≡ 0, 1 (mod 4). Given a Skolem
sequence S of order n , the collection of triples {{k , n +i , n + j } : si = s j = k , k = 1, 2, . . . , n }
is a solution to the first Heffter’s problem.
When n ≡ 2, 3 (mod 4) we use an extension of a Skolem sequence. A hooked Skolem
sequence of order n is a sequence HS = (s1, s2, . . . , s2n+1) of 2n + 1 integers satisfying:
(1) for every k ∈ {1, 2, . . . , n } there exist exactly two elements si , s j ∈ S such that si = s j =
k,
(2) if si = s j = k with i < j , then j − i = k ,
(3) s2n = 0.
Example 16. A hooked Skolem sequence of order 6:
S = (6, 3, 5, 2, 3, 2, 6, 5, 4, 1, 1, 0, 4).
A hooked Skolem sequence of order n exists if and only if n ≡ 2, 3 (mod 4). Given a
hooked Skolem sequence S of order n , the collection of triples {{k , n + i , n + j } : si = s j =
k , k = 1, 2, . . . , n } is a solution to the first Heffter’s problem.
Extensions of Skolem and hooked Skolem sequences, called split and split hooked
Skolem sequences, with zero on the position n + 1 and two zeros on the positions n + 1,
2n + 1, respectively, can be used is similar way in order to obtain solutions to the second
