A partial generalization of the Livingstone-Wagner Theorem

Abstract

For a transitive permutation group G on a finite set Ω, the Livingstone–Wagner Theorem states that if G is k-homogeneous then G is (k − 1)-transitive. It can be conjectured that the number of G-orbits on k-subsets of Ω is greater than or equal to the one on ordered (k − 1)-tuples of Ω, if |Ω| is sufficiently large. For the simplest case k = 3, we prove this by establishing a result on edge-colorings of complete digraphs.