## Peter Cameron's abstracts |

Peter J. Cameron, Groups with right-invariant multiorders

A *Cayley object* for a group *G* is a structure on which
*G* acts regularly as a group of automorphisms. The main theorem asserts
that a necessary and sufficient condition for the free abelian group *G*
of rank *m* to have the generic *n*-tuple of linear orders as a
Cayley object is that *m*>*n*. The background to this theorem is
discussed. The proof uses Kronecker's Theorem on diophantine approximation.

Peter Cameron, Claude Laflamme, Maurice Pouzet, Sam Tarzi, Robert Woodrow, Overgroups of the Automorphism Group of the Rado Graph

We are interested in overgroups of the automorphism group of the Rado graph. One class of such overgroups is completely understood; this is the class of reducts. In this article we tie recent work on various other natural overgroups, in particular establishing group connections between them and the reducts.

João Araújo, Wolfram Bentz and Peter J. Cameron, Groups synchronizing a transformation of non-uniform kernel

This paper concerns the general problem of classifying the deterministic automata that admit a synchronizing (or reset) word. (For our purposes it is irrelevant if the automata have initial or finite states.) Our departure point is the study of the transition semigroup associated to the automaton and then we take advantage of the enormous and very deep progress made during the last decades on the theory of permutation groups, their geometry and combinatorial structure. Our main results provide infinite families of automata admitting a synchronizing (or reset) word.

Let *X* be a finiote set and let *G* be a primitive group of
permutations on *X*. It is well known (by some recent results proved by
P. M. Neumann) that for some such *G* and some singular
transformations *t* of uniform kernel (that is, all blocks have the same
number of elements), the semigroup ⟨*G,g*⟩ does not generate
a constant map. We say that a primitive group *G* on *X* is
*almost synchronizing* if *G* together with any map of
non-uniform kernel generates a constant. In this paper we provide two methods
to build almost synchronizing groups and provide several families of such
groups.

The paper ends with a number of problems likely to attract the attention of experts in computer science, combinatorics and geometry, groups and semigroups, linear algebra and matrix theory.

João Araújo, Peter J. Cameron, James Mitchell and Max Neunhöffer, The classification of normalizing groups

Let *X* be a finite set such that |*X*| = *n*. Let
*T _{n}* and

João Araújo and Peter J. Cameron, Two generalizations of homogeneity in groups with applications to regular semigroups

