These are research problems containing notes and references to solutions if they exist. There is also a list of old problems from my homepage; if you are interested in exercises on permutation groups, there are many in my book, and you can find some further exercises on the web. You may also be interested in the Permutation Groups Resources Page, or the page devoted to problems from the paper P. J. Cameron, Permutations, pp. 205-239 in Paul Erdős and his Mathematics, Vol. II (ed. G. Halász, L. Lovász, M. Simonovits and V. T. Sós), Bolyai Society Mathematical Studies 11, Springer, Berlin, 2002.
A Belorussian translation of this page by Michail Bogdanov is available here. |
STOP PRESS 23 December 2008: Eleonora Crestani and Pablo Spiga have claimed a negative solution to this problem. More news later . . .
(fg)(K) = sum f(L)g(K-L) : L subseteq K, |L| = n.
The constant function e in V_{1} with value 1 is not a zero-divisor. We say that G is entire if A[G] is an integral domain, and strongly entire if A[G]/eA[G] is an integral domain. It is conjectured that G is (strongly) entire if and only if it has no finite orbits on X. In the absence of a proof of this conjecture, can one show the following:
If the permutation groups G_{1} on X_{1} and G_{2} on X_{2} are (strongly) entire, then G_{1} × G_{2} (in its intransitive action on X_{1} union X_{2}) is (strongly) entire.Note: Maurice Pouzet has proved that, if G has no finite orbits, then G is entire. This appears in Theor. Inform. Appl. 42 (2008), 83-103.
The number a_{n} has various other interpretations:
The initial terms in the sequence can be found here.
(Not every transitive permutation group contains a non-identity semiregular subgroup; the smallest counterexample has degree 12.)
Note: Michael Giudici has some partial results on this problem, including the statement that every minimal normal subgroup of any counterexample to the conjecture is intransitive. See:
Note added 22 November 2001: The matroids include all those representable over finite fields (with each element replaced by q parallel elements, where q is the field order). See Problem 18 below for further details.
Note added 13/7/2007: It has now been proved by Burness et al. that the assertion holds for c = 6, with a single exception, the Mathieu group M_{24}.
A subalgebra of the centraliser algebra which contains the identity matrix and is spanned by symmetric zero-one matrices is the Bose-Mesner algebra of an association scheme on the set X, and G acts as a group of automorphisms of this association scheme. There is always at least one such subalgebra, namely the span of I and J-I, where J is the all-one matrix. We call this subalgebra or association scheme trivial.
Problem: For which transitive permutation groups is it true that the only association scheme invariant under G is the trivial one?
This class of groups includes the 2-homogeneous groups. Any such group must be primitive, and (if not 2-homogeneous) is either of diagonal type or almost simple.
Examples which are not 2-homogeneous do exist. Some can be found in table 3.5.1 of I. A. Faradzev, M. H. Klin and M. E. Muzichuk, "Cellular rings and groups of automorphisms of graphs", pp. 1-152 in Investigations in Algebraic Theory of Combinatorial Objects (ed. I. A. Faradzev, A. A. Ivanov, M. H. Klin and A. J. Woldar), Kluwer, Dordrecht, 1994. The smallest is the group PSL(3,3) acting on the cosets of PO(3,3); this group has degree 234. (I am grateful to Leonard Soicher for this reference).
No such group of diagonal type is known, and the problem of deciding whether any such group exists remains open. There are none having two or three simple factors in their socle. See:
Let d(k,n) be the proportion of derangements in the symmetric group S_{n} in its action on k-sets. Then d(k,n) tends to a limit a(k) as n tends to infinity. (So, for example, a(1)=e^{-1} - this is the usual "derangement problem".) Does a(k) tend monotonically to 1 as k tends to infinity?
Problem: Does this result hold for trivalent graphs? What about other special classes of graphs such as strongly regular graphs?
If G has the same Parker vector as a Frobenius group (resp. a 2-transitive group), is it a Frobenius group (resp. a 2-transitive group)?
If P is a 2-group which is not elementary abelian, then some non-identity element of the centre of P is a square.The answer to this question is negative. The smallest counterexamples have order 128, and there are two of them. This was found by Alexander Hulpke and Andreas Caranti. Alexander provided the following example in GAP:
gap> g:=SmallGroup(128,36);If not, is the following weaker statement true?gap> z:=Centre(g); Group([ f6, f7 ]) gap> r:=List(ConjugacyClasses(g),Representative);; gap> s:=Filtered(r,i->Order(i)>2);; gap> List(s,Order); [ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ] gap> Set(List(s,i->i^2)); [ f4,f5,f4*f7,f5*f6,f3*f4*f5,f3*f4*f5*f6,f3*f4*f5*f7,f3*f4*f5*f6*f7 ] gap> List(last,i->i in z); [ false, false, false, false, false, false, false, false ]
If P is a 2-group which is not elementary abelian, and Q is a core-free subgroup of P, then there is an element lying in no conjugate of Q which is a square.Avinoam Mann also suggested the above group as a possible counterexample to the second question. However, Steve Linton and John Murray both checked that there is no core-free subgroup Q for which it is a counterexample. So the question is still open.
Solution (13 September 2004): The answer to the second question is also negative. Pablo Spiga found that the group of order 128 with generators (1,2,7,3)(4,8)(5,11)(6,9)(10,14)(12,16,13,15), (1,4,7,5)(2,8)(3,11)(6,13,14,12)(9,15)(10,16), and (1,6)(2,9,3,10)(4,12,5,13)(7,14)(8,15)(11,16) is a counterexample. Indeed, in this group the set of elements with fixed points coincides with the set of squares. This group is SmallGroup(128,836) in the GAP library.
The motivating question, whether a vertex-transitive trivalent graph necessarily has a semiregular automorphism of order greater than 2, is currently still open. (But see Problem 23.)
For example, when k=2, the groups are the tetrahedral, octahedral and icosahedral groups, acting on the vertices, edges and faces of the corresponding polyhedra. (Every rotation has an axis, so has just two fixed points in this action.) So the correct bound is 60. (This is a theorem of Iwahori, J. Fac. Sci., Univ. Tokyo 11 (1964), 47-64.)
An upper bound in terms of k has been found by C. Franchi, On permutation groups of finite type, European J. Combinatorics 22 (2001), 821-837.
It follows that the centraliser of a in G is a p-group. Let its order be p^{m}.
A theorem of Kegel (Math. Z. 75 (1961), 373-376) shows that G is nilpotent. Then a theorem of Khukhro (Mat. Zametki 38 (1985), 652-657) shows that G has a normal subgroup whose nilpotency class and index are bounded by functions of p and m.
Is it true that the nilpotency class of G is bounded by a function of p and m?
This question has been settled in the affirmative by Andrei Jaikin, using a theorem of E. Khukhro, On locally nilpotent groups admitting a splitting automorphism of prime order, Mat. sb. 130 (1986), 120-127.
(a) Is there an efficient method to decide whether a set of partitions is the image under F of a subgroup of S_{n}?
(b) If G and H are subgroups of S_{n} such that F(G)=F(H), then G and H have the same order. Are they necessarily isomorphic?
Note added 19 May 2000: The answer to (b) is negative. Eamonn O'Brien has shown that there are two pairs of groups of order 64 (numbers 19 and 111, and 94 and 249, in the lists in MAGMA and GAP), which act transivitely on 16 points, such that the two groups in each pair give rise to the same sets of cycle partitions. You can find a GAP program to verify this.
See P. J. Cameron, Partitions and permutations, Discrete Math. 291 (2005), 45-54.
F(x) = P(x+1).
Now consider the linear analogue. Let G be a subgroup of the general linear group GL(n,q). For i = 0, ..., n, let p_{i} be the probability that the fixed points of a random element form precisely an i-dimensional subspace, and let F_{i} be the number of orbits of G on linearly independent i-tuples. Again the two sequences determine each other.
Problem: Express the relation between these two sequences in terms of generating functions.
Note: This problem is now solved (2 August 2000). It is just a case of finding the right definitions of the q-analogues! See:
Let G be a permutation group on the infinite set X. Assume that G is oligomoprhic, that is, G has only finitely many (say f_{n}) orbits on the set of n-element subsets of X. Dugald Macpherson, Proc. London Math. Soc. (3) 46 (1983), 471-486, showed that, if G is primitive on X (preserves no non-trivial equivalence relation) but not highly set-transitive ((that is, f_{n} > 1 for some n), then the sequence (f_{n}) grows exponentially, that is, limsup (f_{n})^{1/n} > 1. These two assumptions apply throughout this problem, though analogous problems can be posed with primitivity relaxed.
Further information on such sequences is available in my survey article.
A base for a permutation group is a sequence of points whose stabiliser is the identity; it is irredundant if no point is fixed by the stabiliser of its predecessors. Cameron and Fon-Der-Flaass, Europ. J. Combinatorics 16 (1995), 537-544, called a permutation group an IBIS group if all irredundant bases have the same number of elements; they showed that the irredundant bases of an IBIS group are the bases of a matroid.
Problem: What is the relation between the Tutte polynomial of the matroid and the cycle index of the permutation group?
It is known that sometimes the first determines the second and sometimes vice versa. Perhaps there is a gadget which generalises both! See P. J. Cameron, Cycle index, weight enumerator and Tutte polynomial, Electronic J. Combinatorics 9(1) (2002), #N2 (10pp).
How large is the largest antichain of subgroups of the symmetric group S_{n}? More precisely, estimate a_{n}/s_{n}, where a_{n} is the size of the largest antichain and s_{n} the total number of subgroups.
Let L(G) be the subgroup lattice of the finite group G. Is the following true or false? Suppose that the Boolean lattice B(n) of subsets of an n-element set is embeddable as a meet-semilattice of L(G), and suppose that n is maximal with this property. Then there is an embedding of B(n) as meet-semilattice, such that the least element of B(n) is a normal subgroup of G.
Note: The quaternion group Q_{8} shows that we cannot make the least element of B(n) correspond to the identity in general.
Let Z(G) denote the cycle index of the permutation group G, and let F_{n}^{*}(G) be the number of orbits of G on the set of all n-tuples of its permutation domain.
Let G and H be permutation groups acting on sets X and Y respectively. We consider G×H as a permutation group on X×Y. We have
Solution: Solved by Daniele Gewurz. See a paper by Daniele Gewurz, Francesca Merola and me in Discrete Mathematics 308 (2008), 386-394; doi: 10.1016/j.disc.2006.11.054
Let G be a Frobenius group with Frobenius kernel N and Frobenius complement H having orders n and h respectively. Number the elements of N as x_{1},...,x_{n}. Now let X_{ij} be the n × n matrix with (k,l) entry equal to the cardinality of the intersection of x_{i}^{-1}Hx_{k} and x_{j}^{-1}Hx_{l}. Note that X_{ii} = hI while, for i and j distinct, X_{ij} is a zero-one matrix.
Is it true that
Sum_{k} X_{ik}X_{kj} = nX_{ij}+h(h-1)J,where J is the all-one matrix?
Solution: This problem is now solved in the affirmative (but I have lost the solution . . .)
Is it true that a vertex-transitive trivalent graph has a semiregular automorphism (one with all cycles of the same size) of order greater than 2?
Note: This has now been settled affirmatively: see P. J. Cameron, J. Sheehan and P. Spiga, Europ. J. Combinatorics 27 (2006), 924-930; doi: 10.1080/00927870701404812, and a stronger result has been given by Cai Heng Li, Proc. Amer. Math. Soc. 136 (2008), 1905-1910.
Clearly b(G) <= s(G). Is it true that, if G is primitive but not 2-transitive, then s(G) <= b(G) log n?
See Combinatorics Study Group notes on this problem (PDF file).
Is F closed under pointwise multiplication?
I conjecture that the answer is "no". Specifically, let F be the sequence (1,2,4,10,26,...) whose nth term is the number of solutions of g^{2}=1 in the symmetric group of degree n. This sequence belongs to F, but I conjecture that the sequence (1,4,16,100,676...) whose terms are the squares of the terms in this sequence is not in F.
Remark: The set of sequences counting orbits of permutation groups on all n-tuples is closed under pointwise multiplication. Moreover, the set of sequences counting orbits on n-tuples of distinct elements for groups with the property that the stabiliser of a finite set fixes no additional points is closed under pointwise multiplication.
Further remark: The answer in general is "no": if G is the stabiliser of a point in the symmetric group, the sequence begins 2, 3, 4, ..., but a group with 4 orbits on points must have at least 12 orbits on ordered pairs of distinct points. It is harder for transitive groups (where a possible counterexample is given in the question), and still more so for primitive groups.
The most extreme example I know is an extension of a 2n-dimensional vector space over GF(2) by a dihedral group of order 2(2^{n}+1); this has rank 2^{n} and subrank 2^{n-1}+1. So perhaps the conjecture holds with a linear function f.
My homepage | Permutation Groups Resources
Peter J. Cameron
p.j.cameron(at)qmul.ac.uk
11 September 2007
Permutation Groups Pages at Queen Mary: |
Resources | Lecture Notes | Problems | The Book | Problems from "Permutations" |
Maths Research Centre |