# Problems from "Permutations"

This document contains further notes on the 28 problems in the paper
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

Page 221: the inequality is the wrong way round in the bound attributed to Wendy Myrvold. Apologies to her.

### The problems

#### Problem 1

Find classes of groups for which Jerrum's Markov chain is rapidly mixing.

#### Problem 2

Investigate the behaviour of the proportion of derangements in the group Sn 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.

#### Problem 3

Does the number F(-1) have any meaning in an oligomorphic group (where it can be defined)?

#### Problem 4

For which classes of transitive permutation groups is the proportion of derangements bounded away from zero?

#### Problem 5

Does there exist a function f(p,b) such that, if n=pab 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 (logpb)2 (about the square of what was previously known).

#### Problem 6

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.  and Giudici . The problem is not yet solved!

#### Problem 7

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.  and Giudici . The problem is not yet solved!

#### Problem 8

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 .

#### Problem 9

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 .

#### Problem 10

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.

#### Problem 11

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 Sn except Sn and possibly An tends to 1 as n tends to infinity.

#### Problem 12

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

#### Problem 13

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 . This was also established by Larose and Malvenuto . The general bound, and the characterisation of equality, have recently been proved by David Ellis.

#### Problem 14

Which sharply s-transitive sets of permutations exist?

#### Problem 15

Determine the sharp groups.

#### Problem 16

[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  solved this by giving the bound max{60,a!a(a!a-1)}. I don't know whether this can be improved.

#### Problem 17

Which geometric sets of permutations exist?

#### Problem 18

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 Sn has cardinality at most Producta 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  in the paper.

#### Problem 19

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

#### Problem 20

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?

#### Problem 21

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 . It's not clear what sort of "classification" might be possible.

#### Problem 22

Which permutation groups attain the bound in the stronger form of Maillet's theorem?

#### Problem 23

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

#### Problem 24

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.

#### Problem 25

Which rational numbers occur as alpha(G) for some finite group G?

#### Problem 26

Extend Theorem 8.1 to special classes of graphs, for example, the class of cubic graphs.

#### Problem 27

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.

#### Problem 28

For which pairs m,n does the group Zm have a regular action on the generic n-tuple of orders?

### New problems

The covering radius of a set S of permutations on {1,...,n} is the largest r such that there is a permutation g for which the Hamming distance from g to any element of S is at least r. See Cameron and Wanless .
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.

#### 30. Partitions and permutations

Here CP(G) denotes the set of all cycle partitions associated with elements of a permutation group G. See Cameron .
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 G1 be a finite permutation group which is (a) primitive, or (b) regular. Let G2 be a permutation group satisfying CP(G1)=CP(G2). Are G1 and G2 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 C0(G)=G and Cn+1(G)=C(Cn(G)) for n>=0. It is known that C3(G)=C4(G) for all finite permutation groups G. Determine those groups for which C2(G)<C3(G).

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

### Further references

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

 Permutation Groups Pages at Queen Mary: Resources | Lecture Notes | Problems | The Book | Problems from "Permutations" Maths Research Centre