Let *X* be a finite set such that |*X*|=*n* and
let *i*≤*j*≤*n*. A group *G*≤*S _{n}*
is said to be (

A group *G*≤*S _{n}* is said to have the

In this paper we classify the groups with the *k*-universal transversal
property (with the exception of two classes of 2-homogeneous groups) and the
(*k*−1,*k*)-homogeneous groups (for
2<*k*≤(*n*+1)/2). As a corollary of the classification we prove
that a (*k*−1,*k*)-homogeneous group is also
(*k*−2,*k*−1)-homogeneous, with two exceptions; and
similarly, but with no exceptions, groups having the *k*-universal
transversal property have the (*k*−1)-universal transversal property.

A corollary of all the previous results is a classification of the groups
that together with any rank *k* transformation on *X* generate a
regular semigroup (for 1≤*k*≤(*n*+1)/2).

The paper ends with a number of challenges for experts in number theory, group and/or semigroup theory, linear algebra and matrix theory.

Peter J. Cameron, Aftermath

I take a quick overview at the recent development of combinatorics and its current directions, as a discipline in its own right, as part of mathematics, and as part of science and wider society.

R. A. Bailey and Peter J. Cameron, Using graphs to find the best block designs

A statistician designing an experiment wants to get as much information as possible from the data gathered. Often this means the most precise estimate possible (that is, an estimate with minimum possible variance) of the unknown parameters. If there are several parameters, this can be interpreted in many ways: do we want to minimize the average variance, or the maximum variance, or the volume of a confidence region for the parameters?

In the case of block designs, these optimality criteria can be calculated from the concurrence graph of the design, and in many cases from its Laplacian eigenvalues. The Levi graph can also be used. The various criteria turn out to be closely connected with other properties of the graph as a network, such as number of spanning trees, isoperimetric number, and the sum of the resistances between pairs of vertices when the graph is regarded as an electrical network.

In this chapter, we discuss the notions of optimality for incomplete-block designs, explain the graph-theoretic connections, and prove some old and new results about optimality.

P. J. Cameron and D. A. Preece,
Three-factor decompositions of **U**_{n} with the generators
in arithmetic progression

Irrespective of whether *n* is prime, prime power with exponent >1,
or composite, the group **U**_{n} of units of
**Z**_{n} can sometimes be obtained as the direct product of cyclic groups generated by *x*, *x*+*k* and *x*+2*k*,
for *x,k*∈**Z**_{n}. Indeed, for many values of
*n*, many distinct 3-factor decompositions of this type exist. The
circumstances in which such decompositions exist are examined. Many
decompositions have additional interesting properties. We also look briefly
at decompositions of the multiplicative groups of finite fields.

Peter J. Cameron and Maximilien Gadouleau, Remoteness of permutation codes

We define a new parameter, called *remoteness*, of a subset of a finite
metric space. It is related to domination and is, in a sense, dual to covering
radius. We study this parameter in the symmetric group (with the Hamming
metric, where the distance between two permutations is the number of positions
in which they differ). We obtain a number of results for sets and groups of
permutations. In particular, the remoteness of a transitive permutation group
of degree *n* is either *n* or *n*−1, and we give a number
of results about which possibility occurs, though without resolving the
question completely.

Peter J. Cameron, Maximilien Gadouleau and Søren Riis, Combinatorial representations

This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any graph is representable over all alphabets of size larger than some number depending on the graph. We also provide a characterisation of families representable over a given alphabet. Then, we associate a rank function and a rank operator to any representation which help us determine some criteria for the functions used in a representation. While linearly representable matroids can be viewed as having representations via matrices with only one row, we conclude this paper by an investigation of representations via matrices with only two rows.

Peter J. Cameron, Dixon's Theorem and random synchronization

A transformation monoid on a set Ω is called *synchronizing* if
it contains an element of rank 1 (that is, mapping the whole of Ω
to a single point). In this paper, I tackle the question: given *n* and
*k*, what is the probability that the submonoid of the full transformation
monoid *T _{n}* generated by

The question has some similarities with a similar question about the probability
that the subgroup of *S _{n}* generated by

Following the technique of Dixon's theorem, we need to analyse the maximal
non-synchronizing submonoids of *T _{n}*. I develop a very close
connection
between transformation monoids and graphs, from which we obtain a description
of non-synchronizing monoids as endomorphism monoids of graphs satisfying some
very strong conditions. However, counting such graphs,
and dealing with the intersections of their endomorphism monoids, seems
difficult.

Peter J. Cameron, Christian Krattenthaler and Thomas W. Müller, Decomposable functors and the exponential principle, II

We develop a new setting for the exponential principle in the context of multisort species, where indecomposable objects are generated intrinsically instead of being given in advance. Our approach uses the language of functors and natural transformations (composition operators), and we show that, somewhat surprisingly, a single axiom for the composition already suffices to guarantee validity of the exponential formula. We provide various illustrations of our theory, among which are applications to the enumeration of (semi-)magic squares and (higher-dimensional) cubes.

Peter J. Cameron, Christian Krattenthaler and Thomas W. Müller, A note on higher-dimensional magic matrices

We provide exact and asymptotic formulae for the number of
unrestricted, respectively indecomposable, *d*-dimensional matrices
where the sum of all matrix entries with one coordinate fixed equals 2.

Adam Bohn, Peter J. Cameron and Peter Müller, Galois groups of multivariate Tutte polynomials

The multivariate Tutte polynomial *Z*^_{M} of a
matroid *M* is a generalisation of the standard two-variable version,
obtained by assigning a separate variable *v _{e}* to each element

P. J. Cameron (editor), Problems from BCC22

These problems were mostly presented at the problem session at the 22nd British Combinatorial Conference at St Andrews, on 10 July 2009. I have removed two problems that were solved before or during the session; problems which have been subsequently solved are retained and given a number which should not change and can be used to refer to them. Solved problems will not appear in the published version but will remain in this document with some indication of the solution.

P. J. Cameron, Generating a group by a transversal

I answer a question of Vivek Jain by showing that, if *H* is a core-free
subgroup of a finite group *G*, then there is a transversal
for *H* in *G* which generates *G*. The result can be
strengthened in a couple of ways: we may assume that the representative
of the coset *H* is the identity; or
we may relax the condition that *H* is core-free (but not too far). The
crucial ingredient in the proof is a theorem of Whiston on the maximum size
of an independent set in the symmetric group.

P. J. Cameron and V. Yildiz, Counting false values in truth tables of propositional formulae connected by implication

In this note we count the number of rows *f _{n}* with the
value "false" in
the truth tables of all bracketed formulae with

P. J. Cameron and D. A. Preece,
Three-factor decompositions of **U**_{n} with
the three generators in arithmetic progression

Irrespective of whether *n* is prime, prime power with exponent >1,
or composite, the group **U**_{n} of units of
**Z**_{n} can sometimes be
obtained as

whereU_{n}= (x) × (x+k) × (x+2k),

Robert F. Bailey and Peter J. Cameron, Base size, metric dimension and other invariants of groups and graphs

The base size of a permutation group, and the metric dimension of a graph, are both well-studied parameters which are closely related. We survey results on the relationship between the two, and with other, related parameters of groups, graphs, coherent configurations and association schemes. We also present some new results, including on the base sizes of wreath products in the product action, and on the metric dimension of Johnson and Kneser graphs.

Peter J. Cameron and Shamik Ghosh,
The power graph of a finite group, submitted to *Discrete Math.*

The *power graph* of a group is the graph whose vertex set is the group,
two elements being adjacent if one is a power of the other. We observe that
non-isomorphic finite groups may have isomorphic power graphs, but that finite
abelian groups with isomorphic power graphs must be isomorphic. We conjecture
that two finite groups with isomorphic power graphs have the same number of
elements of each order. We also show that the only finite group whose
automorphism group is the same as that of its power graph is the Klein group
of order 4.

Tatiana Gateva-Ivanova and Peter Cameron, Multipermutation solutions of the Yang–Baxter equation

Set-theoretic solutions of the Yang–Baxter equation form a meeting-ground
of mathematical physics, algebra and combinatorics. Such a solution consists
of a set *X*
and a function
*r*: *X*×*X* → *X*×*X* which satisfies the braid relation.
We examine solutions here
mainly from the point of view of finite permutation groups: a solution
gives rise to a map from *X* to the symmetric group Sym(*X*) on
*X* satisfying certain conditions.

Our results include many new constructions based on strong twisted union and wreath product, with an investigation of retracts and the multipermutation level and the solvable length of the groups defined by the solutions; and new results about decompositions and factorisations of the groups defined by invariant subsets of the solution.

R. A. Bailey and Peter J. Cameron,
Combinatorics of optimal designs,
*Surveys in Combinatorics 2009* (ed. S. Huczynska, J. D. Mitchell and
C. M. Roney-Dougal), London Math. Soc. Lecture Notes **365**,
Cambridge University Press 2009, pp. 19-73.

To a combinatorialist, a design is usually a 2-design (or balanced incomplete-block design). However, 2-designs do not necessarily exist in all cases where a statistician might wish to use one to design an experiment. As a result, statisticians need to consider structures much more general than the combinatorialist's designs, and to decide which one is "best" in a given situation. This leads to the theory of optimal design. There are several concepts of optimality, and no general consensus about which one to use in any particular situation.

For block designs with fixed block size *k*, all these optimality criteria
are determined by a graph, the *concurrence graph* of the design, and
more specifically, by the eigenvalues of the Laplacian matrix of the graph.
It turns out that the optimality criteria most used by statisticians
correspond to
properties of this graph which are interesting in other contexts:
D-optimality involves
maximizing the number of spanning trees; A-optimality involves minimizing
the sum of resistances between all pairs of terminals (when the graph is
regarded as an electrical circuit, with each edge being a one-ohm resistor);
and E-optimality involves maximizing the smallest eigenvalue of the Laplacian
(the corresponding graphs are likely to have good expansion and random walk
properties).
If you are familiar with these properties, you may expect
that related "nice" properties such as regularity and large girth (or
even symmetry) may tend to hold; some of our examples may come as a surprise!

The aim of this paper is to point out that the optimal design point of view unifies various topics in graph theory and design theory, and suggests some interesting open problems to which combinatorialists of all kinds might turn their expertise. We describe in some detail both the statistical background and the mathematics of various topics such as Laplace eigenvalues of graphs.

Peter J. Cameron,
Decompositions of complete multipartite graphs,
*Discrete Math.* **309** (2009), 4185-4186; doi:
10.1016/j.disc.2008.10.021

This paper answers a recent question of Dobson and Marušič by partitioning the edge set of a complete multipartite graph into two parts, both of which are edge sets of arc-transitive graphs, one primitive and the other imprimitive. The first member of the infinite family is the one constructed by Dobson and Marušič.

Peter J. Cameron,
Oligomorphic permutation groups,
to appear in *Perspectives in Mathematical Sciences*, ed.
N.S.N. Sastry, Mohan Delampady, B. Rajeev and T.S.S.R.K. Rao, Indian
Statistical Institute.

A permutation group *G* (acting on a set Omega, usually infinite)
is said to be *oligomorphic* if *G* has only finitely many orbits
on Omega^{n} (the set of *n*-tuples of elements of Omega).
Such groups
have traditionally been linked with model theory and combinatorial
enumeration; more recently their group-theoretic properties have been
studied, and links with graded algebras, Ramsey theory, topological dynamics,
and other areas have emerged.

This paper is a short summary of the subject, concentrating on the enumerative and algebraic aspects but with an account of group-theoretic properties. The first section gives an introduction to permutation groups and to some of the more specific topics we require, and the second describes the links to model theory and enumeration. We give a spread of examples, describe results on the growth rate of the counting functions, discuss a graded algebra associated with an oligomorphic group, and finally discuss group-theoretic properties such as simplicity, the small index property, and "almost-freeness".

Peter J. Cameron, Daniel Johannsen, Thomas Prellberg and Pascal Schweitzer,
Counting defective parking functions,
*Electronic J. Combinatorics*
**15(1)** (2008), #R92 (15pp).

Suppose that *n* drivers each choose a preferred parking space in a linear
car park with *m* spaces. Each driver goes to the chosen space and parks
there if it is free, and otherwise takes the first available space with
larger number (if any). If all drivers park successfully, the sequence of
choices is called a parking function. In general, if *k* drivers fail to
park, we have a *defective parking function* of *defect* *k*.
Let cp(*n,m,k*) be the number of such functions.

In this paper, we establish a recurrence relation for the numbers
cp(*n,m,k*), and
express this as an equation for a three-variable generating function.
We solve this equation using the kernel method, and extract the coefficients
explicitly: it turns out that the cumulative totals are partial sums in
Abel's binomial identity. Finally, we compute the asymptotics of
cp(*n,m,k*). In particular, for the case *m=n*, if choices are made
independently at random, the limiting distribution
of the defect (the number of drivers who fail to park), scaled by the
square root of *n*, is the Rayleigh distribution. On the other hand,
in case
*m*=omega(*n*), the probability that all
spaces are occupied tends asymptotically to one.

Peter J. Cameron and Ross Applegate,
Orbits on *n*-tuples,
*Communications in Algebra* **37** (2009), 269-275; doi:
10.1080/00927870802243739

A transitive (infinite) permutation group which has *m* orbits on ordered
pairs of distinct points has at least *m*^{n-1}
orbits on ordered *n*-tuples.
This is best possible, and groups attaining the bound can be characterised.

Peter J. Cameron and Priscila A. Kazanidis,
Cores of symmetric graphs,
*J. Australian Math. Soc.* **85** (2008), 145-154; doi:
10.1017/S1446788708000815

The core of a graph Γ is the smallest graph Δ which is homomorphically equivalent to Γ (that is, there exist homomorphisms in both directions). The core of Γ is unique up to isomorphism and is an induced subgraph of Γ.

We give a construction in some sense dual to the core. The
*hull* of a graph Γ is a graph containing Γ as a
spanning subgraph, admitting all the endomorphisms of Γ, and
having as core a complete graph of the same order as the core of
Γ. This construction is related to the notion of a
synchronizing permutation group which arises in semigroup theory; we
provide some more insight by characterizing these permutation groups
in terms of graphs.

It is known that the core of a vertex-transitive graph is vertex-transitive. In some cases we can make stronger statements: for example, if Γ is a nonedge-transitive graph, we show that either the core of Γ is complete, or Γ is its own core.

Rank 3 graphs are nonedge-transitive. We examine some families of these to decide which of the two alternatives for the core actually holds. We will see that this question is very difficult, being equivalent in some cases to unsolved questions in finite geometry (for example, about spreads, ovoids, and partitions into ovoids in polar spaces).

Peter J. Cameron,
A generalisation of *t*-designs,
*Discrete Math.* **309** (2009), 4835-4842; doi:
10.1016/j.disc.2008.07.005

This paper defines a class of designs which generalise
*t*-designs, resolvable designs, and orthogonal arrays. For the parameters
*t*=2, *k*=3 and λ=1, the designs in the class consist
of Steiner triple systems, Latin squares, and 1-factorisations of complete
graphs. For other values of *t* and *k*, we obtain *t*-designs,
Kirkman systems, large sets of Steiner triple systems, sets of mutually
orthogonal Latin squares, and (with a further generalisation) resolvable
2-designs and indeed much more general partitions of designs, as well
as orthogonal arrays over variable-length alphabets.

The Markov chain method of Jacobson and Matthews for choosing a random
Latin square extends naturally to Steiner triple systems and
1-factorisations of complete graphs, and indeed to
all designs in our class with *t*=2, *k*=3, and arbitrary
λ, although little is known about its convergence or even its
connectedness.

Peter J. Cameron and Sam Tarzi, Filters, topologies and groups from the random graph.

We investigate the filter generated by vertex neighbourhoods in the
countable random graph *R*, and two related topologies, with
emphasis on their automorphism groups. These include a number of highly
transitive groups containing Aut(*R*).

Peter Cameron and Natalia Iyudu,
Graphs of relations and Hilbert series,
*J. Symbolic Comput.* **42** (2007), 1066-1078.

We discuss certain combinatorial and counting problems related to
quadratic algebras. First we confirm the Anick conjecture on the minimal
Hilbert series for algebras given by *n* generators and
*n*(n-1)/2 relations for *n*≤7. Then we investigate
the combinatorial structure of the coloured graph associated with the
relations of an RIT algebra. Precise descriptions of graphs (maps)
corresponding to algebras with maximal Hilbert series are given in
certain cases. As a consequence it turns out, for example, that an
RIT algebra may have a maximal Hilbert series only if the components
of the graph associated with each colour are pairwise 2-isomorphic.

Robert F. Bailey and Peter J. Cameron,
On the single-orbit conjecture for uncoverings-by-bases,
*J. Group Theory* **11** (2008), 845-850; doi:
10.1515/JGT.2008.053

Let *G* be a permutation group acting on a finite set *Omega*.
An *uncovering-by-bases* (or UBB) for *B* is a set *U* of
bases for *G* such that any *r*-subsets of *Omega* is
disjoint from at least one base in *U*, where
*r* = [(*d*-1)/2], for *d* the minimum degree of
*G*. The *single-orbit conjecture* asserts that for any finite
permutation group *G* there exists a UBB for *G* contained in a
single orbit of *G* on its irredundant bases. We prove a case of this
conjecture, for when *G* is *k*-transitive and has a base of
size *k*+1. Furthermore, in the restricted case when *G* is
primitive and has a base of size *2*, we show how to construct a UBB
of minimum possible size.

Peter J. Cameron and Sam Tarzi,
On the automorphism group of the *m*-coloured random graph.

Let *R _{m}* be the (unique) universal homogeneous

Peter Cameron, Thomas Prellberg and Dudley Stark,
Asymptotic enumeration of 2-covers and line graphs,
*Discrete Math.*, in press; doi:
10.1016/j.disc.2008.09.008

In this paper we find asymptotic enumerations for the number of line graphs on
*n* labelled vertices and for different types of related combinatorial
objects called 2-covers.

We find that the number of 2-covers, *s _{n}*, and proper 2-covers,

whereB_{2n}2^{-n}exp(-½log(2n/logn))

B_{2n}2^{-n}n^{-½}exp(-[½log(2n/logn)]²).

In our proofs we use probabilistic arguments for the unrestricted types of 2-covers and and generating function methods for the restricted types of 2-covers and line graphs.

P. J. Cameron, Root systems and optimal block designs,
*Michigan Math. J.* **58** (2009), 181-194; doi:
10.1307/mmj/1242071687

Motivated by a question of C.-S. Cheng on optimal block designs, this paper describes the symmetric matrices with entries 0, +1 and -1, zero diagonal, least eigenvalue strictly greater than -2, and constant row sum. I also describe briefly the motivation for the question.

P. J. Cameron (editor), Problems from CGCS.

Most of these problems were presented at the conference on Combinatorics, Geometry and Computer Science, held at CIRM, Luminy, 2-4 May 2007. I have added one problem on a similar theme after the meeting.

The problems have been arranged so that those with similar themes occur together as far as possible.

P. J. Cameron, Permutation codes.

There are many analogies between subsets and permutations of a set, and in particular between sets of subsets and sets of permutations. The theories share many features, but there are also big differences. This paper is a survey of old and new results about sets (and groups) of permutations, concentrating on the analogies and on the relations to coding theory. Several open problems are described.

It is a pleasure to dedicate this paper to Michel Deza, who was a pioneer in the investigation of permutations from this point of view.

R. A. Bailey and P. J. Cameron,
What is a design? How should we classify them?
*Designs, Codes, Crypt* **44** (2007), 223-238; doi:
10.1007/s10623-007-9092-3

In 2001, the United Kingdom Engineering and Physical Sciences Research Council awarded the authors of this paper and Leonard Soicher a grant for "A Web-based resource for design theory". Planning how to put a catalogue of designs on the web forced us to think about the questions which are posed in the title of this paper.

P. J. Cameron and A. Rudvalis, A design and a geometry for the Fischer group
Fi_{22},
*Designs, Codes, Crypt.* **44** (2007), 11-14; doi:
10.1007/s10623-007-9041-1

The Fischer group Fi_{22} acts as a rank 3 group of
automorphisms of a symmetric 2-(14080,1444,148) design. This design does
not have a doubly transitive automorphism group, since there is a partial
linear space with lines
of size 4 defined combinatorially from the design and preserved by its
automorphism group. We investigate this geometry and determine the structure
of various subspaces of it.

C. Buchheim, P. J. Cameron and T. Wu, On the subgroup distance problem,
*Discrete Math.* **309** (2009), 962-968; doi:
10.1016/j.disc.2008.01.036

We investigate the computational complexity of finding an element of a
permutation group *H* contained in *S _{n}* with minimal
distance to a given element

Peter J. Cameron and D. Lockett,
Posets, homomorphisms and homogeneity,
*Discrete Math.*, in press; doi:
10.1016/j.disc.2009.04.027

Jarik Nešetřil suggested to the first author the investigation of notions of homogeneity for relational structures, where "isomorphism" is replaced by "homomorphism" in the definition. Here we look in detail at what happens for posets. For the strict order, all five generalisations of homogeneity coincide, and we give a characterisation of the countable structures that arise. For the non-strict order, there is an additional class. The "generic poset" plays an important role in the investigation.

Peter J. Cameron and Leonard H. Soicher,
Block intersection polynomials,
*Bull. London Math. Soc.* **39** (2007), 559-564; doi:
10.1112/blms/bdm034

We introduce the block intersection polynomial, which is constructed using
certain information about a block design with respect to a subset *S*
of its point-set, and then provides further information about the number
of blocks intersecting *S* in exactly *i* points, for
*i* = 0,...,|*S*|.
We also discuss some applications of block intersection polynomials,
including bounding the multiplicity of a block in a
*t*-(*v*,*k*,λ) design and in a resolvable
*t*-(*v*,*k*,λ) design.

P. J. Cameron and S. Tarzi, Limits of cubes,
*Topology and its Applications* **155** (2008), 1454-1461.

The celebrated Urysohn space is the completion of a countable universal homogeneous metric space which can itself be built as a direct limit of finite metric spaces. It is our purpose in this paper to give another example of a space constructed in this way, where the finite spaces are scaled cubes. The resulting countable space provides a context for a direct limit of finite symmetric groups with strictly diagonal embeddings, acting naturally on a module which additively is the "Nim field" (the quadratic closure of the field of order 2). Its completion is familiar in another guise: it is the set of Lebesgue-measurable subsets of the unit interval modulo null sets. We describe the isometry groups of these spaces and some interesting subgroups, and give some generalisations and speculations.

P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini and A. Winter,
On the quantum chromatic number of a graph,
*Electronic Journal of
Combinatorics* **14(1)** (2007), #R82 (15pp).

We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince an interrogator with certainty that they have a colouring of the graph.

After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is 2, nor if it is 3 in a restricted quantum model; on the other hand we exhibit a graph on 18 vertices and 44 edges with chromatic number 5 and quantum chromatic number 4.

P. J. Cameron and T. Wu, The complexity of the Weight Problem for permutation and matrix groups,

Given a metric *d* on a permutation group *G*, the corresponding
weight problem is to decide whether there exists an element
*g* in *G*
such that *d*(*g,e*)=*k* for some given value
*k* of *d*. In this paper
we show that this problem is **NP**-complete for many well
known metrics. We also consider the problem of finding the maximum
or minimum weight of an element of *G*.

P. J. Cameron, M. Kang and D. Stark, Random preorders and alignments,

A preorder consists of linearly ordered equivalence classes called
*blocks*, and an alignment is a sequence of cycles on *n*
labelled elements.
We investigate the block structure of a random preorder
chosen uniformly at random among all preorders on *n* elements,
and also the distribution of cycles in a random alignment chosen uniformly
at random among all alignments on *n* elements, as *n* tends
to infinity.

P. J. Cameron and K. K. Kayibi, Orbital chromatic and flow roots,

The chromatic polynomial *P*_{Γ}(*x*)
of a graph Γ is a polynomial whose value at the positive
integer *k* is the number
of proper *k*-colourings of Γ. If *G* is
a group of automorphisms of Γ, then there is a polynomial
*OP*_{Γ,G}(*x*), whose value at
the positive integer *k* is the number of orbits
of *G* on proper *k*-colourings of Γ.

It is known there are no real negative chromatic
roots, but they are dense in [32/27,infty). Here we
discuss the location of real orbital chromatic roots. We show,
for example, that they are dense in **R**, but under certain
hypotheses, there are zero-free regions. Our hypotheses include
parity conditions on the elements of *G* and also some
special types of graphs and groups.

We also look at orbital flow roots. Here things are more complicated because the orbit count is given by a multivariate polynomial; but it has a natural univariate specialisation, and we show that the roots of these polynomials are dense in the negative real axis.

R. A. Bailey, Peter J. Cameron and Robert Connelly, Sudoku, gerechte designs, resolutions, affine space, spreads, reguli, and Hamming codes,

The subjects of the title are all connected. The purpose of this paper is
to explain the relation between *Sudoku solutions*
(filled Sudoku grids) and the more general
(and earlier) concept of *gerechte designs*, and to give some
examples of these. Constructing gerechte designs can be viewed as
finding resolutions of a block design constructed from the relevant grid.
We give an upper bound for the number of mutually orthogonal Sudoku solutions,
and a smaller upper bound if certain additional constraints are prescribed,
and show by a geometric construction using spreads (explicitly realised by
Hamming codes) that the bounds are attained. We generalise the bounds and
the constructions to other situations. We explain the statistical background
and construct a few Sudoku solutions with remarkable additional properties.
For one of these types, which we call "symmetric Sudoku solutions",
we give a construction,
and an elementary proof that there are just two inequivalent solutions;
the proofs are based on projective and affine geometry over GF(3) and
the properties of the Hamming code of length 4 over GF(3). We also
explain the statistical considerations behind gerechte designs, and
construct some Sudoku solutions which have good statistical properties.

Peter Cameron, Javier Cilleruelo and Oriol Serra, On monochromatic solutions of equations in groups,

We show that the number of monochromatic solutions of the equation
*x*_{1}^{α1}*x*_{2}^{α2}...*x _{r}*

Peter Cameron, Thomas Prellberg and Dudley Stark, Asymptotic enumeration of incidence matrices,

We discuss the problem of counting *incidence matrices*, i.e., zero-one
matrices with no zero rows or columns. Using different approaches we give
three different proofs for the leading asymptotics for the number of matrices
with *n* ones as *n* tends to infinity. We also give refined
results for the number of *i* × *j* matrices with
*n* ones.

Peter Cameron, Thomas Prellberg and Dudley Stark, Asymptotics for incidence matrix classes,

We define *incidence matrices* to be zero-one matrices
with no zero rows or columns. We are interested in counting
incidence matrices with a given number of ones, irrespective
of the number of rows or columns.
A classification of incidence matrices is considered
for which conditions of symmetry by transposition,
having no repeated rows/columns,
or identification by permutation of rows/columns are imposed.
We find asymptotics and relationships for the number of matrices
with *n* ones in some of these classes as *n* tends to infinity.

R. A. Bailey and Peter J. Cameron, A family of balanced incomplete-block designs with repeated blocks on which general linear groups act,

We give two constructions of a balanced incomplete-block design discovered by van Lint: the design has parameters (13,39,15,5,5), and has repeated blocks and an automorphism group of order 240. One of these methods can be generalised to produce a large class of designs with the properties of the title.

P. J. Cameron, Aspects of infinite permutation groups,

Until 1980, there was no such subgroup as `infinite permutation groups', according to the Mathematics Subject Classification: permutation groups were assumed to be finite. There were a few papers, and a set of lecture notes by Wielandt, from the 1950s.

Now, however, there are far more papers on the topic than can possibly be summarised in an article like this one.

I shall concentrate on a few topics, following the pattern of my conference lectures: the random graph (a case study); homogeneous relational structures (a powerful construction technique for interesting permutation groups); oligomorphic permutation groups (where the relations with other areas such as logic and combinatorics are clearest, and where a number of interesting enumerative questions arise); and the Urysohn space (another case study). I have preceded this with a short section introducing the language of permutation group theory, and I conclude with briefer accounts of a couple of topics that didn't make the cut for the lectures (maximal subgroups of the symmetric group, and Jordan groups).

I have highlighted a few specific open problems in the text. It will be clear that there are many wide areas needing investigation!

P. J. Cameron, B. Jackson and J. Rudd, Orbit-counting polynomials for graphs and codes,

We construct an "orbital Tutte polynomial" associated with a dual pair *M*
and *M** of matrices over a principal ideal domain *R*
and a group *G*
of automorphisms of the row spaces of the matrices. The polynomial has two
sequences of variables, each sequence indexed by associate classes of elements
of *R*.

In the case where *M* is the signed vertex-edge
incidence matrix of a graph Γ over
the ring of integers, the orbital Tutte polynomial specialises to count
orbits of *G* on proper colourings of Γ or on nowhere-zero
flows or tensions on Γ with values in an abelian group *A*.
(In the case of flows, for example, we must substitute for the variable
*x _{i}*
the number of solutions of the equation

In the case where *M* is the generator matrix of a linear code over
GF(*q*), the orbital Tutte polynomial specialises to count orbits of
*G* on words of given weight in *C* or its dual.

P. J. Cameron, J. Sheehan and P. Spiga, Semiregular automorphisms of vertex-transitive cubic graphs,

An old conjecture of Marusic, Jordan and Klin asserts that any finite
vertex-transitive graph has a non-trivial semiregular automorphism.
Marusic and Scapellato proved this for cubic graphs. For these
graphs, we make a stronger conjecture, to the effect that there is a
semiregular automorphism of order tending to infinity with *n*.
We prove that there is one of order greater than 2.

P. J. Cameron and D. S. Stark, Random preorders

A random preorder on *n* elements
consists of linearly ordered equivalence classes called
*blocks*. We investigate the block structure of a preorder
chosen uniformly at random from all preorders on *n* elements as
*n* tends to infinity.

P. J. Cameron, Embedding partial Steiner triple systems so that their automorphisms extend,

It is shown that there is a function *g* on the natural numbers such that
a partial Steiner triple system *U* on *u* points can be embedded
in a Steiner triple system *V* on *v* points, in such a way that
all automorphisms of *U* can be extended to *V*, for every
admissible *v* satisfying *v* > *g*(*u*).
We find exponential upper and lower bounds for *g*.

S. Akbari, P. J. Cameron and G. B. Khosrovshahi, Ranks and signatures of adjacency matrices.

A graph is said to be reduced if no two vertices have the same set
of neighbours. It is well known that for a given natural number
*r*, there are finitely many reduced graphs of rank *r*. Let
*m*(*r*) denote the number of vertices of the largest reduced graph
of rank *r*. We present two constructions (the first due to Kotlov and
Lovász in 1996) which show that for positive *r*,

and we conjecture that the bounds are attained.m(r) ≥ 2^{(r+2)/2}-1 ifris even,

m(r) ≥ 5.2^{(r-3)/2}-1 ifris odd,

It is known that a number of important graph-theoretic parameters are bounded by a function of the rank of a graph and the rank is bounded by a function of the number t of negative eigenvalues. We present deeper insight in this matter.

We also report on the determination of all reduced graphs with rank at most 7, and give information of the classification by rank and signature up to rank 7. This also gives (at least implicitly) an exact enumeration of all graphs with rank at most 7. We have also determined the largest reduced graphs of rank 8.

Peter J. Cameron, Finite geometry and permutation groups: some polynomial links,

Any set of points in a finite projective space PG(*n,q*) defines a matroid
which is representable over GF(*q*). The Tutte polynomial of the matroid is
a two-variable polynomial which includes a lot of numerical information about
the configuration of points. For example, it determines the weight enumerator
of the code associated with the point set, and hence the cardinalities of
hyperplane sections of the set.

Another polynomial used in enumeration is the cycle index of a permutation group, which includes information about the number of orbits of the group on various configurations. This is the subject of a well-developed theory.

The aim (not yet realised) of the research reported here is to combine the Tutte polynomial of a matroid with the cycle index of any group acting on the matroid to obtain a more general polynomial which tells us about the number of orbits of the group on configurations counted by the Tutte polynomial.

The paper includes an introductory exposition of all these topics.

P. J. Cameron and A. M. Vershik, Some isometry groups of the Urysohn space,

We construct various isometry groups of Urysohn space (the unique complete separable metric space which is universal and homogeneous), including abelian groups which act transitively, and free groups which are dense in the full isometry group.

Peter J. Cameron and Pablo Spiga, Min-wise independent groups with respect to any linear order,

A finite permutation group *G* on a linearly ordered set
*Omega* is said to
be a *k*-min-wise independent group, *k*-MWI for short, if
Pr(min(pi(*X*))=pi(*x*))=1/|*X*| for every subset
*X* of *Omega* such
that |*X*|≤*k* and for every *x* in *X*.
We are concerned with the
case of *k*-MWI groups for any linear order. Indeed, we prove that
a permutation group *G* is *k*-MWI with respect to any linear
order if and only if for every *h*≤*k* and for every
*h*-set *X*
the group *G _{X}* is transitive on

Peter Cameron and Norbert Knarr, Tubes in PG(3,

A tube (resp. an oval tube) in PG(3,*q*) is a pair
*T* = {L,*L*}, where {L} *Union L*
is a collection of mutually disjoint lines of PG(3,*q*) such that for
each plane *pi* of PG(3,*q*) containing
L the intersection of *pi* with the lines of *L* is a hyperoval
(resp. an oval). The line L is called the axis of *T*. We show that
every tube for *q* even and every oval tube for *q* odd can be
naturally embedded into a regular spread and hence admits a group of
automorphisms which fixes every element of *T* and acts regularly on
each of them. For *q* odd we obtain a classification of oval tubes up to
projective equivalence. Furthermore, we characterize the reguli in
PG(3,*q*), for *q* odd, as oval tubes which admit more than one axis.

P. J. Cameron and J. Nesetril, Homomorphism-homogeneous relational structures,

We study relational structures (especially graphs and posets) which satisfy the analogue of homogeneity but for homomorphisms rather than isomorphisms. The picture is rather different. Our main results are partial characterisations of countable graphs and posets with this property; an analogue of Fraissé's Theorem; and representations of monoids as endomorphism monoids of such structures.

R. A. Bailey and Peter J. Cameron, Crested products of association schemes,

In this paper, we define a new type of product of association schemes
(and of the related objects, permutation groups and orthogonal block
structures), which generalizes the direct and wreath products (which
are referred to as "crossing" and "nesting" in the statistical
literature.) Given two association schemes *Q _{r}* for

The definition can be generalized to association schemes with families of inherent partitions, or permutation groups with families of intransitive normal subgroups. This time the correspondence is not so straightforward, and works as expected only if the inherent partitions (or orbit partitions) form a distributive lattice.

We conclude with some open problems.

R. A. Bailey, Peter J. Cameron, Peter Dobcsányi, John P. Morgan and Leonard H. Soicher, Designs on the Web,

In 2001, the United Kingdom Engineering and Physical Sciences Research Council awarded three of the authors of this paper a grant for "A Web-based resource for design theory". As the project developed, we have had to face a number of problems, ranging from fundamental questions such as "What is a design?", through research topics such as "How should the concept of partial balance be extended to designs which do not have constant block size?", to more practical problems concerning what format we should use to store designs. This paper gives a brief description of the project to date, concentrating on theoretical questions about designs and their classification.

A. E. Brouwer, Peter J. Cameron, W. H. Haemers and D. A. Preece, Self-dual, not self-polar,

The smallest number of points of an incidence structure which is self-dual but not self-polar is 7. For non-binary structures (where a "point" may occur more than once in a "block") the number is 6.

Peter J. Cameron and Charles R. Johnson, The number of equivalence classes of symmetric sign patterns,

This paper shows that the number of sign patterns of totally non-zero symmetric
*n*-by-*n* matrices, up to conjugation by monomial matrices and
negation, is equal to the number of unlabelled graphs on *n* vertices.

P. J. Cameron, H. R. Maimani, G. R. Omidi and B. Tayfeh-Rezaie, 3-designs from PSL(2,

The group PSL(2,*q*) is 3-homogeneous on the
projective line when *q* is a prime power congruent to 3 modulo
4 and therefore it can be used to construct 3-designs. In
this paper, we determine all 3-designs admitting PSL(2,*q*) with
block size not congruent to 0 or 1 modulo *p* where
*q=p ^{n}*.

Peter J. Cameron and Alexander W. Dent, Orbit-homogeneity,

We introduce the concept of orbit-homogeneity of permutation
groups: a group *G* is orbit *t*-homogeneous if two sets of
cardinality *t* lie in the same orbit of *G* whenever their
intersections with each *G*-orbit have the same cardinality. For
transitive groups, this coincides with the usual notion of
*t*-homogeneity. This concept is also compatible with the idea of
partition transitivity introduced by Martin and Sagan.

We show that any group generated by orbit *t*-homogeneous
subgroups is orbit *t*-homogeneous, and that the condition becomes
stronger as *t* increases up to [*n*/2], where *n* is
the degree. So any group *G* has a unique maximal orbit
*t*-homogeneous subgroup Omega_{t}(*G*), and
Omega_{t}(*G*) ≤ Omega_{t-1}(*G*).

We also give some structural results for orbit *t*-homogeneous
groups and a number of examples.

Peter J. Cameron and Thomas W. Müller, A descent principle in modular subgroup arithmetic,

We establish and comment on a surprising relationship between the
behaviour modulo a prime *p* of the number *s _{n}*(

Peter J. Cameron and Ian M. Wanless, Covering radius for sets of permutations,

We study the covering radius of sets of permutations with respect to the
Hamming distance. Let *f*(*n,s*) be the smallest number
*m* for which there is a set of *m* permutations in
*S _{n}*
with covering radius at most

We find *f*(*n*,1) exactly and bounds on *f*(*n,s*) for
*s*>1. For *s*=2, our
bounds are linear in *n*. This case relates to classical conjectures by
Ryser and Brualdi on transversals of Latin squares and to more recent work
by Kézdy and Snevily. We discuss a flaw in Derienko's published proof
of Brualdi's conjecture. We also show that every latin square contains a set
of entries which meets each row and column exactly once while using no
symbol more than twice.

In the case where the permutations form a group, we give necessary and
sufficient conditions for the covering radius to be exactly *n*. If the
group is *t*-transitive, then its covering radius is at most *n-t*,
and we give a partial determination of groups meeting this bound.

We give some results on the covering radius of specific groups. For
the group PGL(2,*q*), the question can be phrased in geometric terms,
concerning configurations in the Minkowski plane over GF(*q*) meeting
every generator once and every conic in at most *s* points, where *s*
is as small as possible. We give an exact answer except in the case
where *q* is congruent to 1 mod 6.
The paper concludes with some remarks about the relation between packing and
covering radii for permutations.

Peter J. Cameron and Thomas W. Müller, A cohomological property of finite

We define and study a certain cohomological property of finite
*p*-groups (to be of `Frobenius type'), which is implicit in
Frobenius' theorem (Berl. Sitz. 1895, 981-993) concerning the equation
*X ^{m}*=1 and Philip Hall's subsequent work
(Proc. London Math. Soc. 40, 468-501) on
equations in finite groups. Hall's twisted version (loc. cit.,
Theorem 1.6) of Frobenius' theorem implies that each cyclic group
of prime power order is of Frobenius type. We show that this
property in fact pertains to every finite

