To continue my series on the symmetric group, I want to consider the question: What is the role of the symmetric group in mathematics?
First, a diversion. What is the role of graphs in mathematics?
I would say that graphs do two main jobs. First, they model the notion of connectivity. The connection with networks comes to mind; for example, the connectedness of a graph (the number of vertices which have to be deleted in order to disconnect the graph) has an obvious application to networks where the nodes may fail or be destroyed and we wish the remaining nodes to remain in touch with one another.
There are other places where similar ideas arise. I was delighted to learn recently about the graph parameter which can be defined as the sum, over all pairs of vertices, of the effective resistance of the graph, when each edge is replaced by a one-ohm resistor and the two chosen vertices are attached to a battery. A little thought shows that this is a “connectivity measure”. It also describes the expected return time for a random walk on the graph, and this parameter of the concurrence graph of a block design is what statisticians call the “A-optimality criterion”. You can read about this in my paper with R. A. Bailey in the 2009 British Combinatorial Conference invited speakers’ volume.
The other major role of graphs is to model incompatibility. This goes back to the Four-Colour Conjecture, where we are colouring countries on a map; adjacent countries must have different colours, so we join them by an edge. Colouring problems generalise to things like scheduling problems, where (for example) two classes must be scheduled at different times if the same student is to take both; and more generally, to the class of “constraint satisfaction problems”, which can be expressed as the existence of homomorphisms between specified relational structures. (Graph colouring is a particular case of the homomorphism problem: a graph can be coloured with k colours if and only if it has a homomorphism to the complete graph with k vertices.)
What about groups?
It is a commonplace of the subject that groups measure symmetry. The order of the automorphism group of an object is a crude measure of the amount of symmetry of the object; the structure of the automorphim group, and of its action on the object, gives us much more detailed information.
We generally think that symmetry is a good thing. But to continue with graphs for a moment: the only graphs whose automorphism group is the symmetric group on the vertex set are the complete and null graphs. On the other hand, a folklore result (I am really not sure of its provenance, but surely Erdős had a hand in it) asserts that almost all finite graphs have only the identity automorphism. So symmetry is not much use for “typical” graphs. (In the countably infinite case, things are very different; another story I will get round to telling one of these days, maybe.)
But look again at that folklore result. Maybe it reminds you of a theorem of Hilbert, according to which almost all polynomials have as Galois group the symmetric group on their roots.
The Galois group of a polynomial over a base field F is the automorphism group of something related to the polynomial: it consists of all automorphisms of the splitting field (the field generated by the roots) which fix elementwise the field F. Put another way, it is a group of permutations on the roots of F which are, in some sense, symmetries. (There is a complication here, if the polynomial has repeated roots; I will ignore this.)
For example, let ω be a 7th root of unity in the field of complex numbers, and α=ω+ω^{-1}. We can suppose that α = 2 cos 2π/7. Then β=α^{2}–2 = 2 cos 4π/7, and γ=β^{2}–2 = 2 cos 8π/7; and we return to the start since α=γ^{2}–2. The three numbers α, β, γ are the roots of the polynomial x^{3}+x^{2}–2x–1; they have cyclic symmetry, like “paper, scissors, stone” in my first post on the symmetric group.
According to Hilbert, for almost all polynomials, we have the maximum amount of symmetry. So should we all be as happy as kings? Not because of this: Hilbert is telling us that this symmetry is simply absence of structure. So the other role of the symmetric group is to tell us about lack of structure, as we saw already in the case of graphs.
I want to say something about an intermediate case. This theory was discussed by Norman Biggs a long time ago, under the name “pictures”, if my memory serves me well. I will talk about 1-factorisations of complete graphs. These have nothing to do with graphs, really; one of them consists of a set of n–1 partitions of the set {1,…,n} into parts of size 2, in such a way that each 2-element subset occurs in a part of exactly one of the partitions. Note that
- the numbers work out right, since there are n(n–1)/2 2-element subsets, and each partition contains n/2 of them;
- n must be even for such partitions to exist.
It is not hard to see that, for all even n, a factorisation exists.
An automorphism of a factorisation is a permutation of the numbers {1,…,n} which induces a permutation on the set of partitions. It is a strong automorphism if it fixes all of these partitions.
For n=4, there is only one factorisation, which we can write concisely as 12|34, 13|24, 14|23. Its automorphism group is the symmetric group S_{4}, and acts as S_{3} on the set of three partitions, as we saw last time; the group of strong automorphisms is the Klein group.
This example generalises, by taking the factorisation to consist of the parallel classes of lines in an affine space over GF(2). The automorphism group is the affine group, and the group of strong automorphisms is its translation subgroup. Gabor Korchmàros and I showed, using the Classification of Finite Simple Groups (CFSG), that the only factorisations having 2-transitive automorphism groups are these affine examples and three sporadic examples on 6, 12 and 28 points.
Associated with a partition there is another group. The partitions into sets of size 2 correspond to involutions (permutations of order 2), interchanging the elements of each part; the n–1 involutions generate a subgroup of the symmetric group. In our example, this gives the three permutations (1,2)(3,4), (1,3)(2,4) and (1,4)(2,3), generating the Klein group of order 4.
I will use A(F) for the automorphism group of the factorisation F, SA(F) forr the group of strong automorphisms, and G(F) for the group generated by the corresponding involutions.
It is known that A(F) is the trivial group for almost all factorisations F. (I proved this some thirty years ago, along with the same result for Latin squares and Steiner triple systems. Laci Babai proved the result for Steiner triple systems, and implicitly for Latin squares; he got into print before I did, so I decided it wasn’t worth publishing the extra bit. But Laci and I might revisit the problem some day…)
I don’t know whether a proof has been written down anywhere, but it is true also that G(F) is the symmetric group S_{n} or the alternating group A_{n} for almost all factorisations F. (If n is a multiple of 4, then the involutions arising from partitions are even permutations, and lie in the alternating group.)
Here is a sketch of the proof. Observe first that G(F) is always a transitive permutation group, indeed, a generously transitive group (any two points can be interchanged by some group element). Now if this group is not the symmetric or alternating group, then it is contained in some maximal subgroup H of the symmetric or alternating group. For each such H, there are at most |H|^{n-1} choices of F. Now a consequence of CFSG is that there are not too many maximal transitive subgroups, and we can bound this sum. On the other hand, using the solution to the van der Waerden Permanent Conjecture, we can produce a (much larger) lower bound for the total number of factorisations.
This line of argument has been very fruitful. Here is, to my mind, the best result. In a non-cyclic group, it is trivial that every element lies in a proper subgroup. But Łuczak and Pyber proved the following:
For almost all permutations g in S_{n}, the only transitive subgroups of S_{n} containing g are S_{n} and possibly A_{n}.
The precise rate of convergence implied by the “almost all” in this theorem is still unknown.
Both of the above results about factorisations say that most of them have no interesting structure. Is there a deeper connection? Note that
- SA(F) is the centraliser of G(F) in the symmetric group;
- A(F) is contained in the normaliser of G(F) in the symmetric group.
Now the larger a group, the smaller its centraliser. So the first point above hints that there may be a connection between the facts that G(F) is almost always as large as possible and that A(F) is almost always as small as possible. Is it possible to find a more compelling and direct argument?
Now let us return briefly to Galois groups.
Any graph gives rise to a variety of polynomials; I will consider here the chromatic polynomial, though others await attention. The chromatic polynomial of a graph is never irreducible, so its Galois group cannot even be transitive. (If the graph has chromatic number k, then 0,1,…,k–1 are roots of the chromatic polynomial.) But empirically we find that, most of the time, any irreducible factor of the chromatic polynomial has the symmetric group as its Galois group. So two questions arise:
- Can the above empirical statement be turned into mathematics, and proved?
- Is there any connection between “large Galois group” and “small automorphism group” for typical graphs (or indeed between “large automorphism group and small Galois group” for some special graphs)?
The second question is a suggestion of Charles Leedham-Green.
To finish with a question about 1-factorisations, which has been considered by several people, including Ernie Shult and Dave Wagner, but is still open as far as I know:
- Determine the 1-factorisations F which have the property that G(F) is contained in A(F).
Examples include the parallelisms of lines in affine spaces over GF(2).