Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 2 (2009) 207–215
A partial generalization of
the Livingstone–Wagner Theorem
Yasuhiro Nakashima
Graduate School of Information Sciences
Tohoku University, Japan
Received 22 October 2008, accepted 1 November 2009, published online 5 November 2009
Abstract
For a transitive permutation group G on a finite set Ω, the Livingstone–Wagner The-
orem states that if G is k-homogeneous and 2 ≤ k ≤ |Ω|2 , then G is (k − 1)-transitive.
We conjecture that the number of G-orbits on k-subsets of Ω is greater than or equal to
the number of G-orbits on ordered (k − 1)-tuples of Ω, if |Ω| is sufficiently large. For the
simplest case k = 3, we verify this conjecture by establishing a result on edge-colorings of
complete digraphs.
Keywords: Groups, transitivity, orbits.
Math. Subj. Class.: 20B20, 20B35
1 Introduction
LetG be a permutation group on a finite set Ω. Denote by Ω/G the set ofG-orbits on Ω. Let
Ω(k) and Ω[l] denote the family of all k-subsets of Ω and the family of all l-tuples of distinct
elements of Ω, respectively. The group G is said to be k-homogeneous or l-transitive if G
acts transitively on Ω(k) or Ω[l] respectively.
Livingstone and Wagner [3, Theorem 1,2] showed that for any group G acting on Ω,
and for any k with 2 ≤ k ≤ |Ω|2 ,
(1) the inequality |Ω(k)/G| ≥ |Ω(k−1)/G| holds. In particular, k-homogeneity implies
also (k − 1)-homogeneity,
(2) if G is k-homogeneous, then G is (k − 1)-transitive, and
(3) for k ≥ 5, if G is k-homogeneous, then G is k-transitive.
E-mail address: ysnakashima@gmail.com (Yasuhiro Nakashima)
Copyright c© 2009 DMFA Slovenije
208 Ars Math. Contemp. 2 (2009) 207–215
Martin and Sagan [4, Theorem 2] generalized (1) by introducing the concept of λ-
transitivity as follows. Let Sλ be the set of all partitions of Ω of shape λ. If a permutation
group G on Ω acts transitively on Sλ, then G is said to be λ-transitive. Let E denote
the dominance order (see [5, Definition 2.2.2]) on the set of partitions of |Ω|. Martin and
Sagan proved that λ E µ implies |Sλ/G| ≥ |Sµ/G|. In particular, λ-transitivity im-
plies µ-transitivity. Since S(|Ω|−k,k) ∼= Ω(k) and S(|Ω|−k+1,k−1) ∼= Ω(k−1) as G-sets, the
Livingstone–Wagner Theorem (1) follows from the Martin–Sagan Theorem. Analogously,
(2) will follow if we could prove |Ω(k)/G| ≥ |Ω[k−1]/G|. Since |Ω(k)| ≥ |Ω[k−1]| holds
when |Ω| ≥ k! + k − 1, one may expect the inequality |Ω(k)/G| ≥ |Ω[k−1]/G| to be true
for |Ω| sufficiently large. Since S(|Ω|−k+1,1k−1) ∼= Ω[k−1] as G-sets, and the partitions
(|Ω| − k, k), (|Ω| − k + 1, 1k−1) are incomparable with respect to the dominance order,
Theorem 2 of [4] does not apply. For the simplest case k = 3, the inequality follows from
the following result of Cameron and Saxl [1], provided that |Ω[2]/G| ≥ 26.
Proposition 1.1 ([1]). Let G be a transitive permutation group on a set Ω with |Ω| > 2.
Then |Ω(3)/G| ≥
|Ω(2)/G|(|Ω(2)/G| − 1)
6
.
Indeed, since 2|Ω(2)/G| ≥ |Ω[2]/G|, Proposition 1.1 implies
|Ω(3)/G| ≥
|Ω[2]/G|(|Ω[2]/G| − 2)
24
≥ |Ω[2]/G|
provided that |Ω[2]/G| ≥ 26.
The purpose of this paper is to prove the inequality |Ω(3)/G| ≥ |Ω[2]/G| provided
that |Ω| ≥ 11, by counting certain configurations in a regular edge-coloring of a complete
digraph (the definition of which is given in the next section). Here we only note that every
transitive permutation groupG on Ω induces a regular edge-coloring (Ω, CG, φG,ΨG) with
CG = Ω[2]/G, and the number |Ω3| of equivalence classes is at most |Ω(3)/G|. We prove
in Section 5 that if (Ω, C, φ,Ψ) is a regular edge-coloring with |Ω| ≥ 11, then |Ω3| ≥ |C|.
As a corollary to this result, we obtain the following.
Theorem 1.2. For any transitive permutation group G on Ω with |Ω| ≥ 11, |Ω(3)/G| ≥
|Ω[2]/G| holds.
For some permutation groups of degree less than 11, Theorem 1.2 fails to hold. In fact,
C6, C3 oS2, C3 oS2, of degree 6, C7 of degree 7, C4 oS2 of degree 8, and C5 oS2 of degree
10 are all the counterexamples with degree greater than 5. We refer the reader to [2] for
unexplained notation in permutation group theory.
2 Regular edge-colorings
Let Ω, C be finite sets, and let φ : Ω[2] → C be a surjective mapping. We call (Ω, C, φ,Ψ) a
regular edge-coloring if
(R1) For each a ∈ C and each α ∈ Ω, there exists a positive integer δa such that
|{β ∈ Ω | φ(α, β) = a}| = δa.
(R2) There is a bijective mapping Ψ : C → C, which maps a color of an edge to that of its
opposite:
for all (α, β) ∈ Ω[2], (Ψ ◦ φ)(α, β) = φ(β, α).
Y. Nakashima: A partial generalization of the Livingstone–Wagner Theorem 209
Let G be a transitive permutation group on Ω. We obtain a regular edge-coloring in-
duced by G, denoted (Ω, CG, φG,ΨG), as follows. Let CG = Ω[2]/G, and define φG :
Ω[2] → CG by φG(α, β) = (α, β)G for (α, β) ∈ Ω[2], where (α, β)G denotes the G-orbit
of (α, β). Define ΨG by ΨG(φG(α, β)) = φG(β, α). Then (R1) holds by transitivity of G,
and clearly (R2) holds. Thus (Ω, CG, φG,ΨG) is a regular edge-coloring.
For the remainder of this section, we assume that a regular edge-coloring (Ω, C, φ,Ψ)
is given. For A,B ∈ Ω(3), we write A ∼ B if there exists a bijection π from A to B
such that φ(π(α), π(α′)) = φ(α, α′) for any distinct α, α′ ∈ A. Then ∼ is an equivalence
relation. Let [A] denote the equivalence class of A. For a, b, c ∈ C we define
[a, b, c] =
{
{α, β, γ} ∈ Ω(3) | φ(α, β) = a, φ(β, γ) = b, φ(γ, α) = c
}
.
For each A = {α, β, γ} ∈ Ω(3), there exist a, b, c ∈ C such that [A] = [a, b, c]. Conversely,
for any a, b, c ∈ C, we can see that [a, b, c] is an equivalence class unless it is empty. Let
Ω3 denote the set of equivalence classes with respect to∼. For a, b ∈ C, we define a family
of equivalence classes Ta,b by
Ta,b = {[a, b, x] | x ∈ C, [a, b, x] 6= ∅} ⊂ Ω3.
By (R1), Ta,b = ∅ if and only if b = Ψ(a) and δa = 1 for any a, b ∈ C, Tc,c 6= ∅ for any
c ∈ C with c 6= Ψ(c), and TΨ(d),d 6= ∅ for any d ∈ C with δd ≥ 2. For convenience, we
define Ua, Va for any a ∈ C by
Ua = TΨ(a),a, Va = Ta,a. (2.1)
3 Some lemmas
Let (Ω, C, φ,Ψ) be a regular edge-coloring. We first prove some useful lemmas.
Lemma 3.1. Let a, b, c, d, e ∈ C with [a, b, c] 6= ∅. Then [a, b, c] ∈ Td,e if and only if
{Ψ(d), e} ∈
{
{a,Ψ(c)}, {b,Ψ(a)}, {c,Ψ(b)}
}
.
Proof. By the definition, the assertion follows from
[a, b, c] ∈ Td,e
⇐⇒ there exists x ∈ C such that [a, b, c] = [d, e, x]
⇐⇒ (d, e) ∈ {(a, b), (b, c), (c, a), (Ψ(a),Ψ(c)), (Ψ(b),Ψ(a)), (Ψ(c),Ψ(b))}
⇐⇒ (Ψ(d), e) ∈ {(Ψ(a), b), (Ψ(b), c), (Ψ(c), a), (a,Ψ(c)), (b,Ψ(a)), (c,Ψ(b))}
⇐⇒ {Ψ(d), e} ∈
{
{a,Ψ(c)}, {b,Ψ(a)}, {c,Ψ(b)}
}
.
Lemma 3.2. Let a, b, c, d be in C with {a, b} 6= {c, d}. If {Ψ(a),Ψ(b)}∩{c, d} = ∅, then
TΨ(a),b ∩ TΨ(c),d = ∅.
Proof. Suppose TΨ(a),b ∩ TΨ(c),d 6= ∅. Then there exists x ∈ C such that [Ψ(a), b, x] ∈
TΨ(a),b, [Ψ(a), b, x] 6= ∅ and [Ψ(a), b, x] ∈ TΨ(c),d. Lemma 3.1 implies that
{c, d} ∈
{
{Ψ(a),Ψ(x)}, {b, a}, {x,Ψ(b)}
}
.
Thus {Ψ(a),Ψ(b)} ∩ {c, d} 6= ∅, as {a, b} 6= {c, d}.
210 Ars Math. Contemp. 2 (2009) 207–215
Lemma 3.3. Let a, b, c ∈ C with Ψ(a) = a and b /∈ {c,Ψ(c)}. Then Ta,b ∩ Ta,c =
{[a, b,Ψ(c)]} if [a, b,Ψ(c)] 6= ∅, and Ta,b ∩ Ta,c = ∅ otherwise.
Proof. If [a, b,Ψ(c)] 6= ∅, then [a, b,Ψ(c)] ∈ Ta,b ∩ Ta,c, as [a, b,Ψ(c)] = [a, c,Ψ(b)].
Suppose [a, b, x] ∈ Ta,b∩Ta,c, where x ∈ C. Lemma 3.1 implies that {a, c} ∈
{
{a,Ψ(x)},
{b, a}, {x,Ψ(b)}
}
. Since b /∈ {c,Ψ(c)}, either Ψ(x) = c or (a, c) = (Ψ(b), x) holds.
In the former case, we have [a, b, x] = [a, b,Ψ(c)]. In the latter case, we also have
[a, b, x] = [Ψ(b),Ψ(a),Ψ(x)] = [a, b,Ψ(c)]. Thus Ta,b ∩ Ta,c = {[a, b,Ψ(c)]} provided
that [a, b,Ψ(c)] 6= ∅, and Ta,b ∩ Ta,c = ∅ if [a, b,Ψ(c)] = ∅.
Lemma 3.4. Let {a, b}, {c, d} be distinct 2-sets of C and suppose Ψ(w) = w for each
w ∈ {a, b, c, d}. Then Te,e ∩ Ta,b ∩ Tc,d = Te,Ψ(e) ∩ Ta,b ∩ Tc,d = ∅ holds for any e ∈ C.
Proof. If e 6= Ψ(e), then we have {e,Ψ(e)} ∩ {a, b} = ∅, and the assertion follows from
Lemma 3.2. Hence we suppose that e = Ψ(e).
Assume Te,e ∩ Ta,b ∩ Tc,d 6= ∅. As Ta,b ∩ Tc,d 6= ∅, Lemma 3.2 implies that {a, b} ∩
{c, d} 6= ∅. Thus we may assume a = c, and so b 6= d, as {a, b} 6= {c, d}. Lemma 3.3
implies Ta,b ∩ Ta,d = {[a, b, d]}.
By Lemma 3.2, we can see that Te,e ∩ Ta,b 6= ∅ implies {e} ∩ {a, b} 6= ∅, and
that Te,e ∩ Ta,d 6= ∅ implies {e} ∩ {a, d} 6= ∅. Since b 6= d, we have a = e, and
[a, b, d] ∈ Ta,a. Lemma 3.1 implies {a} ∈
{
{a, d}, {b, a}, {d, b}
}
. Hence, either d = a or
b = a, a contradiction.
Lemma 3.5. Suppose a ∈ C, a 6= Ψ(a), and b, c, d, e ∈ C \ {a,Ψ(a)}. If [a, b, c] =
[a, d, e] 6= ∅, then b = d and c = e.
Proof. Since [a, b, c] = [a, d, e] ∈ Ta,d, Lemma 3.1 implies that
{Ψ(a), d} ∈
{
{a,Ψ(c)}, {b,Ψ(a)}, {c,Ψ(b)}
}
.
By assumption, we have {Ψ(a), d} = {b,Ψ(a)}, and b = d. Similarly, c = e is obtained.
For D ⊂ C, we define f(D) by f(D) = 2 + 2
∑
d∈D δd, where δd is defined as in (R1).
IfD = Ψ(D), then we define ∆(D) by ∆(D) = {[x, y, z] | x, y, z ∈ C\D, [x, y, z] 6= ∅}.
Lemma 3.6. Let D ⊂ C. If f(D) < |Ω|, then for any a ∈ C there exist b, c ∈ C \ D such
that [a, b,Ψ(c)] 6= ∅. Moreover, if D = Ψ(D), then ∆(D) 6= ∅.
Proof. Let α, β ∈ Ω with φ(α, β) = a. Then∣∣{ω ∈ Ω \ {α, β} | φ(α, ω) ∈ D or φ(β, ω) ∈ D}∣∣
≤
∣∣{ω ∈ Ω \ {α, β} | φ(α, ω) ∈ D}∣∣+ ∣∣{ω ∈ Ω \ {α, β} | φ(β, ω) ∈ D}∣∣
≤ 2
∑
d∈D
δd
< |Ω| − 2 = |Ω \ {α, β}|.
Thus there exists γ ∈ Ω \ {α, β} such that φ(α, γ) /∈ D and φ(β, γ) /∈ D. Setting
b = φ(β, γ) and c = φ(α, γ), we obtain {α, β, γ} ∈ [a, b,Ψ(c)] with b, c ∈ C \ D.
Suppose D = Ψ(D), and let x ∈ C \ D. By the first part of the lemma, there exist
y, z ∈ C \ D such that [x, y,Ψ(z)] 6= ∅. Since Ψ(D) = D, we have Ψ(z) /∈ D, and hence
[x, y,Ψ(z)] ∈ ∆(D).
Y. Nakashima: A partial generalization of the Livingstone–Wagner Theorem 211
4 Lower bounds of |Ω3|
This section is devoted to establishing some lower bounds for |Ω3|, which will be needed
later. As in the previous section, suppose that (Ω, C, φ,Ψ) is a regular edge-coloring. We
define subsets K,L,M,K1,K2,L1,L2 of C by
K = {a ∈ C | Ψ(a) 6= a}, L = {a ∈ C | Ψ(a) = a}, M = {a ∈ C | δa ≥ 2},
K1 = K \M, K2 = K ∩M, L1 = L \M, L2 = L ∩M,
(4.1)
and we define integers k, l,m by
k = |K|2 , l = |L|, m = |M|. (4.2)
Lemma 4.1. Let {a1, b1}, . . . , {as, bs} be distinct subsets of C with TΨ(ai),bi 6= ∅, for all
i. Let X =
⋃
1≤i≤s TΨ(ai),bi . Then |X| ≥ d
s
3e. In particular
|Ω3| ≥
⌈2m+ |C|(|C| − 1)
6
⌉
.
Proof. Since TΨ(ai),bi 6= ∅, we have
s ≤
∣∣{([x, y, z], j) | x, y, z ∈ C, 1 ≤ j ≤ s, [x, y, z] ∈ TΨ(aj),bj}∣∣
=
∑
[x,y,z]∈Ω3
∣∣{j | 1 ≤ j ≤ s, [x, y, z] ∈ TΨ(aj),bj}∣∣
=
∑
[x,y,z]∈X
∣∣{j | 1 ≤ j ≤ s, [x, y, z] ∈ TΨ(aj),bj}∣∣
≤
∑
[x,y,z]∈X
3 (by Lemma 3.1)
= 3|X|.
Since we can take m+ |C(2)| subsets {ai, bi} with TΨ(ai),bi 6= ∅, the second part follows.
Lemma 4.2. For any a ∈ K2, the inequality |Ua ∪ Va| ≥ 2 holds.
Proof. Let α, β ∈ Ω be such that φ(α, β) = a. There exists γ ∈ Ω \ {α, β} such that
φ(β, γ) = a and φ(α, γ) 6= a, as
|{ω ∈ Ω \ {β} | φ(α, ω) = a}| = δa − 1 < δa = |{ω ∈ Ω | φ(β, ω) = a}|.
We have [{α, β, γ}] = [a, a, φ(γ, α)] ∈ Va. If |Ua ∪ Va| = 1, then Ua = Va, and
[a, a, φ(γ, α)] ∈ Ua. Lemma 3.1 implies
{a} ∈
{
{a, (Ψ ◦ φ)(γ, α)}, {a,Ψ(a)}, {φ(γ, α),Ψ(a)}
}
,
which is a contradiction.
Lemma 4.3. |Ω3| ≥ max
{
m,
⌈4m+ l(l − 1)
6
⌉}
.
212 Ars Math. Contemp. 2 (2009) 207–215
Proof. Let K′ denote a subset of K such that K = K′ ∪Ψ(K′) and K′ ∩Ψ(K′) = ∅. Let
Γ = (
⋃
a∈K′∩M Ua ∪ Va) ∪ (
⋃
b∈L2 Ub). Lemma 3.2 implies that |Γ| =
∑
a∈K′∩M |Ua ∪
Va|+
∑
b∈L2 |Ub|. By Lemma 4.2, we have that |Γ| ≥ 2|K
′∩M|+|L2| = m. In particular,
|Ω3| ≥ m.
We defineX =
{
{c, d} ∈ L(2) | Tc,d∩Γ 6= ∅
}
. We claim |X| ≤ |Γ|. Indeed, if |X| >
|Γ|, then there exist {c, d}, {c′, d′} ∈ X such that Γ ∩ Tc,d ∩ Tc′,d′ 6= ∅. By the definition
of Γ, this contradicts Lemma 3.4, and the claim holds. Equivalently, |L(2) \X| ≥
(
l
2
)
−|Γ|.
Now, Lemma 4.1 implies that
|Ω3| ≥
∣∣∣Γ ∪ ⋃
{c,d}∈L(2)\X
Tc,d
∣∣∣ = |Γ|+ ∣∣∣ ⋃
{c,d}∈L(2)\X
Tc,d
∣∣∣ ≥ ⌈4m+ l(l − 1)
6
⌉
.
Lemma 4.4. Let D ⊂ C. If D = Ψ(D), then
|Ω3| ≥ |∆(D)|+
∣∣∣{[a, x, y] | a ∈ D, x, y ∈ C \ D, [a, x, y] 6= ∅}∣∣∣+ ∣∣∣ ⋃
b,c∈D
Tb,c
∣∣∣.
Proof. Lemma 3.1 implies that the sets corresponding to the terms of the right-hand side
are disjoint. Hence the claim holds.
Lemma 4.5. Suppose D ⊂ C, D = Ψ(D) and f(D) < |Ω|. Then |Ω3| ≥ 1 + |D| +
|
⋃
b,c∈D Tb,c|.
Proof. By assumption, Lemma 3.6 implies that ∆(D) 6= ∅. Also, for each a ∈ D,
Lemma 3.6 implies that there exist xa, ya ∈ C \ D such that [a, xa,Ψ(ya)] 6= ∅. We
have xa ∈ C \ D and Ψ(ya) ∈ C \ D, as Ψ(D) = D. Lemma 4.4 implies that
|Ω3| ≥ |∆(D)|+
∑
a∈D
∣∣∣{[a, xa,Ψ(ya)]}∣∣∣+ ∣∣∣ ⋃
b,c∈D
Tb,c
∣∣∣ ≥ 1 + |D|+ ∣∣∣ ⋃
b,c∈D
Tb,c
∣∣∣.
5 Proof of the main result
In this section we prove Theorem 1.2. Let a regular edge-coloring (Ω, C, φ,Ψ) be given.
Let Uc, Vc, K, L,M, k, l, m be as in (2.1), (4.1) and (4.2).
Lemma 5.1. Assume |Ω| ≥ 8. If m = 0 or |C| ≥ 6, then |Ω3| ≥ |C| holds.
Proof. If m = 0, then |C| = |Ω| − 1 > 6. If |C| > 6, then Lemma 4.1 implies |Ω3| ≥ |C|.
If |C| = 6, then m ≥ 1, as |Ω| ≥ 8. Therefore the result follows from Lemma 4.1.
Lemma 5.2. If |Ω| ≥ 11 and K1 6= ∅, then |Ω3| ≥ |C|.
Proof. Let c ∈ K1. The condition (R1) implies that there exist α1, α2, α3 ∈ Ω such that
φ(α1, α2) = φ(α2, α3) = c. We define d = φ(α3, α1), D = {c,Ψ(c)}, and E = C \ D.
Since |Ω| ≥ 11 and δc = 1, we get that E 6= ∅, and that
for all ω ∈ Ω \ {α1, α3}, φ(ω, α2) ∈ E . (5.1)
By (R1), for any e ∈ E \{d}, there exists βe ∈ Ω \ {α1} such that φ(α3, βe) = e. We have
φ(βe, α2) ∈ E by (5.1). It follows that
|{(x, y) | x ∈ E \ {d}, y ∈ E , [c, x, y] 6= ∅}| ≥ |E \ {d}|. (5.2)
Y. Nakashima: A partial generalization of the Livingstone–Wagner Theorem 213
As f(D) = 6 < |Ω|, Lemma 3.6 implies ∆(D) 6= ∅. Lemma 4.4 implies that
|Ω3| ≥ |∆(D)|+
∣∣{[a, x, y] | a ∈ D, x, y ∈ E , [a, x, y] 6= ∅}∣∣+ ∣∣∣ ⋃
b,b′∈D
Tb,b′
∣∣∣
= |∆(D)|+ |{[c, x, y] | x, y ∈ E , [c, x, y] 6= ∅}|+ |Vc|
= |∆(D)|+ |{(x, y) | x, y ∈ E , [c, x, y] 6= ∅}|+ |Vc|
= |∆(D)|+ |{(x, y) | x ∈ E \ {d}, y ∈ E , [c, x, y] 6= ∅}|
+ |{y | y ∈ E , [c, d, y] 6= ∅}|+ |Vc|.
Combining the inequalities |∆(D)| ≥ 1, |Vc| ≥ 1, and (5.2), we obtain
|Ω3| ≥ 1 + |C| − |{c,Ψ(c), d}|+ 0 + 1 ≥ |C| − 1.
Suppose |Ω3| < |C|. Then equality is forced in each of the above inequalities. In
particular, |∆(D)| = 1, d /∈ {c,Ψ(c)}, and [c, d, y] = ∅ for any y ∈ E .
Now, if there exists γ ∈ Ω\{α1} such that φ(α3, γ) = d, then (5.1) implies φ(γ, α2) ∈
E . This would imply [c, d, y] 6= ∅, where y = φ(γ, α2) ∈ E , which is a contradiction. Thus
there is no such γ. That is, δd = 1. Hence f(D ∪ {d,Ψ(d)}) ≤ 10 < |Ω|, and Lemma 3.6
implies ∆(D ∪ {d,Ψ(d)}) 6= ∅. We have ∆(D) = ∆(D ∪ {d,Ψ(d)}), as |∆(D)| = 1.
However, since f({c,Ψ(c)}) = 6 < |Ω|, Lemma 3.6 implies that there exist z, w ∈ E such
that [d, z, w] 6= ∅. Since [d, z, w] ∈ ∆(D) and [d, z, w] /∈ ∆(D ∪ {d,Ψ(d)}), we have
∆(D) 6= ∆(D ∪ {d,Ψ(d)}), which is a contradiction. Therefore |Ω3| ≥ |C|.
Lemma 5.3. If |Ω| ≥ 11 and L = ∅, then |Ω3| ≥ |C|.
Proof. By assumption, we have C = K1 ∪M. If K1 = ∅, then the result follows from
Lemma 4.3. Otherwise the result follows from Lemma 5.2.
Lemma 5.4. If |Ω| ≥ 11 and K = ∅, then |Ω3| ≥ |C|.
Proof. By Lemma 5.1, we may assume l ≤ 5 and m ≥ 1. If m ≥ 2, then Lemma 4.3
yields the result. Assume m = 1. Set C = {1, . . . , l}. Then we may assume without loss
of generality that δ1 ≥ 2. Since f(C \ {1}) = 2l < |Ω|, Lemma 3.6 yields [c, 1, 1] 6= ∅ for
each c ∈ C. Therefore |Ω3| ≥ l.
Lemma 5.5. Let (Ω, C, φ,Ψ) be a regular edge-coloring with |Ω| ≥ 11 and |C| = 3. Then
|Ω3| ≥ 3 holds.
Proof. We argue by contradiction. Assume |Ω3| < 3. Lemmas 5.3 and 5.4 imply C =
{1,−→1 ,←−1 }, where Ψ(1) = 1 and Ψ(−→1 ) = ←−1 . Also, |Ω3| < |C| implies δ−→1 ≥ 2 by
Lemma 5.2. We have δ1 = 1 by Lemma 4.3. Since |U−→1 ∪ V−→1 | ≥ 2 by Lemma 4.2, it
follows from |Ω3| ≤ 2 that
Ω3 = U−→1 ∪ V−→1 . (5.3)
Now, since [1,
−→
1 ,
←−
1 ] /∈ U−→
1
∪ V−→
1
by Lemma 3.1, we have [1,
−→
1 ,
←−
1 ] = ∅, which implies
T
1,
−→
1
= {[1,−→1 ,−→1 ]} by (5.3). Since f({1}) = 4 < |Ω|, Lemma 3.6 implies ∆({1}) 6= ∅.
Hence
Ω3 = {[1,
−→
1 ,
−→
1 ]} ∪∆({1}). (5.4)
214 Ars Math. Contemp. 2 (2009) 207–215
We compare (5.3) with (5.4). Since [1,
−→
1 ,
−→
1 ] /∈ U−→
1
by Lemma 3.2, we have U−→
1
=
∆({1}), which implies U−→
1
= {[−→1 ,−→1 ,←−1 ]}. Hence Ω3 = {[1,
−→
1 ,
−→
1 ], [
−→
1 ,
−→
1 ,
←−
1 ]}.
Let α1 ∈ Ω. Pick distinct β1, α2, β2, α3 ∈ Ω in such a way that φ(α1, β1) = 1,
φ(α1, α2) =
−→
1 , φ(α2, β2) = 1, and φ(α2, α3) =
−→
1 . Notice that δ1 = 1. Since
φ(α1, α2) = φ(α2, α3) =
−→
1 , we have φ(α1, α3) =
−→
1 . Since φ(α1, α2) =
−→
1 and
φ(α2, β2) = 1, we have φ(β2, α1) =
−→
1 . Similarly, we have φ(α3, β2) =
−→
1 . Thus,
[{α1, α3, β2}] = [
−→
1 ,
−→
1 ,
−→
1 ], a contradiction.
We are now ready to prove our main result.
Theorem 5.6. Let (Ω, C, φ,Ψ) be a regular edge-coloring. If |Ω| ≥ 11, then |Ω3| ≥ |C|.
Proof. Let K = {−→1 , . . . ,
−→
k ,
←−
1 , . . . ,
←−
k }, L = {1, . . . , l}, and Ψ(−→i ) = ←−i . By Lem-
mas 5.1, 5.3, 5.4, and 5.5, we only need to consider the cases where (k, l, |C|) = (1, 2, 4),
(1, 3, 5), and (2, 1, 5). In each case, we may assume δ−→
i
≥ 2 for 1 ≤ i ≤ k, by Lemma 5.2.
Lemma 4.2 implies that
|U−→
i
∪ V−→
i
| ≥ 2. (1 ≤ i ≤ k) (5.5)
Also, Lemma 3.2 implies that
(U−→
i
∪ V−→
i
) ∩ Tj,j′ = ∅. (1 ≤ i ≤ k, 1 ≤ j, j′ ≤ l) (5.6)
Notice that Ta,b 6= ∅ unless b = Ψ(a) and δa = 1, for any a, b ∈ C.
Suppose (k, l) = (1, 2). If δ1 = δ2 = 1, then Lemma 4.5 implies |Ω3| ≥ 4, so we may
assume without loss of generality that δ1 ≥ 2. If |U1 ∪T1,2| ≥ 2, then |Ω3| ≥ |U−→1 ∪V−→1 ∪
U1 ∪ T1,2| = |U−→1 ∪ V−→1 | + |U1 ∪ T1,2| ≥ 4 by (5.5) and (5.6). If |U1 ∪ T1,2| = 1, then
U1 = T1,2, and U1 ∪ T1,2 = {[1, 1, 2]} by Lemma 3.3. In particular, we get [1, 1, 2] 6= ∅.
Lemmas 3.1 and 3.2 imply that {[1, 1, 2]}, U−→
1
, T
1,
−→
1
, and T
2,
−→
1
are pairwise disjoint.
Hence we obtain |Ω3| ≥ 4 by collecting these families.
Next suppose (k, l) = (1, 3). If [1, 2, 3] = ∅, then Lemma 3.3 implies that T1,2,
T1,3, and T2,3 are pairwise disjoint. Hence, |Ω3| ≥ |U−→1 ∪ V−→1 ∪ T1,2 ∪ T1,3 ∪ T2,3| ≥ 5
by (5.5) and (5.6). We may assume that [1, 2, 3] 6= ∅. Lemmas 3.1 and 3.2 imply that
{[1, 2, 3]}, U−→
1
, T
1,
−→
1
, T
2,
−→
1
, and T
3,
−→
1
are pairwise disjoint. Collecting these families, we
have |Ω3| ≥ 5.
Finally suppose (k, l) = (2, 1). Assume |T
1,
−→
1
∪ T
1,
−→
2
| ≥ 2. Lemma 3.2 implies
that (T
1,
−→
1
∪ T
1,
−→
2
), T
Ψ(
−→
1 ),
−→
2
, U−→
1
, and U−→
2
are pairwise disjoint. Hence |Ω3| ≥ |T1,−→1 ∪
T
1,
−→
2
∪ T
Ψ(
−→
1 ),
−→
2
∪ U−→
1
∪ U−→
2
| ≥ 5. We may assume that |T
1,
−→
1
∪ T
1,
−→
2
| = 1. Then
T
1,
−→
1
= T
1,
−→
2
, and T
1,
−→
1
∪ T
1,
−→
2
= {[1,−→1 ,←−2 ]} by Lemma 3.3. In particular, we get
[1,
−→
1 ,
←−
2 ] 6= ∅. Lemma 3.2 implies that {[1,−→1 ,←−2 ]}, U−→
1
∪V−→
1
, andU−→
2
∪V−→
2
are pairwise
disjoint. Therefore |Ω3| ≥ |{[1,
−→
1 ,
←−
2 ]} ∪ U−→
1
∪ V−→
1
∪ U−→
2
∪ V−→
2
| ≥ 5 by (5.5).
Proof of Theorem 1.2. Let (Ω, CG, φG,ΨG) be the regular edge-coloring induced byG. By
the definition of induced regular edge-coloring, |CG| = |Ω[2]/G| holds. For A,B ∈ Ω(3),
if Ag = B for some g ∈ G, then [A] = [B], hence |Ω3| ≤ |Ω(3)/G| holds. The result
follows from Theorem 5.6.
Y. Nakashima: A partial generalization of the Livingstone–Wagner Theorem 215
6 Acknowledgements
The author would like to thank his supervisor Akihiro Munemasa for valuable suggestions
and comments. The author would also like to thank the anonymous referees for pointing
out mistakes in an earlier version of this paper, and for their valuable suggestions.
References
[1] P. J. Cameron and J. Saxl, Permuting unordered subsets, Quart. J. Math. Oxford Ser. (2) 34
(1983), no. 134, 167–170.
[2] J. D. Dixon and B. Mortimer, Permutation Groups, Springer-Verlag, New York, 1996.
[3] D. Livingstone and A. Wagner, Transitivity of finite permutation groups on unordered sets, Math.
Zeitschr. 90 (1965), 393–403.
[4] W. J. Martin and B. E. Sagan, A new notion of transitivity for groups and sets of permutations,
J. London Math. Soc. (2) 73 (2006), 1–13.
[5] B. E. Sagan, The Symmetric Group, second ed., Springer-Verlag, New York, 2001.