Peter J. Cameron, Daniele A. Gewurz and Francesca Merola, Product action,

This paper studies the cycle indices of products of permutation groups.
The main focus is on the product action of the direct product of
permutation groups. The number of orbits of the product on *n*-tuples is
trivial to compute from the numbers of orbits of the factors; on the other
hand, computing the cycle index of the product is more intricate.
Reconciling the two computations leads to some interesting questions about
substitutions in formal power series. We also discuss what happens for
infinite (oligomorphic) groups and give detailed examples. Finally, we
briefly turn our attention to generalised wreath products, which are a
common generalisation of both the direct product with the product action
and the wreath product with the imprimitive action.

Peter J. Cameron and C. Y. Ku, Intersecting families of permutations,

Let *S _{n}* be the symmetric group on the set

Peter J. Cameron and Sam Tarzi, Group actions on amorphous sets

A set *U* is amorphous if every subset of *U* is finite or cofinite;
an amorphous set is bounded if there is a natural number *n* such that
every non-trivial partition of *U* has all but finitely many parts of
size *m*, for some *m*≤*n*. Our main result asserts that,
if *U* is bounded amorphous, then the symmetric group on *U*
modulo the group of finitary permutations is isomorphic to a finite group,
and that every finite group can occur in this situation. We also obtain some
results about the structure of the finitary symmetric group on an amorphous set.
Our results depend heavily on the classification of bounded amorphous
sets by John Truss.

