P. J. Cameron, Permutations, pp. 205-239 in Paul Erdös and his Mathematics, Vol. II, Bolyai Society Mathematical Studies 11, Budapest, 2002.It will be added to as I get information about these problems. I also hope to add new problems (in the spirit of those in the paper) from time to time.
For the context of the problems, see the paper.
Misprints | The problems | New problems | References
Find classes of groups for which Jerrum's Markov chain is rapidly mixing.
Investigate the behaviour of the proportion of derangements in the group S_{n} acting on k-sets. In particular, show that a(k) is an increasing function of k which tends to 1 as k goes to infinity.
Does the number F(-1) have any meaning in an oligomorphic group (where it can be defined)?
For which classes of transitive permutation groups is the proportion of derangements bounded away from zero?
Does there exist a function f(p,b) such that, if n=p^{a}b where p is prime and a>f(p,b), then any transitive permutation group of degree n contains a derangement of p-power order? If so, what is the magnitude of f(p,b)?Pablo Spiga (personal communication) has new lower bounds for the function f (if it exists). These lower bounds are roughly (log_{p}b)^{2} (about the square of what was previously known).
Is it true that every transitive 2-closed group contains a derangement of prime order? In particular, does every vertex-transitive graph (or digraph) admit a fixed-point-free automorphism of prime order?See the papers of Cameron et al. [3] and Giudici [9]. The problem is not yet solved!
Which transitive groups contain no derangement of prime order? In particular, do the degrees of such groups have density 0?See the papers of Cameron et al. [3] and Giudici [9]. The problem is not yet solved!
What information does the Parker vector of G carry about G? In particular, which groups or classes of groups are characterised by their Parker vectors?See Gewurz [8].
Improve the estimate in Theorem 4.3 [for the probability that a random permutation has an invariant set of size k].See Diaconis, Fulman and Guralnick [6].
Show that the number of odd rows of a random Latin square of order n is approximately binomial B(n,1/2) as n tends to infinity.
Show that, with the ... measure [where the probability of a permutation g is proportional to the number of Latin squares having the identity and g as first two rows], the probability that a random permutation lies in no transitive subgroup of S_{n} except S_{n} and possibly A_{n} tends to 1 as n tends to infinity.
(a) Given n and a subset A of {0,...,n-2}, what is the largest cardinality of a set S of permutations of {1,...,n} such that, for all distinct g,h in S, we have fix(gh^{-1}) in A?(b) What is the structure of such a set of permutations of maximum size?
(c) How do the answers change if we assume that S is a group?
Is it true that, if n is sufficiently large in terms of s, then F(n,>=s) = (n-s)!, and a set meeting the bound is a translate of the stabiliser of s points?C. Y. Ku has given an affirmative answer to this problem in the case s=1: that is, an intersecting family of permutations of {1,...,n} having cardinality (n-1)! is a translate of the stabiliser of a point in the symmetric group. See Cameron and Ku [4]. This was also established by Larose and Malvenuto [10]. The general bound, and the characterisation of equality, have recently been proved by David Ellis.
Which sharply s-transitive sets of permutations exist?
Determine the sharp groups.
[reworded a bit] If G is a permutation group in which every non-identity element fixes exactly a points, but G does not have a fixed set of size a, then the order of G is bounded by a function of a; find an explicit bound.C. Franchi [7] solved this by giving the bound max{60,a!a(a!a-1)}. I don't know whether this can be improved.
Which geometric sets of permutations exist?
Let A be a finite set of non-negative integers. Show that, for n sufficiently large in terms of a, an A-intersecting set of permutations in S_{n} has cardinality at most Product_{a in A}(n-a), with equality if and only if it is a geometric set of type A.Wishful thinking, I'm afraid - this is false! There are sets of type {1} on n points with more than n-1 permutations, for arbitrarily large n: see reference [79] in the paper.
Prove Pyber's conjecture, in the following form: there exists a universal constant c such that a primitive permutation group G of degree n has a base of size at most c log|G|/log n.There has been substantial progress on these, summarised in the paper by Liebeck and Shalev [10]. Seress showed that it suffices to prove the result for affine and almost simple groups; Benbenishty proved it for almost simple groups; and Liebeck and Shalev have obtained substantial progress on the affine case.
Is there a function f such that any greedy base for a primitive group G has size at most f(b(G))? Could this even be true with a linear function?
Determine the IBIS groups (or, at least, the corresponding matroids).This problem is harder than I thought. Every linear code over GF(q) is associated with an IBIS group, whose associated matroid is obtained from the matroid of the code by replacing each element by q parallel elements. See Cameron [1]. It's not clear what sort of "classification" might be possible.
Which permutation groups attain the bound in the stronger form of Maillet's theorem?
- Which groups have the property that all greedy bases have the same size? Or that greedy bases are preserved by re-ordering? Can a matroid or similar structure be associated with the greedy bases under suitable conditions?
- What about variants of the greedy algorithm?
- Prove that the minimum base size of an almost simple primitive group is at most 5 with known exceptions.
Find an efficient algorithm (e.g. an on-line algorithm) for finding a generating set of size at most n/2 for the subgroup generated by an arbitrary set of permutations.
Which rational numbers occur as alpha(G) for some finite group G?
Extend Theorem 8.1 to special classes of graphs, for example, the class of cubic graphs.
Show the existence of a function f with the following property: every primitive permutation group of degree n, except the alternating group, has the property that almost all G-invariant f(n)-uniform hypergraphs have automorphism group precisely G. Establish the smallest possible f for which this holds.
For which pairs m,n does the group Z^{m} have a regular action on the generic n-tuple of orders?
For k=0, the answer is the integer part of n/2.
There is an alternative formulation in the Minkowski plane or ruled quadric over GF(q). Let s be minimal such that there is a set of points containing one point of each generator and intersecting each conic in at most s points. Then the covering radius of PGL(2,q) is q+1-s.
(b) Is there a polynomial-length "certificate" S for X with the property that, given the certificate, the fact that X=CP(G) can be verified with a polynomial-time computation after reading each element of X?
Peter J. Cameron
p.j.cameron(at)qmul.ac.uk
30 March 2005
Permutation Groups Pages at Queen Mary: |
Resources | Lecture Notes | Problems | The Book | Problems from "Permutations" |
Maths Research Centre |