Vol. 18, No. 1, 1966

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 290: 1  2
Vol. 289: 1  2
Vol. 288: 1  2
Vol. 287: 1  2
Vol. 286: 1  2
Vol. 285: 1  2
Vol. 284: 1  2
Vol. 283: 1  2
Online Archive
The Journal
Editorial Board
Special Issues
Submission Guidelines
Submission Form
Author Index
To Appear
ISSN: 0030-8730
A combinatorial problem in the symmetric group

Oscar S. Rothaus and John Griggs Thompson

Vol. 18 (1966), No. 1, 175–178

If G is a group and T is a nonempty subset of G, we say that T divides G if and only if G contains a subset S such that every element of G has a unique representation as ts with t in T, s in S, in which case we write T S = G. We study the case where G is Σn, the symmetric group on n symbols and T is the set consisting of the identity and all transpositions in Σn.

The problem may be given a combinatorial setting as follows: For x, y in Σn, let d(x,y) be the minimum number of transpositions needed to write xy1. One verifies that d converts Σn into a metric space, and that T divides Σn if and only if Σn can be covered by disjoint closed spheres of radius one.

We use the irreducible characters of Σn, together with judiciously selected permutation representations of Σn, to prove the following result.

Theorem. If 1 + (n(n 1))2 is divisible by a prime exceeding √n-- + 2, then T does not divide Σn.

Mathematical Subject Classification
Primary: 20.20
Received: 22 December 1964
Published: 1 July 1966
Oscar S. Rothaus
John Griggs Thompson