Peter J. Cameron and Sam Tarzi, Switching with more than two colours,

The operation of switching a finite graph was introduced by Seidel, in the
study of strongly regular graphs. We may conveniently regard a graph as being
a 2-colouring of a complete graph; then the extension to switching of an
*m*-coloured complete graph is easy to define. However, the situation
is very different. For *m*>2, all *m*-coloured graphs lie in
the same switching class. However, there are still interesting things to
say, especially in the infinite case.

This paper presents the basic theory of switching with more than two colours. In the finite case, all graphs on a given set of vertices are equivalent under switching, and we determine the structure of the switching group and show that its extension by the symmetric group on the vertex set is primitive.

In the infinite case, there is more than one switching class; we determine
all those for which the group of switching automorphisms is the symmetric
group. We also exhibit some other cases (including the random *m*-coloured
complete graph) where the group of switching-automorphisms is highly
transitive.

Finally we consider briefly the case where not all switchings are allowed. For convenience, we suppose that there are three colours of which two may be switched. We show that, in the case of almost all finite random graphs, the analogue of the bijection between switching classes and two-graphs holds.

Peter J. Cameron, Homogeneous permutations,

There are just five Fraissé classes of permutations (apart from the trivial class of permutations of a singleton set); these are the identity permutations, ``reversing'' permutations, ``composites'' (in either order) of these two classes, and all permutations. The paper also discusses infinite generalisations of permutations, and the connection with Fraissé's theory of countable homogeneous structures, and states a number of open problems. Links with enumeration results, and the analogous result for circular permutations, are also described.

