Problems from "Permutations"

P. J. Cameron, Permutations, pp. 205-239 in Paul Erdös and his Mathematics, Vol. II, Bolyai Society Mathematical Studies 11, Budapest, 2002.

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^ab 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)?

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?

Which transitive groups contain no derangement of prime order? In particular, do the degrees of such groups have density 0?

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?

Improve the estimate in Theorem 4.3 [for the probability that a random permutation has an invariant set of size k].

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?

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.

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.

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.

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).

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?

29. Covering radius

1. Problem: Given n and k, what is the largest m such that any set of permutations of cardinality at most m has covering radius at least n-k?

   For k=0, the answer is the integer part of n/2.

2. The covering radius of PGL(2,q), in its natural action on q+1 points, is
   • q-2 if q is even;
   • q-3 if q is odd but not congruent to 1 mod 6;
   • q-3, q-4 or q-5 if q is congruent to 1 mod 6.
   Problem: Resolve the last case.

   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.

1. (a) Is there an algorithm which takes as input a set X of partitions of an n-set, performs a polynomial-time (in n) computation after reading each partition, and decides whether X=CP(G) for some permutation group G?

   (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?

2. Let G₁ be a finite permutation group which is (a) primitive, or (b) regular. Let G₂ be a permutation group satisfying CP(G₁)=CP(G₂). Are G₁ and G₂ isomorphic as permutation groups? (This is false if we only assume G transitive.)

3. Let C(G) be the permutation group generated by the cycles of the group G, and define C₀(G)=G and C_n+1(G)=C(C_n(G)) for n>=0. It is known that C₃(G)=C₄(G) for all finite permutation groups G. Determine those groups for which C₂(G)<C₃(G).

4. If H is a subgroup of G with CP(H)=CP(G), must we have H=G? (Yes, if G is finite.)

1. Peter J. Cameron, Cycle index, weight enumerator and Tutte polynomial, Electronic J. Combinatorics 9(1) (2002), #N2 (10pp).
2. Peter J. Cameron, Partitions and permutations, Discrete Math. 291 (2005), 45-54.
3. Peter J. Cameron, Michael Giudici, Gareth A. Jones, William M. Kantor, Mikhail H. Klin, Dragan Marusic and Lewis A. Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc. (2) 66 (2002), 325-333.
4. Peter J. Cameron and C. Y. Ku, Intersecting families of permutations, Europ. J. Combinatorics 24 (2003), 881-890.
5. Peter J. Cameron and Ian M. Wanless, Covering radius for sets of permutations, Discrete Math., in press.
6. Persi Diaconis, Jason Fulman and Robert Guralnick, On fixed points of permutations, preprint July 2007.
7. Clara Franchi, On permutation groups of finite type, European J. Combinatorics 22 (2001), 821-837.
8. Daniele A. Gewurz, Reconstruction of permutation groups from their Parker vectors, J. Group Theory 3 (2000), 271-276.
9. Michael Giudici, Quasiprimitive groups with no fixed point free elements of prime order, J. London Math. Soc. (2) 67 (2003), 73-84.
10. Benoit Larose and Claudia Malvenuto, Stable sets of maximal size in Kneser-type graphs, European J. Combinatorics 25 (2004), 657-673.
11. Martin W. Liebeck and Aner Shalev, Bases of primitive permutation groups, pp. 147-154 in Groups, Combinatorics and Geometry (ed. A. A. Ivanov, M. W. Liebeck and J. Saxl), World Scientific, New Jersey, 2003.

Peter J. Cameron
p.j.cameron(at)qmul.ac.uk
30 March 2005