Peter J. Cameron and Ph. Cara, Independent generating sets and geometries for symmetric groups,

Julius Whiston showed that the size of an independent generating set in the
symmetric group *S _{n}* is at most

Peter J. Cameron, Cycle index, weight enumerator and Tutte polynomial,

With every linear code is associated a permutation group whose cycle index is the weight enumerator of the code (up to normalisation).

There is a class of permutation groups
(the *IBIS groups*) which includes the groups obtained from codes as
above. With every IBIS group is associated a matroid; in the case of a code
group, the matroid differs only trivially from that which arises from the
code. In this case, the Tutte polynomial of the code specialises to the
weight enumerator (by Greene's Theorem), and hence also to the cycle index.
However, in another subclass of IBIS groups, the *base-transitive groups*,
the Tutte polynomial can be derived from the cycle index but not
vice versa.

I propose a polynomial for IBIS groups which generalises both Tutte polynomial and cycle index.

Peter J. Cameron, Random strongly regular graphs?

Strongly regular graphs lie on the cusp between highly structured and unstructured. For example, there is a unique strongly regular graph with parameters (36,10,4,2), but there are 32548 non-isomorphic graphs with parameters (36,15,6,6). (The first assertion is a special case of a theorem of Shrikhande, while the second is the result of a computer search by McKay and Spence.) In the light of this, it will be difficult to develop a theory of random strongly regular graphs!

For certain values of the parameters, we have at least one prerequisite for a theory of random objects: there should be very many of them (e.g. superexponentially many). Two other features we would like are a method to sample from the uniform distribution (this is known in a couple of special cases) and information about how various graph parameters behave as random variables on the uniform distribution. Very little is known but there are a few recent results and some interesting problems.

This paper develops no general theory, but explores a few examples and techniques which can be applied in some cases.

Thomason has developed a theory of "pseudo-random graphs" which he calls
(*p*,α)-jumbled graphs. Some of these graphs are strongly regular,
but they are very special strongly regular graphs. I conclude with some
speculation about "random jumbled graphs".

Anthony Bonato, Peter Cameron, Dejan Delic and Stéphan Thomassé, Generalized pigeonhole properties of graphs and oriented graphs,

A relational structure *A* satisfies the P(*n,k*) property if
whenever the vertex set of *A* is partitioned into *n* nonempty
parts, the substructure induced by the union of some *k* of the parts
is isomorphic to *A*. The P(2,1) property is just the pigeonhole
property (P) introduced by P. Cameron, "Aspects of the Random Graph",
and studied by the first three authors. We classify the countable graphs,
tournaments and oriented graphs with the P(3,2) property.

Peter J. Cameron and Bridget S. Webb, What is an infinite design?

It is usually assumed that an *infinite design* is a *design with
infinitely many points*. This encompasses a myriad of structures,
some nice and others not. In this paper we consider examples of structures that
we would not like to call designs, and investigate additional conditions
that exclude such anomalous structures. In particular, we expect a design
to be regular, the complement of a design to be a design, and a
*t*-design to be an *s* design for all *s* less than *t*.
These are all properties that can be taken for granted with finite designs,
and for infinite Steiner systems. We present a new definition of an
infinite *t*-design, and give examples of structures that satisfy
this definition. We note that infinite designs considered in the
literature to date satisfy our definition. We show that infinite design
theory does not always mirror finite design theory; for example, there
are designs with *v* > *b*.

Peter J. Cameron, Coherent configurations, association schemes and permutation groups, pp. 55-71 in

*Coherent configurations* are combinatorial objects invented for the
purpose of studying finite permutation groups; every permutation group which
is not doubly transitive preserves a non-trivial coherent configuration.
However, symmetric coherent configurations have a much longer history, having
been used in statistics under the name of *association schemes*.

The relationship between permutation groups and association schemes is quite subtle; there are groups which preserve no non-trivial association scheme, and other groups for which there is not a unique minimal association scheme.

This paper gives a brief outline of the theory of coherent configurations and association schemes, and reports on some recent work on the connection between association schemes and permutation groups.

Priscila P. Alejandro, R. A. Bailey and Peter J. Cameron, Association schemes and permutation groups,

Every permutation group which is not 2-transitive acts on a nontrivial
coherent configuration, but the question of which permutation groups *G*
act on nontrivial association schemes (symmetric coherent configurations) is
considerably more subtle. A closely related question is: when is there a
unique minimal *G*-invariant association scheme? We examine these
questions, and relate them to more familiar concepts of permutation group
theory (such as generous transitivity) and association scheme theory (such as
stratifiability).

Our main results are the determination of all regular groups having a unique
minimal association scheme, and a classification of groups with no
non-trivial association scheme. The latter must be primitive, and are either
2-homogeneous, almost simple, or of diagonal type. The diagonal groups have
some very interesting features, and we examine them further. Among other
things we show that a diagonal group with non-abelian base group cannot be
stratifiable if it has ten or more factors, or generously transitive if it
has nine or more; and we characterise the quaternion group *Q*_{8}
as the unique non-abelian group *T* such that a diagonal group with eight
factors *T* is generously transitive.

Peter J. Cameron and Dudley Stark, A prolific construction of graphs with the

A graph is *n*-e.c. (*n*-existentially closed) if for every pair
of subsets *U*, *W* of the vertex set *V* of the graph
such that *U* and *W* are disjoint and
|*U*|+|*W*|=*n*, there is a vertex *v* (not in *U*
or *W*) such all edges between *v* and *U* are present and
no edges between *v* and *W* are present. A graph is strongly regular
if it is a regular graph such that the number of
vertices mutually adjacent to a pair of vertices *v*_{1},
*v*_{2} depends
only on whether or not *v*_{1} and *v*_{2} are
adjacent in the graph.

The only strongly regular graphs that are known to be *n*-e.c. for large
*n* are the Paley graphs.
Recently D. G. Fon-Der-Flaass has found prolific
constructions of strongly regular graphs using affine designs.
He notes that some of these constructions were also studied by Wallis.
By taking the affine designs
to be Hadamard designs obtained from
Paley tournaments, we use probabilistic methods to show that many
non-isomorphic strongly regular *n*-e.c. graphs of order
(*q*+1)^{2} exist whenever *q* is a prime power at least
16*n*^{2}2^{2n} and congruent to
3 mod 4.

Peter J. Cameron, Strongly regular graphs, draft.

Strongly regular graphs form an important class of graphs which lie somewhere between the highly structured and the apparently random. This chapter gives an introduction to these graphs with pointers to more detailed surveys of particular topics.

Peter J. Cameron, Automorphisms of graphs, draft

This chapter surveys automorphisms of finite graphs, concentrating on the asymmetry of typical graphs, prescribing automorphism groups (as either permutation groups or abstract groups), and special properties of vertex-transitive graphs and related classes. There are short digressions on infinite graphs and graph homomorphisms.

Peter J. Cameron, Multi-letter Youden rectangles from quadratic forms,

Some infinite families of systems of linked symmetric designs
(or SLSDs, for short) were constructed by Cameron and
Seidel using quadratic and bilinear forms over GF(2).
The smallest of these systems was used by Preece and Cameron to
construct certain designs (which they called fully-balanced
hyper-graeco-latin Youden "squares"). The purpose of this paper is to
construct an infinite sequence of closely related designs (here called
*multi-letter Youden rectangles*) from the SLSDs of Cameron and Seidel.
These rectangles are *k* × *v*, with
*v*=2^{2n} and
*k=*2^{2n-1}±2^{n-1}.
The paper also provides a non-trivial example of how to translate from the
combinatorial view of designs (sets with incidence relations) to the
statistical (sets with partitions).

Peter J. Cameron, Topology in permutation groups, in

This paper is a survey of some topological aspects of permutation groups, especially concerning the question: "What does it tell us about a permutation group if it is a group of homeomorphisms of a topology?" This topic is not unrelated to a natural topology on the symmetric group, that of pointwise convergence; this connection is also discussed. The main new result of the paper is an elementary proof of part of a theorem of Macpherson and Praeger, according to which a group which preserves no non-trivial topology is highly transitive.

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,

A transitive finite permutation group is called *elusive* if it
contains no non-trivial semiregular subgroup. The purpose of this paper
is to collect known information about elusive groups. The main results
are recursive constructions of elusive permutation groups,
using various product operations and affine group constructions.
We also include a brief historical introduction and a list of known
elusive groups. In a sequel, Giudici determines all the
quasiprimitive elusive groups.

Part of the motivation for studying this class of groups is a conjecture due to Marusic, Jordan and Klin, asserting that there is no elusive 2-closed permutation group. We show that the constructions given here will not build counterexamples to this conjecture.

Peter J. Cameron, Fixed points and cycles, pp. 49-60 in

This paper presents a tapas of results on fixed points and cycles in permutation groups, arising in such disparate areas as matrix group recognition, Brauer groups, Latin squares, and relational databases.

DVI or PostScript

Peter J. Cameron, The random graph revisited, in

The random graph, or Rado's graph (the unique countable homogeneous graph) has made an appearance in many parts of mathematics since its first occurrences in the early 1960s. In this paper I will discuss some old and new results on this remarkable structure.

DVI or PostScript

Peter J. Cameron, Codes, matroids and trellises, Combinatorics 2000 (Gaeta, May 2000).

There is a natural bijection between representable matroids and linear codes over a given field, which is not as well known as it ought to be. An early result on this is Greene's theorem asserting that the weight enumerator of the code is a specialisation of the Tutte polynomial of the matroid. This connection also throws light on the minimal trellis for decoding a given code, and gives new results (and easier proofs of old results) on trellis complexity.

DVI or PostScript

Peter J. Cameron, Partitions and permutations,

With any permutation *g* of a set *Omega* is associated a partition
of *Omega* into the cycles of *g*. What information do we get
about a group *G* of permutations if we know either the set or the
multiset of partitions of *Omega*, or of partitions of *n*
(the cardinality of *Omega*), which arise as the cycle
partitions of its elements? Some partial answers to these questions are
given.

Peter J. Cameron, The random graph has the strong small index property,

Hodges *et al.* showed that the countable random graph has
the small index property. The stronger result of the title is
deduced from this and a general theorem about permutation groups.
A consequence is that the automorphism group of the random graph
is not isomorphic to the automorphism group of any other countable
homogeneous graph or digraph.

Peter J. Cameron, Permutation groups whose non-identity elements have

In this note I prove an asymptotic structure theorem for groups with the
property that any non-identity element fixes exactly *k* points. I also
look briefly at the infinite analogue, and at a conjectured analogue for
groups with prescribed sets of fixed-point numbers.

DVI or PostScript

Peter J. Cameron, Sequences realized by oligomorphic permutation groups,

The purpose of this paper is to identify, as far as possible, those
sequences in the
Encyclopedia of Integer Sequences which count orbits
of an infinite permutation group acting on *n*-sets or
*n*-tuples of elements of the permutation domain. The paper
also provides an introduction to the properties of such sequences
and their relations with combinatorial enumeration problems.

Peter J. Cameron, Permutations, pp. 205-239 in

This paper is a survey of some combinatorial problems related to permutations and permutation groups. It is inspired by the work of Paul Erdős in two ways. One one hand, I present some partial extensions of the seminal work of Erdős and Turán on random permutations, to groups other than the symmetric group. On the other, many of the topics considered can be regarded as analogues for sets of permutations of results on set-systems (or hypergraphs) springing from the Erdős-Ko-Rado theorem.

I begin with the celebrated Orbit-Counting Lemma, and a generalisation
which connect orbits of a group on *n*-tuples with the probability
generating function for fixed points of its elements. Various results
and problems on derangements (fixed-point-free elements) are also given.
In the next section, I turn from fixed points to cycles. Observing that
the cycle index is the probability generating function for cycle structure,
we recover the earlier theorem, as well as a recent result of Parker.
Next I survey some extremal results for sets or groups of
permutations with prescribed distances (distance being defined
in terms of fixed points). After a brief discussion of the semilattice
of subpermutations (partial permutations), I conclude with a
concept to replace that of "random permutation" in the infinite
case: for countable sets, there is a unique such object (this is
the analogue of the Erdős-Rényi theorem on the countable
random graph).

AMS 05 A 05

**Note:** An update on the problems in this paper is available
here.

Peter Cameron and Wilfrid Hodges, Some combinatorics of imperfect information,

We can use the compositional semantics of Hodges
to show that any compositional semantics for
logics of imperfect information must obey certain
constraints on the number of semantically inequivalent
formulas. As a corollary, there is no compositional
semantics for the "independence-friendly" logic of
Hintikka and Sandu (henceforth IF) in which the
interpretation in a structure *A* of each 1-ary formula
is a subset of the domain of *A* (Corollary 14
proves this and more). After a fashion, this
rescues a claim of Hintikka and provides the proof which
he lacked:

... there is no realistic hope of formulating compositional truth-conditions for [sentences of IF], even though I have not given a strict impossibility proof to that effect.One curious spinoff is that there is a structure of cardinality 6 on which the logic of Hintikka and Sandu gives nearly eight million inequivalent formulas in one free variable (which is more than the population of Finland).

AMS 03 B 60

Peter J. Cameron (editor), Problems on discrete metric spaces,

These problems were presented at the Third International Conference on Discrete Metric Spaces, held at CIRM, Luminy, France, 15-18 September 1998. The names of the originators of a problem are given where these are known and different from the presenter of the problem at the conference.

AMS 52 C 99

DVI or PostScript

Peter J. Cameron, Homogeneous Cayley objects,

We examine a number of countable homogeneous relational structures
with the aim of deciding which countable groups can act regularly
on them. Since a group *X* acts regularly on a graph *G* if
and only if *G* is a Cayley graph for *X*, we will extend
the terminology and say that *M* is a *Cayley object* for
*X* if *X* acts regularly on *M*. We consider, among
other things, graphs, hypergraphs, metric spaces and total orders.

AMS 20 B 07

DVI or PostScript

Peter J. Cameron, SGDs with 2-transitive automorphism group,

Symmetric graph designs, or SGDs, were defined
by Gronau *et al.* as a common generalisation of symmetric BIBDs
and orthogonal double covers. This note gives a
classification of SGDs admitting a 2-transitive
automorphism group. There are too many for a complete
determination, but in some special cases the
determination can be completed, such as those
which admit a 3-transitive group, and those with
λ=1. The latter case includes the
determination of all near 1-factorisations of K_{n}
(partitions of the edge set into subsets each of which
consists of disjoint edges covering all but one point)
which admit 2-transitive groups.

AMS 05 B 30

DVI or PostScript

Peter J. Cameron, An extremal problem related to biplanes,

The existence problem for biplanes has proved to be intractable: only finitely many are known. However, it can be turned into an extremal problem, on which some progress can be made.

AMS 05 B 05

DVI or PostScript

Peter J. Cameron, Some counting problems related to permutation groups, Proceedings of FPSAC10, Toronto, June 1998.

This paper discusses investigations of sequences of natural
numbers which count the orbits of an infinite permutation group
on *n*-sets or *n*-tuples. It surveys known results on the
growth rates, cycle index techniques, and an interpretation
as the Hilbert series of a graded algebra, with a possible
application to the question of smoothness of growth. I suggest
that these orbit-counting sequences are sufficiently special
to be interesting but sufficiently common to support a general
theory.

AMS 20 B 07, 05 A 15

DVI or PostScript

Peter J. Cameron and Csaba Szabó, Independence algebras,

An independence algebra is an algebra *A* in which the subalgebras satisfy
the exchange axiom, and any map from a basis of *A* into *A*
extends to an endomorphism. Independence algebras fall into two classes;
the first are specified by a set *X*, a group *G*, and a
*G*-space *C*. The second are
much more restricted; we show that the subalgebra lattice is a projective
or affine geometry, and give a complete classification of the finite
algebras.

AMS 08 A 05

DVI or PostScript

L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments,

Two tournaments *T*_{1} and *T*_{2} on the same
vertex set *X* are said to be *switching equivalent* if
*X* has a subset *Y* such that *T*_{2} arises from
*T*_{1} by switching all arcs between *Y* and
its complement in *X*.
The main result of this paper is a characterisation
of the abstract finite groups which are full automorphism groups of
switching classes of tournaments: they are those whose Sylow 2-subgroups
are cyclic or dihedral. Moreover, if *G* is such a group,
then there is a switching class *C*, with
Aut(*C*) isomorphic to *G*, such that every subgroup of
*G* of odd order is the full
automorphism group of some tournament in *C*.

Unlike previous results of this type, we do not give an explicit
construction, but only an existence proof. The proof follows as a
special case of a result on the full automorphism group of random
*G*-invariant digraphs selected from a certain class of probability
distributions.

We also show that a permutation group *G*, acting on a set *X*,
is contained in the automorphism group of some switching class
of tournaments with vertex set *X* if and only if the Sylow 2-subgroups
of *G* are cyclic or dihedral and act semiregularly on *X*.
Applying this result to individual permutations leads to
an enumeration of switching classes, of switching classes admitting odd
permutations, and of tournaments in a switching class.

We conclude by remarking that both the class of switching classes of finite tournaments, and the class of "local orders" (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting autmorphism groups (by a theorem of Fraïssé).

AMS 20B25; also 05C20, 05C25, 05C30, 05E99

DVI or PostScript

E. A. Bender, P. J. Cameron, A. M. Odlyzko and B. L. Richmond, Connectedness, classes, and cycle index,

This paper begins with the observation that half of all graphs containing no induced path of length 3 are disconnected. We generalize this in several directions. First, we give necessary and sufficient conditions (in terms of generating functions) for the probability of connectedness in a suitable class of graphs to tend to a limit strictly between zero and one. Next we give a general framework in which this and related questions can be posed, involving operations on classes of finite structures. Finally, we discuss briefly an algebra associated with such a class of structures, and give a conjecture about its structure.

AMS 05 A 16

Peter J. Cameron and Paul Erdős, Notes on sum-free and related sets,

Our main topic is the number of subsets of [1,*n*]
which are maximal with respect to some condition such as
being sum-free, having no number dividing another, etc.
We also investigate some related questions.

AMS 11 P 99

Peter J. Cameron, A census of infinite distance-transitive graphs,

This paper describes some classes of infinite distance-transitive graphs. It has no pretensions to give a complete list, but concentrates on graphs which have no finite analogues.

AMS 05 C 25

Peter J. Cameron, On an algebra related to orbit-counting,

With any permutation group *G* on an infinite set *Omega* is
associated a graded algebra *A ^{G}* (the algebra of

I conjectured 20 years ago that, if *G* has no finite orbits on
Omega, then *A ^{G}* is an integral domain (and even has the
stronger property that a specific quotient is an integral domain).
I shall say that

AMS 20 B 07

Neil J. Calkin and Peter J. Cameron, Almost odd random sum-free sets,

We show that, if *S*_{1} is a strongly complete sum-free set
of positive integers and if *S*_{0} is a finite sum-free set,
then with positive probability a random sum-free set *U*
contains S_{0} and is contained in *S*_{0} union
*S*_{1}. As a corollary we show that with positive probability,
2 is the only even element of a random sum-free set.

AMS 11 P 99

Peter J. Cameron, On the probability of connectedness,

Given a class of structures with a notion of connectedness (satisfying some reasonable assumptions), we consider the limit (as n tends to infinity) of the probability that a random (labelled or unlabelled) n-element structure in the class is connected. The paper consists of three parts: a specific example, N-free posets, where the limiting probability of connectedness is the golden ratio; an investigation of the relation between this question and the growth rate of the number of structures in the class; and a generalisation of the problem to other combinatorial constructions motivated in part by the group-theoretic constructions of direct and wreath product.

AMS 05 A 16

Peter J. Cameron, The algebra of an age, in

Associated with any oligomorphic permutation group *G*,
there is a graded algebra *A ^{G}* such that the
dimension of its

AMS 03 C 35

A. R. Calderbank, P. J. Cameron, W. M. Kantor and J. J. Seidel,

When *m* is odd, spreads in an orthogonal vector space of type
*Omega ^{+}(2m+2,2)* are related to binary
Kerdock codes and extremal line-sets in

AMS 94 B 27

Peter J. Cameron, Aspects of cofinitary permutation groups, pp. 93-99 in

A permutation group is cofinitary if any non-identity element fixes only finitely many points. In this article, I discuss two aspects of the theory of cofinitary permutation groups, one topological, the other combinatorial. Several open problems are included.

AMS 20 B 07

Peter J. Cameron, Finite geometries after Aschbacher's theorem:

Studying the geometry of a group *G* leads us to questions
about its maximal subgroups and primitive permutation
representations (the *G*-invariant relations and similar
structures, the base size, recognition problems, and so on).
Taking the point of view that finite projective geometry
is the geometry of the groups *PGL(n,q)*, Aschbacher's
theorem gives us eight natural families of geometric objects,
with greater or smaller degrees of familiarity. This paper
presents some speculations on how the subject could develop
from this point of view.

AMS 51 E 20

Peter J. Cameron, Oligomorphic groups and homogeneous graphs, in

These notes are, in a sense, an elaboration on the comments on pages 232-234 of the book on Distance-transitive Graphs by Brouwer, Cohen and Neumaier. Apart from these brief comments, the book is exclusively concerned with finite graphs. Many of these finite graphs are geometrically defined, and involve a finite field and sometimes a finite dimension. By allowing one or both of these parameters to be infinite, we often obtain infinite distance-transitive graphs. However, entirely new phenomena occur in the infinite case, which have no finite analogues.

In these notes, I discuss infinite graphs (and other structures) with a large amount of symmetry. The discussion concentrates on the purely infinite phenomena, though we glance briefly at the infinite versions of finite graphs. The celebrated "random graph" is typical of the new situation; the first section summarises some of the remarkable properties of this graph. Following this, we survey some basic material from permutation groups and model theory. Then we discuss various constructions and characterisations of infinite highly symmetric graphs, and connections with several topics in finite combinatorics, including random graphs, enumeration, and graph reconstruction.

AMS 05 C 25

Peter J. Cameron, Graphs and first-order logic,

This chapter concerns some connections between graph theory and first-order logic. After an introduction to first-order logic and a discussion of which graph properties are first-order, we consider various logical concepts such as aleph_0-categoricity and homogeneity for graphs, and present a couple of theorems about finite graphs requiring logical techniques in their proofs. The chapter concludes with a discussion of a recent construction method due to Hrushovski related to sparse random graphs.

AMS 05 C 99

Peter J. Cameron, Graphs and groups,

In this chapter, the connections between a graph and its automorphism group are described. The main themes are that most graphs have very little symmetry; abstract automorphism groups can be prescribed independently of most graph-theoretic properties; vertex-transitivity, however, entails various structural properties; and still higher degrees of symmetry can be expected to lead to a complete classification.

AMS 05 C 25

Peter J. Cameron, The random graph, in

Erdős and Rényi showed the paradoxical result that there is a unique (and highly symmetric) countably infinite random graph. This graph, and its automorphism group, form the subject of the present survey.

AMS 05 C 80

Peter J. Cameron, Stories about groups and sequences,

The main theme of this paper is that counting orbits of an infinite permutation group on finite subsets or tuples is very closely related to combinatorial enumeration. This point of view ties together various disparate "stories", concerning two-graphs, circular orders, Stirling numbers, series-reduced trees, etc.

AMS 05 A 99

Peter J. Cameron, Metric and topological aspects of the symmetric group of countable degree,

There is a natural topology on the symmetric group on an infinite set Omega. If Omega is countable, the topology is derived from a metric, and the group is complete. This paper gives an account of this topology, including translations of topological concepts for permutation groups, the use of Baire category and Haar measure, and some results about cofinitary permutation groups which are motivated by the combinatorics of finite symmetric groups.

AMS 20 B 07

Peter J. Cameron, Cycle-closed permutation groups,

A finite permutation group is cycle-closed if it contains all the cycles of all of its elements. It is shown by elementary means that the cycle-closed groups are precisely the direct products of symmetric groups and cyclic groups of prime order. Moreover, from any group, a cycle-closed group is reached in at most three steps, a step consisting of adding all cycles of all group elements. For infinite groups, there are several possible generalisations. Some analogues of the finite result are proved.

AMS 20 B 07

Peter J. Cameron, Cofinitary permutation groups,

A permutation group is cofinitary if any non-identity element fixes only finitely many points. This paper presents a survey of such groups. The paper has four parts. Sections 1-5 develop some basic theory, concerning groups with finite orbits, topology, maximality, and normal subgroups. Sections 6-10 give a variety of constructions, both direct and from geometry, combinatorial group theory, trees, and homogeneous relational structures. Sections 11-15 present some generalisations of sharply k-transitive groups, including an orbit-counting result with a character-theoretic flavour. The final section treats some miscellaneous topics. Several open problems are mentioned.

AMS 20 B 07

Peter J. Cameron, Sequence operators from groups,

This note is inspired by the paper *Some Canonical
Sequences of Integers* by Bernstein and Sloane.
The main observation is that seven of the operators
defined in that paper have natural interpretations
in terms of counting orbits of groups, providing
a pattern which is completed by five further
operators. Some of their eigen-sequences also have
group-theoretic meaning.

AMS 20 B 07

P. J. Cameron and D. G. Fon-Der-Flaass, Bases for groups and matroids,

In this paper, we give two equivalent conditions for the irredundant bases of a permutation group to be the bases of a matroid. (These are deduced from a more general result on families of sets.) If they hold, then the group acts geometrically on the matroid, in the sense that the fixed points of any element form a flat. Some partial results towards a classification of such permutation groups are given. Further, if G acts geometrically on a perfect matroid design, there is a formula for the number of G-orbits on bases in terms of the cardinalities of flats and the numbers of G-orbits on tuples. This reduces, in a particular case, to the inversion formula for Stirling numbers.

AMS 20 B 05

Peter J. Cameron

27 July 2009