Peter Cameron's abstracts

Parthajit Bhowal, Peter J. Cameron, Rajat Kanti Nath and Benjamin Sambale, Genus and crosscap of solvable conjugacy class graphs of finite groups, Arch. Math., 122 (2024), 475-489

Ajay Kumar, Lavanya Selvaganesh, T. Tamizh Chelvam and Peter J. Cameron, Superpower graphs of finite groups, J. Algebra Appl., in press

For a finite group G, the superpower graph S(G) of G is an undirected simple graph with vertex set G and two vertices are adjacent in S(G) if and only if the order of one divides the order of the other in G. The aim of this paper is to provide tight bounds for the vertex connectivity, discuss Hamiltonian-like properties of superpower graph of finite non-abelian groups having an element of exponent order.

We also give some general results about superpower graphs and their relation to other graphs such as the Gruenberg–Kegel graph.

doi: 10.1142/S0219498825502147

Xuanlong Ma and Peter J. Cameron, Finite groups whose commuting graph is split, Proc. Krasovskii Institute of Mathematics and Mechanics, in press.

As a contribution to the study of graphs on groups, we show that the commuting graph of a finite group G is a split graph, or a threshold graph, if and only if either G is abelian or G is a generalized dihedral group

D(A) = ⟨A,t : (for all a∈A)(at)²=1⟩

Peter J. Cameron, James East, Des FitzGerald, James D. Mitchell, Luke Pebody and Thomas Quinn-Gregson, Minimum degrees of finite rectangular bands, null semigroups, and variants of full transformation semigroups, Combinatorial Theory 3(3) (2023), #16 (48pp.)

For a positive integer n, the full transformation semigroup T_n consists of all self maps of the set {1,…,n} under composition. Any finite semigroup S embeds in some T_n, and the least such n is called the (minimum transformation) degree of S and denoted μ(S). We find degrees for various classes of finite semigroups, including rectangular bands, rectangular groups and null semigroups. The formulae we give involve natural parameters associated to integer compositions. Our results on rectangular bands answers a question of Easdown from 1992, and our approach utilises some results of independent interest concerning partitions/colourings of hypergraphs.

As an application, we prove some results on the degree of a variant T_n^a. (The variant S^a = (S,*) of a semigroup S with respect to a fixed element a∈S, has underlying set S and operation x*y = xay.) It has been previously shown that n ≤ μ(T_n^a) ≤ 2n−r if the sandwich element a has rank r, and the upper bound of 2n−r is known to be sharp if r ≥ n−1. Here we show that μ(T_n^a) = 2n−r for r ≥ n−6. In stark contrast to this, when r = 1, and the above inequality says n ≤ μ(T_n^a) ≤ 2n−1, we show that μ(T_n^a)/n → 1 and μ(T_n^a)−n → ∞ as n → ∞.

Among other results, we also classify the 3-nilpotent subsemigroups of T_n, and calculate the maximum size of such a subsemigroup.

doi: 10.5070/C63362799; arXiv 2110.09701

S. Anukumar Kathirvel, Peter J. Cameron and T. Tamizh Chelvam, Generalized non-coprime graph of groups, J. Algebraic Combinatorics, in press

Let G be a finite group with identity e and H be a non-trivial subgroup of G. The generalized non-coprime graph Γ(G,H) of G with respect to H is the simple undirected graph with G−e as the vertex set and two distinct vertices x and y are adjacent if and only if gcd(|x|,|y|) > 1 and either x∈H or y∈H, where |x| is the order of x∈G. In this paper, we study certain graph theoretical properties of generalized non-coprime graphs of finite groups, concentrating on cyclic groups. More specifically, we obtain necessary and sufficient conditions for the generalized non-coprime graph of a cyclic group to be in the class of stars, paths, triangle-free, complete bipartite, complete, split, claw-free, chordal or perfect graphs. Then we show that widening the class of groups to all finite nilpotent groups gives us no new graphs, but we give as an example of contrasting behaviour the class of EPPO groups (those in which all elements have prime power order). We conclude with a connection to the Gruenberg–Kegel graph.

arXiv 2208.01900

Peter J. Cameron, What can graphs and algebraic structures say to each other? AKCE Internat. J. Graphs and Combinatorics, in press

doi: 10.1080/09728600.2023.2290036

Marina Anagnostopoulou-Merkouri, Peter J. Cameron and Enoch Suleiman, Pre-primitive permutation groups, J. Algebra 636 (2023), 695-715

A transitive permutation group G on a finite set Ω is said to be pre-primitive if every G-invariant partition of Ω is the orbit partition of a subgroup of G. It follows that pre-primitivity and quasiprimitivity are logically independent (there are groups satisfying one but not the other) and their conjunction is equivalent to primitivity. Indeed, part of the motivation for studying pre-primitivity is to investigate the gap between primitivity and quasiprimitivity. We investigate the pre-primitivity of various classes of transitive groups including groups with regular normal subgroups, direct and wreath products, and diagonal groups. In the course of this investigation, we describe all G-invariant partitions for various classes of permutation groups G. We also look briefly at conditions similarly related to other pairs of conditions, including transitivity and quasiprimitivity, k-homogeneity and k-transitivity, and primitivity and synchronization.

doi: 10.1016/j.jalgebra.2023.09.012; arXiv 2302.13703

R. A. Bailey, Peter J. Cameron, Dáario Ferreira, Sandra Ferreira and Célia Nunes, Designs for half-diallel experiments with commutative orthogonal block structure, J. Statit. Planning Inference 231 (2024), 106139

In some experiments, the experimental units are all pairs of individuals who have to undertake a given task together. The set of such pairs forms a triangular association scheme. Appropriate randomization then gives two non-trivial strata. The design is said to have commutative orthogonal block structure (COBS) if the best linear unbiased estimators of treatment contrasts do not depend on the stratum variances. There are precisely three ways in which such a design can have COBS. We give a complete description of designs for which all treatment contrasts are in the same stratum. Then we give a very general construction for designs with COBS which have some treatment contrasts in each stratum.

doi: 10.1016/j.jspi.2023.106139

J. Araújo, J. P. Araújo, P. J. Cameron, E. W. H. Lee and J. Raminhos, A survey on varieties generated by small semigroups and a companion website, J. Algebra 635 (2023), 698-735

The aim of this paper is to provide an atlas of identity bases for varieties generated by small semigroups and groups. To help the working mathematician easily find information, we provide a companion website that runs in the background automated reasoning tools, finite model builders, and GAP, so that the user has an automatic \textit{intelligent} guide on the literature.

This paper is mainly a survey of what is known about identity bases for semigroups or groups of small orders, and we also mend some gaps left unresolved by previous authors. For instance, we provide the first complete and justified list of identity bases for the varieties generated by a semigroup of order up to 4, and the companion website contains the list of varieties generated by a semigroup of order up to 5.

The paper ends with several open problems.

doi: 10.1016/j.jalgebra.2023.06.030

Peter J. Cameron, Independence and bases: Theme and variations, Model Theory, in press

This paper describes a complex of related ideas, ranging from Urbanik's v^*-algebras, through Deza's geometric groups and Zilber's homogeneous geometries, to Sims' bases for permutation groups and their use in defining "size" parameters on finite groups, with a brief look at Cherlin's relational complexity. It is not a complete survey of any of these topics, but aims to describe the links between them.

Marina Anagnostopoulou-Merkouri and Peter J. Cameron, Association schemes with given stratum dimensions: on a paper of Peter M. Neumann, Algebraic Combinatorics 6 (2023), 1189-1210

In January 1969, Peter M. Neumann wrote a paper entitled "Primitive permutation groups of degree 3p". The main theorem placed restrictions on the parameters of a primitive but not 2-transitive permutation group of degree three times a prime. The paper was never published, and the results have been superseded by stronger theorems depending on the classification of the finite simple groups, for example a classification of primitive groups of odd degree.

doi: 10.5802/alco.307; arXiv 2208.04049

R. A. Bailey and Peter J. Cameron, Laplacian eigenvalues and optimality, in Graphs, Groups, Designs and Dynamics (ed. R. A. Bailey, Peter J. Cameron and Yaokun Wu), 176-265, London Math. Soc. Lecture Notes 491, Cambridge Univ. Press, Cambridge, in press

Eigenvalues of the Laplacian matrix of a graph have been widely used in studying connectivity and expansion properties of networks, and also in analysing random walks on a graph.

Independently, statisticians introduced various optimality criteria in experimental design, the goal being to obtain more accurate estimates of quantities of interest in an experiment. It turns out that the most popular of these optimality criteria for block designs are determined by the Laplacian eigenvalues of the concurrence graph, or of the Levi graph, of the design.

The number of spanning trees is also an evaluation of the Tutte polynomial of the graph, and is the subject of the Merino--Welsh conjecture relating it to acyclic and totally cyclic orientations, of interest in their own right.

Parthajit Bhowal, Peter J. Cameron, Rajat Kanti Nath and Benjamin Sambale, Solvable conjugacy class graph of groups, Discrete Math., in press.

In this paper we introduce the graph Γ_sc(G)$ associated with a group G, called the solvable conjugacy class graph (abbreviated as SCC-graph), whose vertices are the nontrivial conjugacy classes of G and two distinct conjugacy classes C, D are adjacent if there exist x∈C and y∈D such that ⟨x, y⟩ is solvable.

We discuss the connectivity, girth, clique number, and several other properties of the SCC-graph. One of our results asserts that there are only finitely many finite groups whose SCC-graph has given clique number d, and we find explicitly the list of such groups with d = 2. We pose some problems on the relation of the SCC-graph to the solvabale graph and to the NCC-graph, which we cannot solve.

doi: 10.1016/j.disc.2023.113467; arXiv 2112.02613

G. Arunkumar, P. J. Cameron, T. Kavaskar, and T. Tamizh Chelvam, Induced subgraphs of zero-divisor graphs, Discrete Math. 346 (2023), paper 113580

The zero-divisor graph of a finite commutative ring with unity is the graph whose vertex set is the set of zero-divisors in the ring, with a and b adjacent if ab = 0. We show that the class of zero-divisor graphs is universal, in the sense that every finite graph is isomorphic to an induced subgraph of a zero-divisor graph. This remains true for various restricted classes of rings, including boolean rings, products of fields, and local rings. But in more restricted classes, the zero-divisor graphs do not form a universal family. For example, the zero-divisor graph of a local ring whose maximal ideal is principal is a threshold graph; and every threshold graph is embeddable in the zero-divisor graph of such a ring. More generally, we give necessary and sufficient conditions on a non-local ring for which its zero-divisor graph to be a threshold graph. In addition, we show that there is a countable local ring whose zero-divisor graph embeds the Rado graph, and hence every finite or countable graph, as induced subgraph. Finally, we consider embeddings in related graphs such as the 2-dimensional dot product graph.

doi: 10.1016/j.disc.2023.113580; arXiv 2207.11741

Peter J. Cameron and Veronica Phan, Enhanced power graphs of groups are weakly perfect, Australasian J. Combinatorics 85(1) (2023), 100-105.

A graph is weakly perfect if its clique number and chromatic number are equal. We show that the enhanced power graph of a finite group G is weakly perfect: its clique number and chromatic number are equal to the maximum order of an element of G. The proof requires a combinatorial lemma. We give some remarks about related graphs.

arXiv 2207.07156

Peter J. Cameron, Angsuman Das and Hiranya Kishore Dey, On some properties of vector space based graphs, Linear and Multilinear Algebra, 71 (2023), 2858-2868

In this paper, we study some problems related to subspace inclusion graph In(V) and subspace sum graph G(V) of a finite-dimensional vector space V. Namely, we prove that In(V) is a Cayley graph as well as Hamiltonian when the dimension of V is 3. We also find the exact value of independence number of G(V) when the dimension of V is odd. The above two problems were left open in previous works in literature. Moreover, we prove that the determining numbers of In(V) and G(V) are bounded above by 6. Finally, we study some forbidden subgraphs of these two graphs.

doi: 10.1080/03081087.2022.2121370

Peter J. Cameron, R. Raveendra Prathap and T. Tamizh Chelvam, Subgroup sum graphs of finite abelian groups, Graphs and Combinatorics 38 (2022), article 114.

Let G be a finite abelian group, written additively, and H a subgroup of G. The subgroup sum graph Γ_G,H is the graph with vertex set G, in which two distinct vertices x and y are joined if x+y ∈ H\{0}. These graphs form a fairly large class of Cayley sum graphs. Among cases which have been considered previously are the prime sum graphs, in the case where H = pG for some prime number p. In this paper we present their structure and a detailed analysis of their properties. We also consider the simpler graph Γ⁺_G,H, which we refer to as the extended subgroup sum graph, in which x and y are joined if x+y ∈ H: the subgroup sum is obtained by removing from this graph the partial matching of edges having the form {x,−x} when 2x ≠ 0. We study perfectness, clique number and independence number, connectedness, diameter, spectrum, and domination number of these graphs and their complements. We interpret our general results in detail in the prime sum graphs.

doi: 10.1007/s00373-022-02515-w; arXiv 2111.05748

J. Araújo, P. J. Cameron, C. Casolo, F. Matucci and C. Quadrelli, Integrals of groups, II, Israel J. Math., in press.

An integral of a group G is a group H whose derived group (commutator subgroup) is isomorphic to G. This paper continues the investigation on integrals of groups started in the paper Integrals of groups. We study:

• A sufficient condition for a bound on the order of an integral for a finite integrable group and a necessary condition for a group to be integrable.
• The existence of integrals that are p-groups for abelian p-groups, and of nilpotent integrals for all abelian groups.
• Integrals of (finite or infinite) abelian groups, including nilpotent integrals, groups with finite index in some integral, periodic groups, torsion-free groups and finitely generated groups.
• The variety of integrals of groups from a given variety, varieties of integrable groups and classes of groups whose integrals (when they exist) still belong to such a class.
• Integrals of profinite groups and a characterization for integrability for finitely generated profinite centreless groups.
• Integrals of Cartesian products, which are then used to construct examples of integrable profinite groups without a profinite integral.

arXiv 2008.13675

G. Arun Kumar, Peter J. Cameron, Rajat Kanti Nath and Lavanya Selvaganesh, Super graphs on groups, I. Graphs and Combinatorics, in press

Let G be a finite group. A number of graphs with the vertex set G have been studied, including the power graph, enhanced power graph, and commuting graph. These graphs form a hierarchy under the inclusion of edge sets, and it is useful to study them together. In addition, several authors have considered modifying the definition of these graphs by choosing a natural equivalence relation on the group such as equality, conjugacy, or equal orders, and joining two elements if there are elements in their equivalence class that are adjacent in the original graph. In this way, we enlarge the hierarchy into a second dimension. Using the three graph types and three equivalence relations mentioned gives nine graphs, of which in general only two coincide; we find conditions on the group for some other pairs to be equal. These often define interesting classes of groups, such as EPPO groups, 2-Engel groups, and Dedekind groups.

We study some properties of graphs in this new hierarchy. In particular, we characterize the groups for which the graphs are complete, and in most cases, we characterize the dominant vertices (those joined to all others). Also, we give some results about universality,  perfectness, and clique number.

doi: 10.1007/s00373-022-02496-w; arXiv 2112.02395

Peter J. Cameron and Bojan Kuzma, Between the enhanced power graph and the commuting graph, J. Graph Theory 102 (2023), 295-303.

The purpose of this note is to define a graph whose vertex set is a finite group G, whose edge set is contained in that of the commuting graph of G and contains the enhanced power graph of G. We call this graph the deep commuting graph of G. Two elements of G are joined in the deep commuting graph if and only if their inverse images in every central extension of G commute.

We give conditions for the graph to be equal to either of the enhanced power graph and the commuting graph, and show that the automorphism group of G acts as automorphisms of the deep commuting graph.

doi: 10.1002/jgt.22871; arXiv 2012.03789

Peter J. Cameron, Balanced incomplete block designs, chapter in The Sage Encyclopedia of Research Design, Sage Publishing, Thousand Oaks, 2002, 6pp.

Block designs are useful in experimental design when the experimental material is not uniform but can be divided into homogeneous blocks. Typically, blocks cannot contain all the treatments, so incomplete block designs are used. The condition of balance, if it can be achieved, guarantees that the designs are optimal in minimizing the variance of treatment differences.

This entry provides a survey of balanced incomplete block designs (BIBDs). It discusses necessary conditions on the parameters for the existence of the designs and optimality results. It also provides a brief introduction to constructions of BIBDs using difference families, finite fields, or recursive methods, and some generalizations, including pointers about what to do if no BIBD is available.

doi: 10.4135/9781071812082.n35

Peter J. Cameron, V. V. Swathi and M. S. Sunitha, Matching in power graphs of finite groups, Annals of Combinatorics 26 (2022), 379-391.

The power graph P(G) of a finite group G is the undirected simple graph with vertex set G, where two elements are adjacent if one is a power of the other. In this paper, the matching numbers of power graphs of finite groups are investigated. We give upper and lower bounds, and conditions for the power graph of a group to possess a perfect matching. We give a formula for the matching number for any finite nilpotent group. In addition, using some elementary number theory, we show that the matching number of the enhanced power graph P_e(G) of G (in which two elements are adjacent if both are powers of a common element) is equal to that of the power graph of G.

doi: 10.1007/s00026-022-00576-5; arXiv: 2107.01157

Peter J. Cameron, Allen Herman and Dimitri Leemans, String C-groups with Schur index 2, J. Pure Appl. Algebra, in press

We give examples of finite string C-groups (the automorphism groups of abstract regular polytopes) that have irreducible characters of real Schur index 2. This answers a problem of Monson concerning these groups.

doi: 10.1016/j.jpaa.2022.107025; arXiv 2201.01313

Peter J. Cameron and Natalia Maslova, Criterion of unrecognizability of a finite group by its Gruenberg--Kegel graph, J. Algebra 607 (2022), 186-213

The Gruenberg--Kegel graph Γ(G) associated with a finite group G is an undirected graph without loops and multiple edges whose vertices are the prime divisors of |G| and in which vertices p and q are adjacent in Γ(G) if and only if G contains an element of order pq. This graph has been the subject of much recent interest; one of our goals here is to give a survey of some of this material, relating to groups with the same Gruenberg--Kegel graph. However, our main aim is to prove several new results. Among them are the following.

• There are infinitely many finite groups with the same Gruenberg--Kegel graph as the Gruenberg--Kegel of a finite group G if and only if there is a finite group H with non-trivial solvable radical such that Γ(G) = Γ(H).
• There is a function F on the natural numbers with the property that if a finite n-vertex graph whose vertices are labelled by pairwise distinct primes is the Gruenberg--Kegel graph of more than F(n) finite groups, then it is the Gruenberg--Kegel graph of infinitely many finite groups. (The function we give satisfies F(n) = O(n⁷), but this is not best possible.)
• If a finite graph Γ whose vertices are labelled by pairwise distinct primes is the Gruenberg--Kegel graph of only finitely many finite groups, then all such groups are almost simple; moreover, Γ has at least three pairwise non-adjacent vertices, and each vertex is non-adjacent to at least one other vertex, in particular, 2 is non-adjacent to at least one odd vertex.
• Groups whose power graphs, or commuting graphs, are isomorphic have the same Gruenberg--Kegel graph.
• The groups ²G₂(27) and E₈(2) are uniquely determined by the isomorphism types of their Gruenberg--Kegel graphs.

doi: 10.1016/j.jalgebra.2021.12.005; arXiv 2012.01482

João Araújo, Wolfram Bentz, Peter J. Cameron, Michael Kinyon and Janusz Konieczny, Matrix theory for independence algebras, Linear Algebra Appl. 642 (2022), 221-250

A universal algebra A with underlying set A is said to be an independence algebra if it is a matroid algebra and every mapping α:X → A defined on a basis X of A can be extended to an endomorphism of A. These algebras are particularly well-behaved generalizations of vector spaces, and hence they naturally appear in several branches of mathematics, such as model theory, group theory, and semigroup theory.

It is well known that matroid algebras have a well-defined notion of dimension. Let A be any independence algebra of finite dimension n, with at least two elements. Denote by End(A) the monoid of endomorphisms of A. In the 1970s, Głazek proposed the problem of extending the matrix theory for vector spaces to a class of universal algebras which included independence algebras. In this paper, we answer that problem by developing a theory of matrices for (almost all) finite-dimensional independence algebras.

In the process of solving this, we explain the relation between the classification of independence algebras obtained by Urbanik in the 1960s, and the classification of finite independence algebras up to endomorphism-equivalence obtained by Cameron and Szabó in 2000. (This answers another question by experts on independence algebras.) We also extend the classification of Cameron and Szabó to all independence algebras.

The paper closes with a number of questions for experts on matrix theory, groups, semigroups, universal algebra, set theory or model theory.

doi: 10.1016/j.laa.2022.02.021

A P₄-free graph is called a cograph. In this paper we partially characterize finite groups whose power graph is a cograph. As we will see, this problem is a generalization of the determination of groups in which every element has prime power order, first raised by Graham Higman in 1957 and fully solved very recently.

First we determine all groups G and H for which the power graph of G×H is a cograph. We show that groups whose power graph is a cograph can be characterised by a condition only involving elements whose orders are prime or the product of two (possibly equal) primes. Some important graph classes are also taken under consideration. For finite simple groups we show that in most of the cases their power graphs are not cographs: the only ones for which the power graphs are cographs are certain groups PSL(2,q) and Sz(q) and the group PSL(3,4). However, a complete determination of these groups involves some hard number-theoretic problems.

doi 10.1016/j.jalgebra.2021.09.034; arXiv 2106.14217

Let 1 ≤ r < n be integers. We give a proof that the group Aut(X_n^N,σ_n) of automorphisms of the one-sided shift on n letters embeds naturally as a subgroup H_n of the outer automorphism group Out(G_n,r) of the Higman–Thompson group G_n,r. From this, we can represent the elements of Aut(X_n^N,σ_n) by finite state non-initial transducers admitting a very strong synchronizing condition. Let H∈H_n and write |H| for the number of states of the minimal transducer representing H. We show that H can be written as a product of at most |H| torsion elements. This result strengthens a similar result of Boyle, Franks and Kitchens, where the decomposition involves more complex torsion elements and also does not support practical a priori estimates of the length of the resulting product. We also give new proofs of some known results about Aut(X_n^N,σ_n).

journal paper, doi 10.19086/da.28243, arXiv 2004.08478

We describe, through the use of Rubin's theorem, the automorphism groups of the Higman–Thompson groups G_n,r as groups of specific homeomorphisms of Cantor spaces C_n,r. This continues a thread of research begun by Brin, and extended later by Brin and Guzmán: to characterise the automorphism groups of the "Chameleon groups of Richard Thompson," as Brin referred to them in 1996. The work here completes the first stage of that twenty-year-old program, containing (amongst other things) a characterisation of the automorphism group of V, which was the "last chameleon". The homeomorphisms which arise fit naturally into the framework of Grigorchuk, Nekrashevich, and Suschanskiĭ's rational group of transducers: they are exactly those homeomorphisms which are induced by bi-synchronizing transducers, which we define in the paper. This result appears to offer insight into the nature of Brin and Guzmán's exotic automorphisms, while also uncovering connections with the theory of reset words for automata (arising in the Road Colouring Problem) and with the theory of automorphism groups of the full shift.

arXiv 1605.09302

Ajay Kumar, Lavanya Selvaganeshi, Peter J. Cameron and T. Tamizh Chelvam, Recent developments on the power graph of finite groups – a survey, AKCE Internat. J. Graphs Combinatorics 18 (2021), 65-94

doi: 10.1080/09728600.2021.1953359

R. A. Bailey, Peter J. Cameron, Cheryl E. Praeger and Csaba Schneider, The geometry of diagonal groups, Trans. Amer. Math. Soc. 375 (2022), 5259-5311.

Diagonal groups are one of the classes of finite primitive permutation groups occurring in the conclusion of the O'Nan–Scott theorem. Several of the other classes have been described as the automorphism groups of geometric or combinatorial structures such as affine spaces or Cartesian decompositions, but such structures for diagonal groups have not been studied in general. The main purpose of this paper is to describe and characterise such structures, which we call diagonal semilattices. Unlike the diagonal groups in the O'Nan–Scott theorem, which are defined over finite characteristically simple groups, our construction works over arbitrary groups, finite or infinite.

A diagonal semilattice depends on a dimension m and a group T. For m = 2, it is a Latin square, the Cayley table of T, though in fact any Latin square satisfies our combinatorial axioms. However, for m ≥ 3, the group T emerges naturally and uniquely from the axioms. (The situation somewhat resembles projective geometry, where projective planes exist in great profusion but higher-dimensional structures are coordinatised by an algebraic object, a division ring.)

A diagonal semilattice is contained in the partition lattice on a set Ω, and we provide an introduction to the calculus of partitions. Many of the concepts and constructions come from experimental design in statistics.

We also determine when a diagonal group can be primitive, or quasiprimitive (these conditions turn out to be equivalent for diagonal groups).

Associated with the diagonal semilattice is a graph, the diagonal graph, which has the same automorphism group as the diagonal semilattice except in four small cases with m ≤ 3. The class of diagonal graphs includes some well-known families, Latin-square graphs and folded cubes, and is potentially of interest. We obtain partial results on the chromatic number of a diagonal graph, and mention an application to the synchronization property of permutation groups.

doi: 10.1090/tran/8507; arXiv 2007.10726

R. A. Bailey, Peter J. Cameron, Michael Kinyon, and Cheryl E. Praeger, Diagonal groups and arcs over groups, Designs, Codes, Cryptography 90 (2022), 2069-2080,

In an earlier paper by three of the present authors and Csaba Schneider, it was shown that, for m ≥ 2, a set of m+1 partitions of a set Ω, any m of which are the minimal non-trivial elements of a Cartesian lattice, either form a Latin square (if m = 2), or generate a join-semilattice of dimension m associated with a diagonal group over a base group G.

In this paper we investigate what happens if we have m+r partitions with r ≥ 2, any m of which are minimal elements of a Cartesian lattice. If m = 2, this is just a set of mutually orthogonal Latin squares. We consider the case where all these squares are isotopic to Cayley tables of groups, and give an example to show the groups need not be all isomorphic. For m > 2, things are more restricted. Any m+1 of the partitions generate a join-semilattice admitting a diagonal group over a group G. It may be that the groups are all isomorphic, though we cannot prove this. Under an extra hypothesis, we show that G must be abelian and must have three fixed-point-free automorphisms whose product is the identity. (We describe explicitly all abelian groups having such automorphisms.) Under this hypothesis, the structure gives an orthogonal array, and conversely in some cases.

If the group is cyclic of prime order p, then the structure corresponds exactly to an arc of cardinality m+r in the (m−1)-dimensional projective space over the field with p elements, so all known results about arcs are applicable. More generally, arcs over a finite field of order $q$ give examples where G is the elementary abelian group of order q. These examples can be lifted to non-elementary abelian groups using p-adic techniques.

arXiv 2010.16338

R. A. Bailey and Peter J. Cameron, The diagonal graph, J. Ramanujan Math. Soc. 36 (2021), 353-361.

According to the O'Nan--Scott Theorem, a finite primitive permutation group either preserves a structure of one of three types (affine space, Cartesian lattice, or diagonal semilattice), or is almost simple. However, diagonal groups are a much larger class than those occurring in this theorem. For any positive integer m and group G (finite or infinite), there is a diagonal semilattice, a sub-semilattice of the lattice of partitions of a set Ω, whose automorphism group is the corresponding diagonal group. Moreover, there is a graph (the diagonal graph), bearing much the same relation to the diagonal semilattice and group as the Hamming graph does to the Cartesian lattice and the wreath product of symmetric groups.

Our purpose here, after a brief introduction to this semilattice and graph, is to establish some properties of this graph. The diagonal graph Γ_D(G,m) is a Cayley graph for the group G^m, and so is vertex-transitive. We establish its clique number in general and its chromatic number in most cases, with a conjecture about the chromatic number in the remaining cases. We compute the spectrum of the adjacency matrix of the graph, using a calculation of the Möbius function of the diagonal semilattice. We also compute some other graph parameters and symmetry properties of the graph.

We believe that this family of graphs will play a significant role in algebraic graph theory.

arXiv: 2101.02451

Pallabi Manna, Peter J. Cameron and Ranjit Mehatari, Forbidden subgraphs of power graphs, Electronic J. Combinatorics 28(3) (2021), Paper P3.4

The undirected power graph (or simply power graph) of a group G, denoted by P(G), is a graph whose vertices are the elements of the group G, in which two vertices u and v are connected by an edge between if and only if either u = vⁱ or v = u^j for some i,j.

A number of important graph classes, including perfect graphs, cographs, chordal graphs, split graphs, and threshold graphs, can be defined either structurally or in terms of forbidden induced subgraphs. We examine each of these five classes and attempt to determine for which groups G the power graph P(G) lies in the class under consideration. We give complete results in the case of nilpotent groups, and partial results in greater generality. In particular, the power graph is always perfect; and we determine completely the groups whose power graph is a threshold or split graph (the answer is the same for both classes). We give a number of open problems.

doi: 10.37236/9961; arXiv: 2010.05198

Peter J. Cameron, Graphs defined on groups, Internat. J. Group Theory 11 (2022), 43-124

This paper concerns aspects of various graphs whose vertex set is a group G and whose edges reflect group structure in some way (so that, in particular, they are invariant under the action of the automorphism group of G). The particular graphs I will chiefly discuss are the power graph, enhanced power graph, deep commuting graph, commuting graph, and non-generating graph.

My main concern is not with properties of these graphs individually, but rather with comparisons between them. The graphs mentioned, together with the null and complete graphs, form a hierarchy (as long as G is non-abelian), in the sense that the edge set of any one is contained in that of the next; interesting questions involve when two graphs in the hierarchy are equal, or what properties the difference between them has. I also consider various properties such as universality and forbidden subgraphs, comparing how these properties play out in the different graphs.

I have also included some results on intersection graphs of subgroups of various types, which are often in a "dual" relation to one of the other graphs considered. Another actor is the Gruenberg--Kegel graph, or prime graph, of a group: this very small graph has a surprising influence over various graphs defined on the group.

Other graphs which have been proposed, such as the nilpotence, solvability, and Engel graphs, will be touched on rather more briefly. My emphasis is on finite groups but there is a short section on results for infinite groups. There are briefer discussions of general Aut(G)-invariant graphs, and structures other than groups (such as semigroups and rings).

Proofs, or proof sketches, of known results have been included where possible. Also, many open questions are stated, in the hope of stimulating further investigation.

doi: 10.22108/ijgt.2021.127679.1681; arXiv 2102.11177

J. Araújo, J. P. Araújo, W. Bentz, P. J. Cameron and P. Spiga, A transversal property for permutation groups motivated by partial transformations, J. Algebra 573 (2021), 741-759

doi: 10.1016/j.jalgebra.2020.12.024; arXiv 1911.02058

P. J. Cameron, S. D. Freedman and C. M. Roney-Dougal, Non-commuting, non-generating graph of a nilpotent group, Electronic J. Combinatorics paper P1.16 (15pp)

For a nilpotent group G, let Ξ(G) be the difference between the complement of the generating graph of G and the commuting graph of G, with vertices corresponding to central elements of G removed. That is, Ξ(G) has vertex set G∖Z(G), with two vertices adjacent if and only if they do not commute and do not generate G. Additionally, let Ξ⁺(G) be the subgraph of Ξ(G) induced by its non-isolated vertices. We show that if Ξ(G) has an edge, then Ξ⁺(G)$ is connected with diameter 2 or 3, with Ξ(G) = Ξ⁺(G) in the diameter 3 case. In the infinite case, our results apply more generally, to any group with every maximal subgroup normal. When G is finite, we explore the relationship between the structures of G and Ξ(G) in more detail.

doi: 10.37236/9802; arXiv 2008.09291

R. A. Bailey, Peter J. Cameron, Michael Giudici and Gordon F. Royle, Groups generated by derangements, J. Algebra 572 (2021), 245-262

We examine the subgroup D(G) of a transitive permutation group G which is generated by the derangements in G. Our main results bound the index of this subgroup: we conjecture that, if G has degree n and is not a Frobenius group, then |G:D(G)| ≤ √n−1; we prove this except when G is a primitive affine group. For affine groups, we translate our conjecture into an equivalent form regarding |H:R(H)|, where H is a linear group on a finite vector space and R(H) is the subgroup of H$ generated by elements having eigenvalue 1.

If G is a Frobenius group, then D(G) is the Frobenius kernel, and so G/D(G) is isomorphic to a Frobenius complement. We give some examples where D(G) ≠ G, and examine the group-theoretic structure of G/D(G); in particular, we construct groups G in which G/D(G) is not a Frobenius complement.

doi: 10.1016/j.jalgebra.2020.12.020; arXiv 2004.01950

Bea Adam-Day and Peter J. Cameron, Undirecting membership in models of ZFA,, Aequationes Math. 95 (2021), 393-400

It is known that, if we take a countable model of Zermelo–Fraenkel set theory ZFC and "undirect" the membership relation (that is, make a graph by joining xto y if either x∈y or y∈x), we obtain the Erdős–Rényi random graph. The crucial axiom in the proof of this is the Axiom of Foundation; so it is natural to wonder what happens if we delete this axiom, or replace it by an alternative (such as Aczel's Anti-Foundation Axiom). The resulting graph may fail to be simple; it may have loops (if x∈x for some x) or multiple edges (if x∈y and y∈x for some distinct x,y). We show that, in ZFA, if we keep the loops and ignore the multiple edges, we obtain the "random loopy graph" (which is ℵ₀-categorical and homogeneous), but if we keep multiple edges, the resulting graph is not ℵ₀-categorical, but has infinitely many 1-types. Moreover, if we keep only loops and double edges and discard single edges, the resulting graph contains countably many connected components isomorphic to any given finite connected graph with loops.

doi: 10.1007/s00010-020-00763-w, arXiv 1709.07943

J. Araújo, W. Bentz and P. J. Cameron, The existential transversal property: a generalization of homogeneity and its impact on semigroups, Trans. Amer. Math. Soc. 374 (2021), 1155-1195.

Let G be a permutation group of degree n, and k a positive integer with k ≤ n. We say that G has the k-existential property, or k-et, if there exists a k-subset A of the domain Ω whose orbit under G contains transversals for all k-partitions P of Ω. This property is a substantial weakening of the k-universal transversal property, or k-ut, investigated by the first and third author, which required this condition to hold for all k-subsets A of the domain Ω.

Our first task in this paper is to investigate the k-et property and to decide which groups satisfy it. For example, it is known that for k < 6 there are several families of k-transitive groups, but for k ≥ 6 the only ones are alternating or symmetric groups; here we show that in the k-et context the threshold is 8, that is, for 8 ≤ k ≤ n/2, the only transitive groups with k-et are the symmetric and alternating groups; this is best possible since the Mathieu group M₂₄ (degree 24) has 7-et. We determine all groups with k-et for 4 ≤ k ≤ n/2, up to some unresolved cases for k = 4,5, and describe the property for k = 2,3 in permutation group language. These considerations essentially answer Problem 5 proposed in the paper on k-ut referred to above; we also slightly improve the classification of groups possessing the k-ut property.

In that earlier paper, the results were applied to semigroups, in particular, to the question of when the semigroup ⟨G,t⟩ is regular, where t is a map of rank k (with k < n/2); this turned out to be equivalent to the k-ut property. The question investigated here is when there is a k-subset $A$ of the domain such that ⟨G,t⟩ is regular for all maps t with image A. This turns out to be much more delicate; the k-et property (with A as witnessing set) is a necessary condition, and the combination of k-et and (k−1)-ut is sufficient, but the truth lies somewhere between.

Given the knowledge that a group under consideration has the necessary condition of k-et, the regularity question for k ≤ n/2 is solved except for one sporadic group.

The paper ends with a number of problems on combinatorics, permutation groups and transformation semigroups, and their linear analogues.

doi: 10.1090/tran/8285, arXiv 1808.06085

J. Araújo, W. Bentz and P. J. Cameron, Primitive permutation groups and strongly factorizable transformation semigroups, J. Algebra 565 (2020), 513-530.

Let Ω be a finite set and T(Ω) be the full transformation monoid on Ω. The rank of a transformation t in T(Ω) is the natural number |Ωt|. Given a subset A of T(Ω), denote by ⟨A⟩ the semigroup generated by A. Let k be a fixed natural number such that 2 ≤ k ≤ |Ω|. In the first part of this paper we (almost) classify the permutation groups G on Ω such that for all rank k transformations t in T(Ω), every element in S_t = ⟨G,t⟩ can be written as a product eg, where e is an idempotent in S_t and g∈G. In the second part we prove, among other results, that if S ≤ T(Ω) and G is the normalizer of S in the symmetric group on Ω, then the semigroup SG is regular if and only if S is regular. (Recall that a semigroup S is regular if for all x∈S there exists y∈S such that x = xyx.) The paper ends with a list of problems.

doi: 10.1016/j.jalgebra.2020.05.023; arXiv 1910.08335

P. J. Cameron and S. H. Jafari, On the connectivity and independence number of power graphs of groups, Graphs Combin. 36 (2020), 895-904

doi: 10.1007/s00373-020-02162-z; arXiv 1910.06721

R. A. Bailey, Peter J. Cameron, L. H. Soicher and E. R. Williams, Substitutes for the non-existent square lattice designs for 36 vertices, J. Agricultural, Biological and Environmental Statistics 25 (2020), 487-499

Square lattice designs are often used in trials of new varieties of various agricultural crops. However, there are no square lattice designs for 36 varieties in blocks of size six for four or more replicates. Here we use three different approaches to construct designs for up to eight replicates. All the designs perform well in terms of giving a low average variance of variety contrasts.

Supplementary materials are available online.

doi: 10.1007/s13253-020-00388-1; arXiv 1912.08087

Full text; arXiv 1905.06569

Peter Cameron, David Ellis and William Raynaud, Smallest cyclically covering subspaces of F_qⁿ, and lower bounds in Isbell's conjecture, Europ. J. Combinatorics 81 (2019), 242-255.

For a prime power q and a positive integer n, we say a subspace U of F_qⁿ is cyclically covering if the union of the cyclic shifts of U is equal to F_qⁿ. We investigate the problem of determining the minimum possible dimension of a cyclically covering subspace F_qⁿ. (This is a natural generalisation of a problem posed in 1991 by the first author.) We prove several upper and lower bounds, and for each fixed q, we answer the question completely for infinitely many values of n (which take the form of certain geometric series). Our results imply lower bounds for a well-known conjecture of Isbell, and a generalisation theoreof, supplementing lower bounds due to Spiga. We also consider the analogous problem for general representations of groups. We use arguments from combinatorics, representation theory and finite field theory.

doi: 10.1016/j.ejc.2019.06.004, arXiv 1810.03485

R. A. Bailey and Peter J. Cameron, Multi-part balanced incomplete-block designs, Statistical Papers 60 (2019), 405-426.

We consider designs for cancer trials which allow each medical centre to treat only a limited number of cancer types with only a limited number of drugs. We specify desirable properties of these designs, and prove some consequences. Then we give several different constructions. Finally we generalize this to three or more factors, such as biomarkers.

doi: 10.1007/s00362-018-01071-x; arXiv 1803.00006

J. N. Bray, Q. Cai, P. J. Cameron, P. Spiga and H.Zhang, The Hall–Paige conjecture, and synchronization for affine and diagonal groups, J. Algebra 545 (2020), 27-42

The Hall–Paige conjecture asserts that a finite group has a complete mapping if and only if its Sylow subgroups are not cyclic. The conjecture is now proved, and one aim of this paper is to document the final step in the proof (for the sporadic simple group J₄).

We apply this result to prove that primitive permutation groups of simple diagonal type with three or more simple factors in the socle are non-synchronizing. We also give the simpler proof that, for groups of affine type, or simple diagonal type with two socle factors, synchronization and separation are equivalent.

Synchronization and separation are conditions on permutation groups which are stronger than primitivity but weaker than 2-homogeneity, the second of these being stronger than the first. Empirically it has been found that groups which are synchronizing but not separating are rather rare. It follows from our results that such groups must be primitive of almost simple type.

doi: 10.1016/j.jalgebra.2019.02.025; arXiv 1811.12671

J. Araújo, P. J. Cameron, C. Casolo and F. Matucci, Integrals of groups, Israel J. Math. 234 (2019), 149-178

An integral of a group G is a group H whose derived group (commutator subgroup) is isomorphic to G. This paper discusses integrals of groups, and in particular questions about which groups have integrals and how big or small those integrals can be. Our main results are:

• If a finite group has an integral, then it has a finite integral.
• A precise characterization of the set of natural numbers n for which every group of order n is integrable: these are the cubefree numbers n which do not have prime divisors p and q with q divides p−1.
• An abelian group of order n has an integral of order at most n^1+o(1), but may fail to have an integral of order bounded by cn for constant c.
• A finite group can be integrated more than once (in the class of finite groups) if and only if it is a central product of an abelian group and a perfect group.

There are many other results on such topics as centreless groups, groups with composition length 2, and infinite groups.

We also include a number of open problems.

doi: 10.1007/s11856-019-1926-y; arXiv 1803.10179

R. A. Bailey, Peter J. Cameron, Alexander L. Gavrilyuk and Sergey V. Goryainov, Equitable partitions of Latin-square graphs, J. Combinatorial Designs 27 (2019), 142-160.

We study equitable partitions of Latin-square graphs, and give a complete classification of those whose quotient matrix does not have an eigenvalue −3.

doi: 10.1002/jcd.21634, arXiv 1802.01001

R. A. Bailey, Peter J. Cameron and Tomas Nilson, Sesqui-arrays, a generalisation of triple arrays, Australas. J. Combinatorics 71(3) (2018), 427-451.

A triple array is a rectangular array containing letters, each letter occurring equally often with no repeats in rows or columns, such that the number of letters common to two rows, two columns, or a row and a column are (possibly different) non-zero constants. Deleting the condition on the letters common to a row and a column gives a double array. We propose the term sesqui-array for such an array when only the condition on pairs of columns is deleted.

In this paper we give three constructions for sesqui-arrays. The first gives (n+1)×n² arrays on n(n+1) letters for n ≥ 2. (Such an array for n = 2 was found by Bagchi.) This construction uses Latin squares. The second uses the Sylvester graph, a subgraph of the Hoffman–Singleton graph, to build a good block design for 36 treatments in 42 blocks of size 6, and then uses this in a 7×36 sesqui-array for 42 letters.

We also give a construction for K×(K−1)(K−2)/2 sesqui-arrays on K(K−1)/2 letters from biplanes. The construction starts with a block of a biplane and produces an array which satisfies the requirements for a sesqui-array except possibly that of having no repeated letters in a row or column. We show that this condition holds if and only if the Hussain chains for the selected block contain no 4-cycles. A sufficient condition for the construction to give a triple array is that each Hussain chain is a union of 3-cycles; but this condition is not necessary, and we give a few further examples.

We also discuss the question of which of these arrays provide good designs for experiments.

Full text; arXiv 1706.02930

Mohammed Aljohani, John Bamberg and Peter J. Cameron, Synchronization and separation in the Johnson scheme, Portugaliae Mathematica 74 (2018), 213-232

Recently Peter Keevash solved asymptotically the existence question for Steiner systems by showing that S(t,k,n)$ exists whenever the necessary divisibility conditions on the parameters are satisfied and n is sufficiently large in terms of k and t. The purpose of this paper is to make a conjecture which if true would be a significant extension of Keevash's theorem, and to give some theoretical and computational evidence for the conjecture.

We phrase the conjecture in terms of the notions (which we define here) of synchronization and separation for association schemes. These definitions are based on those for permutation groups which grow out of the theory of synchronization in finite automata. In this theory, two classes of permutation groups (called synchronizing and separating) lying between primitive and 2-homogeneous are defined. A big open question is how the permutation group induced by S_n on k-subsets of {1,…,n} fits in this hierarchy; our conjecture would give a solution to this problem for n large in terms of k.

doi: 10.4171/PM/2003; arXiv 1706.01365

Peter J. Cameron, Horacio Guerra and Šimon Jurina, The power graph of a torsion-free group, J. Algebraic Combinatorics 49 (2019), 83–98.

The power graph P(G) of a group G is the graph whose vertex set is G, with x and y joined if one is a power of the other; the directed power graph P^→(G) has the same vertex set, with an arc from x to y if y is a power of x. It is known that, for finite groups, the power graph determines the directed power graph up to isomorphism. However, it is not true that any isomorphism between power graphs induces an isomorphism between directed power graphs. Moreover, for infinite groups the power graph may fail to determine the directed power graph.

In this paper, we consider power graphs of torsion-free groups. Our main results are that, for torsion-free nilpotent groups of class at most 2, and for groups in which every non-identity element lies in a unique maximal cyclic subgroup, the power graph determines the directed power graph up to isomorphism. For specific groups such as Z and Q, we obtain more precise results. Any isomorphism P(Z)\to P(G) preserves orientation, so induces an isomorphism between directed power graphs; in the case of Q, the orientations are either all preserved or all reversed.

We also obtain results about groups in which every element is contained in a unique maximal cyclic subgroup (this class includes the free and free abelian groups), and about subgroups of the additive group of Q and about Qⁿ.

doi: 10.1007/s10801-018-0819-1; arXiv 1705.01586

P. J. Cameron and J. Semeraro, The cycle polynomial of a permutation group, Electronic J. Combinatorics 25(1) (2018), Paper P1.14

Full text; arXiv 1701.06954

João Araújo and Peter J. Cameron, Primitive groups, road closures, and idempotent generation

We are interested in semigroups of the form ⟨G,a⟩\G, where G is a permutation group of degree n and a a non-permutation on the domain of G. A theorem of the first author, Mitchell and Schneider shows that, if this semigroup is idempotent-generated for all possible choices of a, then G is the symmetric or alternating group of degree n, with three exceptions (having n = 5 or n = 6). Our purpose here is to prove stronger results where we assume that ⟨G,a⟩\G is idempotent-generated for all maps of fixed rank k. For k ≥ 6 and n ≥ 2k+1, we reach the same conclusion, that G is symmetric or alternating. These results are proved using a stronger version of the k-universal transversal property previously considered by the authors.

In the case k = 2, we show that idempotent generation of the semigroup for all choices of a is equivalent to a condition on the permutation group G, stronger than primitivity, which we call the road closure condition. We cannot determine all the primitive groups with this property, but we give a conjecture about their classification, and a body of evidence (both theoretical and computational) in support of the conjecture.

The paper ends with some problems.

arXiv 1611.08233

J. Araújo, J. P. Araújo, P. J. Cameron, T. Dobson, A. Hulpke and P. Lopes, Imprimitive permutations in primitive groups, J. Algebra 115 (2017), 135-176

The goal of this paper is to study primitive groups that are contained in the union of maximal (in the symmetric group) imprimitive groups. The study of types of permutations that appear inside primitive groups. The study of types of permutations that appear inside primitive groups goes back to the origins of the theory of permutation groups. However, this is another instance of a situation common in mathematics in which a very natural problem turns out to be extremely difficult. Fortunately, the enormous progresses of the last few decades seem to allow a new momentum on the attack to this problem. In this paper we prove that there are infinite families of primitive groups contained in the union of imprimitive groups and propose a new hierarchy for primitive groups based on that fact. In addition to the previous results and hierarchy, we introduce some algorithms to handle permutations, provide the corresponding GAP implementation, solve some open problems, and propose a large list of open problems.

doi: 10.1016/j.jalgebra.2017.03.043; arXiv 1611.06450

Peter J. Cameron and Kerri Morgan, Algebraic properties of chromatic roots, Electronic J. Combinatorics 24(1) (2017), paper #P1.21

A chromatic root is a root of the chromatic polynomial of a graph. Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008. The purpose of this paper is to report on the seminar and subsequent developments.

We conjecture that, for every algebraic integer α, there is a natural number n$ such that α+n is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one "interesting" factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.

Full text; arXiv 1610.00424

Bertalan Bodor, Peter J. Cameron and Csaba Szabó, Infinitely many reducts of homogeneous structures, Algebra Universalis 79 (2018), article 43

It is shown that the countably infinite dimensional pointed vector space (the vector space equipped with a constant) over a finite field has infinitely many first order definable reducts. This implies that the countable homogeneous Boolean-algebra has infinitely many reducts.

doi: 10.1007/s00012-018-0526-8; arXiv 1609.07694

Peter J. Cameron, Andrea Lucchini and Colva M. Roney-Dougal, Generating sets of finite groups, Trans. Amer. Math. Soc. 370 (2018), 6751-6770.

We investigate the extent to which the exchange relation holds in finite groups G. We define a new equivalence relation where two elements are equivalent if each can be substituted for the other in any generating set for G. We then refine this to a new sequence of equivalence relations by saying that two elements are equivalent in the rth relation if each can be substituted for the other in any r-element generating set. The relations become finer as r increases, and we define a new group invariant ψ(G) to be the value of r at which they stabilise.

Remarkably, we are able to prove that if G is soluble then ψ(G)∈{d(G),d(G)+1}, where d(G) is the minimum number of generators of G, and to classify the finite soluble groups G for which ψ(G) = d(G). For insoluble G, we show that d(G) ≤ ψ(G) ≤ d(G)+5. However, we know of no examples of groups G for which ψ(G) > d(G)+1.

As an application, we look at the generating graph of G, whose vertices are the elements of G, the edges being the 2-element generating sets. Our level-2 relation enables us to calculate Aut(Γ(G)) for all soluble groups G of nonzero spread, and give detailed structural information about Aut(Γ(G)) in the insoluble case.

doi: 10.1090/tran/7248; arXiv 1609.06077

Tomas Nilson and Peter Cameron, Triple arrays from difference sets, J. Combinatorial Designs 25 (2017), 494-506.

This paper addresses the question whether triple arrays can be constructed from Youden squares developed from difference sets. We prove that if the difference set is abelian, then having −1 as multiplier is both a necessary and sufficient condition for the construction to work. Using this, we are able to give a new infinite family of triple arrays. We also give an alternative and more direct version of the construction, leaving out the intermediate step via Youden squares. This is used when we analyse the case of non-abelian difference sets, for which we prove a sufficient condition for giving triple arrays. We do a computer search for such non-abelian difference sets, but have not found any examples satisfying the given condition.

doi 10.1002/jcd.21569, arXiv 1609.00152

Collin Bleak, Peter Cameron, Yonah Maissel, Andrés Navas, and Feyisayo Olukoya, The further chameleon groups of Richard Thompson and Graham Higman: Automorphisms via dynamics for the Higman groups G_n,r

We characterise the automorphism groups of the Higman groups G_n,r as groups of specific homeomorphisms of Cantor spaces C_n,r, through the use of Rubin's theorem. This continues a thread of research begun by Brin, and extended later by Brin and Guzmán: to characterise the automorphism groups of the 'Chameleon groups of Richard Thompson,' as Brin referred to them in 1996. The work here completes the first stage of that twenty-year-old program, containing (amongst other things) a characterisation of the automorphism group of V, which was the 'last chameleon.' As it happens, the homeomorphisms which arise naturally fit into the framework of Grigorchuk, Nekrashevich, and Suschanskiĭ's rational group of transducers, and exhibit fascinating connections with the theory of reset words for automata (arising in the Road Colouring Problem), while also appearing to offer insight into the nature of Brin and Guzmán's exotic automorphisms.

arXiv 1605.09302

Peter J. Cameron, Maria Elisa Fernandes, Dimitri Leemans, and Mark Mixer, Highest rank of a polytope for A_n, Proc. London Math. Soc. 115 (2017), 135-176

doi: 10.1112/plms.12039; arXiv 1605.09173

Ghodratallah Aalipour, Saieed Akbari, Peter J. Cameron, Reza Nikandish and Farzad Shaveisi, On the structure of the power graph and the enhanced power graph of a group, Electronic J. Combinatorics 24(3) (2017), P3.16

Let G be a group. The power graph of G is a graph with the vertex set G, having an edge between two elements whenever one is a power of the other. We characterize nilpotent groups whose power graphs have finite independence number. For a bounded exponent group, we prove its power graph is a perfect graph and we determine its clique/chromatic number. Furthermore, it is proved that for every group G, the clique number of the power graph of G is at most countably infinite. We also measure how close the power graph is to the commuting graph by introducing a new graph which lies in between. We call this new graph as the enhanced power graph. For an arbitrary pair of these three graphs we characterize finite groups for which this pair of graphs are equal.

Full text; arXiv 1603.04337

P. J. Cameron, A. Castillo-Ramirez, M. Gadouleau and J. D. Mitchell, Lengths of words in transformation semigroups generated by digraphs, J. Algebraic Combinatorics 45 (2017), 149-170.

Given a simple digraph D on n vertices (with n ≥ 2), there is a natural construction of a semigroup ⟨D⟩ associated with D. For any edge (a,b) of D, let a→b be the idempotent of defect 1 mapping a to b and fixing all vertices other than a; then define ⟨D⟩ to be the semigroup ⟨a→b:(a,b)∈E(D)⟩. For α∈⟨D⟩, let l(D,α) be the minimal length of a word in E(D) expressing α. When D = K_n is the complete undirected graph, Howie and Iwahori, independently, obtained a formula to calculate l(K_n,α), for any α∈⟨D⟩ = Sing_n; however, no analogous nontrivial results are known when D ≠ K_n. In this paper, we characterise all simple digraphs D such that either l(D,α) is equal to Howie–Iwahori's formula for all α∈⟨D⟩, or l(D,α) = n−fix(α) for all α∈⟨D⟩, or l(D,α) = n−rk(α) for all α∈⟨D⟩. When D is an acyclic digraph and α∈⟨D⟩, we find a tight upper bound for l(D,α). Finally, we study the case when D is a strong tournament (which corresponds to a smallest generating set of idempotents of defect 1 of Sing_n), and we propose some conjectures.

doi 10.1007/s10801-016-0703-9; arXiv 1602.00935

João Araújo, Peter J. Cameron and Benjamin Steinberg, Between primitive and 2-transitive: Synchronization and its friends, Europ. Math. Soc. Surveys 4 (2017), 101-184; doi: 10.4171/EMSS/4-2-1;

An automaton is said to be synchronizing if there is a word in the transitions which sends all states of the automaton to a single state. Research on this topic has been driven by the Černý conjecture, one of the oldest and most famous problems in automata theory, according to which a synchronizing n-state automaton has a reset word of length at most (n−1)². The transitions of an automaton generate a transformation monoid on the set of states, and so an automaton can be regarded as a transformation monoid with a prescribed set of generators. In this setting, an automaton is synchronizing if the transitions generate a constant map. A permutation group G on a set Ω is said to synchronize a map f if the monoid ⟨G,f⟩ generated by G and f is synchronizing in the above sense; we say G is synchronizing if it synchronizes every non-permutation.

The classes of synchronizing groups and friends form an hierarchy of natural and elegant classes of groups lying strictly between the classes of primitive and 2-homogeneous groups. These classes have been floating around for some years and it is now time to provide a unified reference on them. The study of all these classes has been prompted by the Černý conjecture, but it is of independent interest since it involves a rich mix of group theory, combinatorics, graph endomorphisms, semigroup theory, finite geometry, and representation theory, and has interesting computational aspects as well. So as to make the paper self-contained, we have provided background material on these topics. Our purpose here is to present results that show the connections between the various areas of mathematics mentioned above, we include a new result on the Černý conjecture, some challenges to finite geometers, some thoughts about infinite analogues, and a long list of open problems.

doi: 10.4171/EMSS/4-2-1; arXiv 1511.03184

Let Ω be a set of cardinality n, G a permutation group on Ω, and f:Ω→Ω a map which is not a permutation. We say that G synchronizes f if the transformation semigroup ⟨G,f⟩ contains a constant map, and that G is a synchronizing group if G synchronizes every non-permutation.

A synchronizing group is necessarily primitive, but there are primitive groups that are not synchronizing. Every non-synchronizing primitive group fails to synchronize at least one uniform transformation (that is, transformation whose kernel has parts of equal size), and it had previously been conjectured that this was essentially the only way in which a primitive group could fail to be synchronizing — in other words, that a primitive group synchronizes every non-uniform transformation.

The first goal of this paper is to prove that this conjecture is false, by exhibiting primitive groups that fail to synchronize specific non-uniform transformations of ranks 5 and 6. As it has previously been shown that primitive groups synchronize every non-uniform transformation of rank at most 4, these examples are of the lowest possible rank. In addition we produce graphs with primitive automorphism groups that have approximately √n non-synchronizing ranks, thus refuting another conjecture on the number of non-synchronizing ranks of a primitive group.

Determining the exact spectrum of ranks for which there exist non-uniform transformations not synchronized by some primitive group is just one of several natural, but possibly difficult, problems on automata, primitive groups, graphs and computational algebra arising from this work; these are outlined in the final section.

doi 10.1112/plms/pdw040; arXiv 1504.01629

Thomas Britz and Peter J. Cameron, Codes, Chapter 16 in Handbook of the Tutte Polynomial (ed. J. Ellis-Monaghan and I. Moffatt), , CRC Press, Boca Raton, 2022, pp. 328-344.

This chapter introduces linear codes and some of their properties, surveys how the Tutte polynomial determines these properties, and provides an overview of more general results as well as applications to coding theory.

doi: 10.1201/9780429161612-16

João Araújo, Wolfram Bentz and Peter J. Cameron, Orbits of primitive k-homogenous groups on (n−k)-partitions with applications to semigroups, Trans. Amer. Math. Soc. 371 (2019), 105-136

Let X be a finite set such that |X| = n, and let k < n/2. A group is k-homogeneous if it has only one orbit on the sets of size k. The aim of this paper is to prove some general results on permutation groups and then apply them to transformation semigroups. On groups we find the minimum number of permutations needed to generate k-homogeneous groups (for k ≥ 1); in particular we show that 2-homogeneous groups are 2-generated. We also describe the orbits of k-homogenous groups on partitions with n−k parts, classify the 3-homogeneous groups G whose orbits on (n−3)-partitions are invariant under the normalizer of G in S_n, and describe the normalizers of 2-homogeneous groups in the symmetric group. Then these results are applied to extract information about transformation semigroups with given group of units, namely to prove results on their automorphisms and on the minimum number of generators. The paper finishes with some problems on permutation groups, transformation semigroups and computational algebra.

doi: 10.1090/tran/7274; arXiv 1512.05608

Let λ = (λ₁,λ₂,…) be a partition of n, a sequence of positive integers in non-increasing order with sum n. Let Ω := {1,…,n}. An ordered partition P = (A₁,A₂,…) of Ω has type λ if |A_i| = λ_i.

Following Martin and Sagan, we say that G is λ-transitive if, for any two ordered partitions P = (A₁,A₂,…) and Q = (B₁,B₂,…) of Ω of type λ, there exists g∈G with A_ig = B_i for all i. A group G is said to be λ-homogeneous if, given two ordered partitions P and Q as above, inducing the sets P' and Q', there exists g∈G such that P'g = Q'. Clearly a λ-transitive group is λ-homogeneous.

The first goal of this paper is to classify the λ-homogeneous groups (Theorems 1.1 and 1.2). The second goal is to apply this classification to a problem isn semigroup theory.

Let T_n and S_n denote the transformation monoid and the symmetric group on Ω, respectively. Fix a group H ≤ T_n. Given a non-invertible transformation a in T_n and a group G ≤ S_n, we say that (a,G) is an H-pair if the semigroups generated by {a}∪H and {a}∪G contain the same non-units. Using the classification of the λ-homogeneous groups we classify all the S_n-pairs (Theorem 1.7). For a multitude of transformation semigroups this theorem immediately implies a description of their automorphisms, congruences, generators and other relevant properties (Theorem 8.5).

This topic involves both group theory and semigroup theory; we have attempted to include enough exposition to make the paper self-contained for researchers in both areas.

The paper finishes with a number of open problems on permutation and linear groups.

doi: 10.1016/j.jalgebra.2015.12.025; arXiv 1304.7391

Peter J. Cameron, Josephine Kusuma and Patrick Solé, Z₄-codes and their Gray map images as orthogonal arrays, Designs, Codes, Crypt. 84 (2017), 109-114.

A classic result of Delsarte connects the strength (as orthogonal array) of a linear code with the minimum weight of its dual: the former is one less than the latter.

Since the paper of Hammons et al., there is a lot of interest in codes over rings, especially in codes over Z₄ and their (usually non-linear) binary Gray map images.

We show that Delsarte's observation extends to codes over arbitrary finite rings. However, the connection between the strength of a Z₄-code and that of its Gray map image is more problematic. We conjecture that the strength of the Gray map image of C is one less than the minimum Lee weight of the dual of C, and give some evidence for this conjecture.

doi: 10.1007/s10623-016-0225-4; arXiv: 1510.01509

Peter J. Cameron, Maximilien Gadouleau, James D. Mitchell and Yann Peresse, Chains of subsemigroups, Israel J. Math.

We investigate the maximum length of a chain of subsemigroups in various classes of semigroups, such as the full transformation semigroups, the general linear semigroups, and the semigroups of order-preserving transformations of finite chains. In some cases, we give lower bounds for the total number of subsemigroups of these semigroups. We give general results for finite completely regular and finite inverse semigroups. Wherever possible, we state our results in the greatest generality; in particular, we include infinite semigroups where the result is true for these.

The length of a subgroup chain in a group is bounded by the logarithm of the group order. This fails for semigroups, but it is perhaps surprising that there is a lower bound for the length of a subsemigroup chain in the full transformation semigroup which is a constant multiple of the semigroup order.

doi: 10.1007/s11856-017-1523-x; arXiv 1501.06394

J. M. Howie, the influential St Andrews semigroupist, claimed that we value an area of pure mathematics to the extent that (a) it gives rise to arguments that are deep and elegant, and (b) it has interesting interconnections with other parts of pure mathematics.

This paper surveys some recent results on the transformation semigroup generated by a permutation group G and a single non-permutation a. Our particular concern is the influence that properties of G (related to homogeneity, transitivity and primitivity) have on the structure of the semigroup. In the first part of the paper, we consider properties of S=⟨G,a⟩ such as regularity and generation. The second is a brief report on the synchronization project, which aims to decide in what circumstances S contains an element of rank 1. The paper closes with a list of open problems on permutation groups and linear groups, and some comments about the impact on semigroups are provided.

These two research directions outlined above lead to very interesting and challenging problems on primitive permutation groups whose solutions require combining results from several different areas of mathematics, certainly fulfilling both of Howie's elegance and value tests in a new and fascinating way.

arXiv 1308.3585

Peter J. Cameron, Enumerative combinatorics, pp. 1-40 in Algebra, Logic and Combinatorics (ed. Shaun Bullett, Frank Smith and Tom Fearn), World Scientific, Singapore, 2016 (LTCC Advanced Mathematics Series, Vol. 3).

This chapter presents a very brief introduction to enumerative combinatorics. After a section on formal power series, it discusses examples of counting subsets, partitions and permutations; techniques for solving recurrence relations; the inclusion-exclusion principle; the Möbius function of a poset; q-binomial coefficients; and orbit-counting. A section on the theory of species (introduced by André Joyal) follows. The chapter concludes with a number of exercises, some of which are worked.

ISBN 978-1-78634-029-0

Peter J. Cameron, Maria Elisa Fernandes, Dimitri Leemans and Mark Mixer, String C-groups as transitive subgroups of Sym(n), J. Algebra 447 (2016), 468-478.

If Γ is a string C-group which is isomorphic to a transitive subgroup of the symmetric group Sym(n) (other than Sym(n) and the alternating group Alt(n)), then the rank of Γ is at most n/2+1, with finitely many exceptions (which are classified). It is conjectured that only the symmetric group has to be excluded.

doi: 10.1016/j.jalgebra.2015.09.040; arXiv 1410.5863

Peter J. Cameron, Anh N. Dang, and Søren Riis, Guessing games on triangle-free graphs, Electronic J. Combinatorics 23(1) (2016), Paper #1.48

The guessing game introduced by Riis is a variant of the "guessing your own hats" game and can be played on any simple directed graph G on n vertices. For each digraph G, it is proved that there exists a unique guessing number gn(G) associated to the guessing game played on G. When we consider the directed edge to be bidirected, in other words, the graph G is undirected, Christofides and Markstom introduced a method to bound the value of the guessing number from below using the fractional clique number Kf(G). In particular they showed gn(G) ≥ |V(G)|−Kf(G). Moreover, it is pointed out that equality holds in this bound if the underlying undirected graph G falls into one of the following categories: perfect graphs, cycle graphs or their complement. In this paper, we show that there are triangle-free graphs that have guessing numbers which do not meet the fractional clique cover bound. In particular, the famous triangle-free Higman–Sims graph has guessing number at least 77 and at most 78, while the bound given by fractional clique cover is 50.

Full text; arXiv 1410.2405

R. A. Bailey, Peter J. Cameron, Katarzyna Filipiak, Joachim Kunert and Augustyn Markiewicz, On optimality and construction of circular repeated-measurements designs, Statistica Sinica 27 (2017), 1-22.

The aim of this paper is to characterize and construct universally optimal designs among the class of circular repeated-measurements designs when the parameters do not permit balance for carry-over effects. It is shown that some circular weakly neighbour balanced designs defined by Filipiak and Markiewicz are universally optimal repeated-measurements designs. These results extend the work of Magda, Kunert, Filipiak and Markiewicz.

doi: 10.5705/ss.202015.0045; arXiv 1410.1661

Peter J. Cameron and Cheryl E. Praeger, Constructing flag-transitive, point-imprimitive designs, J. Algebraic Combinatorics 43 (2016), 755-769.

doi: 10.1007/s10801-015-0591-4; arXiv 1408.6598

Peter J. Cameron and Sebastian M. Cioabă, A graph partition problem, Amer. Math. Monthly 122 (2015), 972-983.

Given a graph G on n vertices, for which m is it possible to partition the edge set of the m-fold complete graph mK_n into copies of G? We show that there is an integer m₀, which we call the partition modulus of G, such that the set M(G) of values of m for which such a partition exists consists of all but finitely many multiples of m₀. Trivial divisibility conditions derived from G give an integer m₁ which divides m₀; we call the quotient m₀/m₁ the partition index of G. It seems that most graphs G have partition index equal to 1, but we give two infinite families of graphs for which this is not true. We also compute M(G) for various graphs, and outline some connections between our problem and the existence of designs of various types.

arXiv 1408.0371

Peter J. Cameron and Pablo Spiga, Most switching classes with primitive automorphism groups contain graphs with trivial groups, Australasian J. Combinatorics 62 (2015), 76-90.

The operation of switching a graph Γ with respect to a subset X of the vertex set interchanges edges and non-edges between X and its complement, leaving the rest of the graph unchanged. This is an equivalence relation on the set of graphs on a given vertex set, so we can talk about the automorphism group of a switching class of graphs.

It might be thought that switching classes with many automorphisms would have the property that all their graphs also have many automorphisms. However the main theorem of this paper shows a different picture: with finitely many exceptions, if a non-trivial switching class S has primitive automorphism group, then it contains a graph whose automorphism group is trivial. We also find all the exceptional switching classes; up to complementation, there are just six.

Full text; arXiv 1407.5288

Peter J. Cameron, Ben Fairbairn and Maximilien Gadouleau, Computing in matrix groups without memory, Chicago J. Theor. Computer Sci., Vol 2014, article 8

Full text; doi: 10.4086/cjtcs.2014.008; arXiv 1310.6009

Peter J. Cameron, Ben Fairbairn and Maximilien Gadouleau, Computing in permutation groups without memory, Chicago J. Theor. Computer Sci., Vol 2014, article 7

Full text; doi: 10.4086/cjtcs.2014.007; arXiv 1310.6008

László Babai and Peter J. Cameron, Most primitive groups are full automorphism groups of edge-transitive hypergraphs, J. Algebra 421 (2015), 512–523.

We prove that, for a primitive permutation group G acting on a set of size n, other than the alternating group, the probability that Aut(X,Y^G) = G for a random subset Y of X, tends to 1 as n tends to infinity. So the property of the title holds for all primitive groups except the alternating groups and finitely many others. This answers a question of M. Klin. Moreover, we give an upper bound n^1/2+ε for the minimum size of the edges in such a hypergraph. This is essentially best possible.

doi 10.1016/j.jalgebra.2014.09.002; arXiv 1404.3585

João Araújo and Peter J. Cameron, Primitive groups synchronize non-uniform maps of extreme ranks, J. Combinatorial Theory (B) 106 (2014), 98-114.

Let Ω be a set of cardinality n, G a permutation group on Ω, and f:Ω→Ω a map which is not a permutation. We say that G synchronizes f if the semigroup ⟨G,f⟩ contains a constant map.

The first author has conjectured that a primitive group synchronizes any map whose kernel is non-uniform. Rystsov proved one instance of this conjecture, namely, degree n primitive groups synchronize maps of rank n−1 (thus, maps with kernel type (2,1,…,1)). We prove some extensions of Rystsov's result, including this: a primitive group synchronizes every map whose kernel type is (k,1,…,1). Incidentally this result provides a new characterization of imprimitive groups. We also prove that the conjecture above holds for maps of extreme ranks, that is, ranks 3, 4 and n−2.

These proofs use a graph-theoretic technique due to the second author: a transformation semigroup fails to contain a constant map if and only if it is contained in the endomorphism semigroup of a non-null (simple undirected) graph.

The paper finishes with a number of open problems, whose solutions will certainly require very delicate graph theoretical considerations.

doi 10.1016/j.jctb.2014.01.006; arXiv 1306.4827

João Araújo and Peter J. Cameron, Permutation groups and transformation semigroups: results and problems, Proceedings of Groups St Andrews 2013

J. M. Howie, the influential St Andrews semigroupist, claimed that we value an area of pure mathematics to the extent that (a) it gives rise to arguments that are deep and elegant, and (b) it has interesting interconnections with other parts of pure mathematics.

This paper surveys some recent results on the transformation semigroup generated by a permutation group G and a single non-permutation a. Our particular concern is the influence that properties of G (related to homogeneity, transitivity and primitivity) have on the structure of the semigroup. In the first part of the paper, we consider properties of S = ⟨G,a⟩ such as regularity and idempotent generation. The second is a brief report on the synchronization project, which aims to decide in what circumstances S contains an element of rank 1. The paper closes with a list of open problems on permutation groups and linear groups, and some comments about the impact on semigroups are provided.

These two research directions outlined above lead to very interesting and challenging problems on primitive permutation groups whose solutions require combining results from several different areas of mathematics, certainly fulfilling both of Howie's elegance and value tests in a new and fascinating way.

arXiv 1308.3585

Joshua M. Browning, Peter J. Cameron and Ian M. Wanless, Bounds on the number of small Latin subsquares, J. Combinatorial Theory (A) 124 (2014), 41-56.

Let ζ(n,m) be the largest number of order m subsquares achieved by any Latin square of order n. We show that ζ(n,m) = Θ(n³) if m ∈ {2,3,5} and ζ(n,m) = (n⁴) if m ∈ {4,6,9,10}. In particular, (1/8)n³+O(n²) ≤ ζ(n,2) ≤ (1/4)n³+O(n²) and (1/27)n³+O(n^5/2) ≤ ζ(n,3) ≤ (1/18)n³+O(n²) for all n. We find an explicit bound on ζ(n,2^d) of the form Θ(n^d+2) and which is achieved only by elementary abelian 2-groups.

For a fixed Latin square L let ζ*(n,L) be the largest number of subsquares isotopic to L achieved by any Latin square of order n. When L is a cyclic Latin square we show that ζ*(n,L) = Θ(n³). For a large class of Latin squares L we show that ζ*(n,L) = O(n³). For any Latin square L we give an ε in the interval (0,1) such that ζ*(n,L) ≥ Ω(n^2+ε). We belive that this bound is achieved for certain squares L.

doi 10.1016/j.jcta.2014.01.002

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.

doi 10.1007/978-1-4614-7254-4_22; arXiv 1301.7544

Peter J. Cameron, Groups with right-invariant multiorders, Australasian J. Combinatorics 56 (2013), 187-193.

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.

Full text; arXiv 1209.3220

Peter Cameron, Claude Laflamme, Maurice Pouzet, Sam Tarzi, Robert Woodrow, Overgroups of the Automorphism Group of the Rado Graph, pp. 45-54 in Asymptotic Geometric Analysis (ed. Monika Ludwig, Vitali D. Milman, Vladimir Pestov and Nicole Tomczak-Jaegermann), Fields Inst. Communications 68, Springer 2013; ISBN 978-1-4614-6405-1.

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.

arXiv 1205.3717

João Araújo, Wolfram Bentz and Peter J. Cameron, Groups synchronizing a transformation of non-uniform kernel, Theoretical Computer Science 498 (2013), 1-9.

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

doi 10.1016/j.tcs.2013.06.016; arXiv 1205.0682

João Araújo, Peter J. Cameron, James Mitchell and Max Neunhöffer, The classification of normalizing groups, J. Algebra 373 (2013), 481-490

Let X be a finite set such that |X| = n. Let T_n and S_n denote respectively the transformation monoid and the symmetric group on n points. Given a∈T_n\S_n, we say that a group G ≤ S_n is a-normalizing if ⟨a,G⟩\G = ⟨g⁻¹ag | g∈G⟩. If G is a-normalizing for all a∈T_n\S_n, the we say that G is normalizing. The goal of this paper is to classify normalizing groups and hence answer a question posed elsewhere. The paper ends with a number of problems for experts in groups, semigroups and matrix theory.

doi: 10.1016/j.jalgebra.2012.08.033; arXiv 1205.0450

João Araújo and Peter J. Cameron, Two generalizations of homogeneity in groups with applications to regular semigroups, Trans. Amer. Math. Soc. 368 (2016), 1159-1188

Let X be a finite set such that |X|=n and let i≤j≤n. A group G≤S_n is said to be (i,j)-homogeneous if for every I,J⊆X, such that |I|=i and |J|=j, there exists g∈G such that Ig⊆J. (Clearly (i,i)-homogeneity is i-homogeneity in the usual sense.)

A group G≤S_n is said to have the k-universal transversal property if given any set I⊆X (with |I|=k) and any partition P of X into k blocks, there exists g∈G such that Ig is a section for P. (That is, the orbit of each k-subset of X contains a section for each k-partition of X.)

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.

doi 10.1090/tran/6368; arXiv 1204.2195

Peter J. Cameron, Aftermath: a personal view of combinatorics, Combinatorics Ancient and Modern (ed. J. J. Watkins and R. J. Wilson), Oxford University Press, 2013; ISBN 978-0-19-965659-2.

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.

arXiv 1111.4050

R. A. Bailey and Peter J. Cameron, Using graphs to find the best block designs, pp. 282-317 in Topics in Structural Graph Theory (ed. L. W. Beineke and R. J. Wilson), Encyclopedia of Mathematics and its Applications 147, Cambridge University Press, 2013

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.

arXiv 1111.3768

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+2k, 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.

arXiv 1111.3507

Peter J. Cameron and Maximilien Gadouleau, Remoteness of permutation codes, Europ. J. Combinatorics 33 (2012), 1273-1285

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.

doi: 10.1016/j.ejc.2012.03.027; arXiv 1110.2028

Peter J. Cameron, Maximilien Gadouleau and Søren Riis, Combinatorial representations, Combinatorial representations, J. Combinatorial Theory (A) 120 (2013), 671-682.

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.

doi 10.1016/j.jcta.2012.12.002; arXiv 1109.1216

Peter J. Cameron, Dixon's Theorem and random synchronization, Discrete Mathematics 313 (2013), 1233-1236.

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 k random transformations is synchronizing?

The question has some similarities with a similar question about the probability that the subgroup of S_n generated by k random permutations is transitive. For k=1, the answer is 1/n; for k=2, Dixon's Theorem asserts that it is 1-o(1) as n→∞ (and good estimates are now known). For our synchronization question, for k=1 the answer is also 1/n; I conjecture that for k=2 it is also 1-o(1).

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.

doi 10.1016/j.disc.2012.06.002; arXiv 1108.3958

Peter J. Cameron, Christian Krattenthaler and Thomas W. Müller, Decomposable functors and the exponential principle, II, Séminaire Lotharingien de Combinatoire 61A (2010), Article B61Am.

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.

Full text; arXiv 0911.3760

Peter J. Cameron, Christian Krattenthaler and Thomas W. Müller, A note on higher-dimensional magic matrices, Australasian J. Combinatorics 50 (2011), 207-217.

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.

Full text; arXiv 1104.4938

Adam Bohn, Peter J. Cameron and Peter Müller, Galois groups of multivariate Tutte polynomials, J. Algebraic Combinatorics 36 (2012), 223-230.

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 e of the ground set. It encodes the full structure of M. Let v = {v_e}, let K be an arbitrary field, and suppose M is connected. We prove that Z^_M is irreducible over K(v), and show that the Galois group of Z^_M over K(v) is the symmetric group of degree n, where n is the rank of M. An immediate consequence of this result is that the Galois group of the multivariate Tutte polynomial of any matroid is a direct product of symmetric groups. We also report on the implications of our work for the graph-theoretical formulation of the multivariate Tutte polynomial. In particular we show that our main theorem holds for biconnected graphs, and conjecture a similar result for the standard Tutte polynomial of such a graph.

doi 10.1007/s10801-011-0332-2; arXiv 1006.3869

P. J. Cameron (editor), Problems from BCC22, Discrete Math. 311 (2011), 1074-1083.

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.

doi 10.1016/j.disc.2011.02.024

Robert F. Bailey and Peter J. Cameron, Base size, metric dimension and other invariants of groups and graphs Bull. London Math. Soc. 43 (2011), 209-242.

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.

doi 10.1112/blms/bdq096

Peter J. Cameron and Shamik Ghosh, The power graph of a finite group, Discrete Math. 311 (2011), 1220-1222.

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.

doi 10.1016/j.disc.2010.02.011

P. J. Cameron and B. S. Webb, Perfect countably infinite Steiner triple systems, Australasian J. Combinatorics 54 (2012), 273-278.

We use a free construction to prove the existence of perfect Steiner triple systems on a countably infinite point set. We use a specific countably infinite family of partial Steiner triple systems to start the construction, thus yielding 2^ℵ₀ non-isomorphic perfect systems.

Journal paper

Tatiana Gateva-Ivanova and Peter Cameron, Multipermutation solutions of the Yang–Baxter equation, Comm. Math. Phys. 309 (2012), 589-631.

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.

doi 10.1007/s00220-011-1394-7; arXiv 0907.4276

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.

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

doi 10.1016/j.disc.2008.10.021

Peter J. Cameron, Oligomorphic permutation groups, Perspectives in Mathematical Sciences, ed. N.S.N. Sastry, Mohan Delampady, B. Rajeev and T.S.S.R.K. Rao, World Scientific, Singapore, 2009, pp. 37-61; ISBN 978-981-4273-64-0.

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

arXiv 0803.0302; journal paper

Peter J. Cameron and Ross Applegate, Orbits on n-tuples, Communications in Algebra 37 (2009), 269-275.

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.

doi 10.1080/00927870802243739

Peter J. Cameron and Priscila A. Kazanidis, Cores of symmetric graphs, J. Australian Math. Soc. 85 (2008), 145-154.

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

doi 10.1017/S1446788708000815

Peter J. Cameron, A generalisation of t-designs, Discrete Math. 309 (2009), 4835-4842.

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.

doi 10.1016/j.disc.2008.07.005

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.

arXiv 0801.3013

Robert F. Bailey and Peter J. Cameron, On the single-orbit conjecture for uncoverings-by-bases, J. Group Theory 11 (2008), 845-850.

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.

doi 10.1515/JGT.2008.053

Peter Cameron, Thomas Prellberg and Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, Discrete Math. 310 (2010), 230-240.

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, t_n, on [n] both have asymptotic growth

B_2n2^-nexp(-½log(2n/log n))

B_2n2^-nn^-½exp(-[½log(2n/log n)]²).

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.

doi 10.1016/j.disc.2008.09.008

P. J. Cameron, Root systems and optimal block designs, Michigan Math. J. 58 (2009), 181-194.

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.

doi 10.1307/mmj/1242071687

P. J. Cameron (editor), Problems from CGCS Luminy, Europ. J. Combinatorics 31 (2010), 644-648.

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.

doi 10.1016/j.ejc.2009.03.045

P. J. Cameron, Permutation codes, Europ. J. Combinatorics 31 (2010), 482-490.

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.

doi 10.1016/j.ejc.2009.03.044

R. A. Bailey and P. J. Cameron, What is a design? How should we classify them? Designs, Codes, Crypt 44 (2007), 223-238.

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.

doi 10.1007/s10623-007-9092-3

P. J. Cameron and A. Rudvalis, A design and a geometry for the Fischer group Fi₂₂, Designs, Codes, Crypt. 44 (2007), 11-14.

The Fischer group Fi₂₂ 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.

doi 10.1007/s10623-007-9041-1

C. Buchheim, P. J. Cameron and T. Wu, On the subgroup distance problem, Discrete Math. 309 (2009), 962-968.

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 pi in S_n, for different metrics on S_n. We assume that H is given by a set of generators, and is such that the problem cannot be solved in polynomial time by exhaustive enumeration. For the case of the Cayley distance, this problem has been shown to be NP-hard, even if H is abelian of exponent 2. We present a much simpler proof of this result, which also works for the Hamming distance, the l_p distance, Lee's distance, Kendall's tau, and Ulam's distance. Moreover, we give an NP-hardness proof for the l_infty distance using a different reduction idea. Finally, we settle the complexity of the corresponding fixed-parameter and maximization problems.

doi 10.1016/j.disc.2008.01.036

Peter J. Cameron and D. Lockett, Posets, homomorphisms and homogeneity, Discrete Math. 310 (2010), 604-613.

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.

doi 10.1016/j.disc.2009.04.027

Peter J. Cameron and Leonard H. Soicher, Block intersection polynomials, Bull. London Math. Soc. 39 (2007), 559-564.

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.

doi 10.1112/blms/bdm034

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.

arXiv 0608016; journal paper

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.

doi 10.1016/j.disc.2009.03.005

P. J. Cameron, M. Kang and D. Stark, Random preorders and alignments, Discrete Math. 310 (2010), 591-603.

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.

doi 10.1016/j.disc.2009.04.021

P. J. Cameron and K. K. Kayibi, Orbital chromatic and flow roots, Combinatorics, Probability and Computing 16 (2007), 401-407.

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.

doi 10.1017/S0963548306008200

R. A. Bailey, Peter J. Cameron and Robert Connelly, Sudoku, gerechte designs, resolutions, affine space, spreads, reguli, and Hamming codes, American Math. Monthly 115 (2008), 383-404.

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, Revista Matemática Iberoamericana 23 (2007), 385-395.

We show that the number of monochromatic solutions of the equation x₁^α1x₂^α2...x_r^α_r=g in a 2-coloring of a finite group G, where α₁,...,α_r are permutations and g in G, depends only on the cardinalities of the chromatic classes but not on their distribution. We give some applications to arithmetic Ramsey statements.

Peter Cameron, Thomas Prellberg and Dudley Stark, Asymptotic enumeration of incidence matrices, J. Physics : Conference Series 42 (2006), 59-70.

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.

arXiv 0511008

Peter Cameron, Thomas Prellberg and Dudley Stark, Asymptotics for incidence matrix classes, Electronic J. Combinatorics 13 (2006), #R85 (19pp.)

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.

arXiv 0510155; journal paper

R. A. Bailey and Peter J. Cameron, A family of balanced incomplete-block designs with repeated blocks on which general linear groups act, J. Combinatorial Designs 15 (2007), 143-150.

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.

doi 10.1002/jcd.20120

P. J. Cameron, Aspects of infinite permutation groups, Groups St Andrews 2005 volume 1 (ed. C. M. Campbell, M. R. Quick, E. F. Robertson and G. C. Smith), London Math. Soc. Lecture Notes 339, Cambridge Univ. Press, Cambridge, 2007, pp. 1-35; ISBN 0-521-69469-8.

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, Discrete Math. 308 (2008), 920-930.

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 ia=0 in the group A. In particular, unlike the case of counting nowhere-zero flows, the answer depends on the structure of A, not just on its order.)

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.

doi 10.1016/j.disc.2007.07.108

P. J. Cameron, J. Sheehan and P. Spiga, Semiregular automorphisms of vertex-transitive cubic graphs, European J. Combinatorics 27 (2006), 924-930.

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, Embedding partial Steiner triple systems so that their automorphisms extend, J. Combinatorial Design 13 (2005), 466-470.

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.

Peter J. Cameron, Finite geometry and permutation groups: some polynomial links, Rendiconti di Matematica (VII) 26 (2006), 339-350.

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, Ann. Pure Appl. Logic 143 (2006), 70-78.

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, Communications in Algebra 35 (2007), 3026-3033.

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 X. Next we use this result to deduce a complete classification of these groups for k>2.

doi 10.1080/00927870701404812

Peter Cameron and Norbert Knarr, Tubes in PG(3,q), Europ. J. Combinatorics 27 (2006), 114-124.

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. Nešetřil, Homomorphism-homogeneous relational structures, Combinatorics, Probability and Computing 15 (2006), 91-103.

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, J. London Math. Soc. 72 (2005), 1-24.

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 r=1,2, each having an inherent partition F_r (that is, a partition whose equivalence relation is a union of adjacency relations in the association scheme), we define a product of the two schemes, which reduces to the direct product if F₁=U₁ or F₂=E₂, and to the wreath product if F₁=E₁ and F₂=U₂, where E_r and U_r are the relation of equality and the universal relation on Q_r. We calculate the character table of the crested product, and show that if the two schemes Q₁ and Q₂ have formal duals, then so does their crested product (and we give a simple description of this dual). We make an analogous definition for permutation groups with intransitive normal subgroups, and show that the constructions for association schemes and permutation groups are related in a natural way.

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, Discrete Math. 306 (2006), 33014-3027.

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, Discrete Math. 306 (2006), 3051-3053.

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, Discrete Math. 306 (2006), 3074-3077.

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,q), Discrete Math. 306 (2006), 3063-3073.

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

Peter J. Cameron and Alexander W. Dent, Orbit-homogeneity in permutation groups, J. London Math. Soc. 38 (2006), 597-606.

Peter J. Cameron and Thomas W. Müller, A descent principle in modular subgroup arithmetic, J. Pure Appl. Algebra 203 (2005), 189-203.

We establish and comment on a surprising relationship between the behaviour modulo a prime p of the number s_n(G) of index n subgroups in a group G, and that of the corresponding subgroup numbers for a subnormal subgroup of p-power index in G. One of the applications of this result presented here concerns the explicit determination modulo p of s_n(G) in the case when G is the fundamental group of a finite graph of finite p-groups. As another application, we extend one of the main results of the second author's paper concerning the p-patterns of free powers G^*q of a finite group G with q a p-power to groups of the more general form H * G^*q, where H is any finite p-group.

Peter J. Cameron and Ian M. Wanless, Covering radius for sets of permutations, Discrete Math. 293 (2005), 91-109.

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 n−s. We study f(n,s) in the general case and also in the case when the set of permutations forms a group.

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 p-groups, Archiv der Mathematik 82 (2004), 200-204.

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

Peter J. Cameron, Daniele A. Gewurz and Francesca Merola, Product action, Discrete Math. 308 (2008), 386-394.

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.

doi 10.1016/j.disc.2006.11.054

Peter J. Cameron and C. Y. Ku, Intersecting families of permutations, Europ. J. Combinatorics 24 (2003), 881-890.

Peter J. Cameron and Sam Tarzi, Switching with more than two colours, Europ. J. Combinatorics 25 (2004), 169-177.

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, Electronic J. Combinatorics 9(2) (2002), #R2 (9pp).

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.

Journal paper

Peter J. Cameron and Ph. Cara, Independent generating sets and geometries for symmetric groups, J. Algebra 258 (2002), 641-650.

Julius Whiston showed that the size of an independent generating set in the symmetric group S_n is at most n−1. We determine all sets meeting this bound. We also give some general remarks on the maximum size of an independent generating set of a group and its relationship to coset geometries for the group. In particular, we determine all coset geometries of maximum rank for the symmetric group S_n for n>6.

Peter J. Cameron, Cycle index, weight enumerator and Tutte polynomial, Electronic J. Combinatorics 9(1) (2002), #N2 (10pp).

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.

Journal paper

Peter J. Cameron, Random strongly regular graphs? Discrete Math. 273 (2003), 101-112.

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, European J. Combinatorics 23 (2002), 257-274.

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? J. Combinatorial Design 10 (2002), 79-91.

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 < 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 Groups, Combinatorics and Geometry (ed. A. A. Ivanov, M. W. Liebeck and J. Saxl), World Scientific, Singapore, 2003.

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, Discrete Math. 266 (2003), 47-67.

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₈ 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 n-e.c. property, Electronic J. Combinatorics 9(1) (2002), #R31 (12pp).

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₁, v₂ depends only on whether or not v₁ and v₂ 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)² exist whenever q is a prime power at least 16n²2²ⁿ and congruent to 3 mod 4.

Journal paper

Peter J Cameron, Strongly regular graphs(1); Automorphisms of graphs(2), two chapters in in Topics in Algebraic Graph Theory (ed. L. W. Beineke and R. J. Wilson), Cambridge Univ. Press, Cambridge, 2004 (ISBN 0521801974), pp. 203-221 and 137-155.

2. 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, Discrete Math. 266 (2003), 143-151.

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²ⁿ 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 Groups: Topological, Combinatorial and Arithmetic Aspects (ed. T. W. Müller), London Math. Soc. Lecture Notes 311, Cambridge University Press, Cambridge, 2004, pp. 93-105.

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, J. London Math. Soc. (2) 66 (2002), 325-333.

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 Finite Geometries: Proceedings of the Fourth Isle of Thorns Conference (ed. A. Blokhuis, J. W. P. Hirschfeld, D. Jungnickel and J. A. Thas), Kluwer, Boston, 2001.

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.

Peter J. Cameron, The random graph revisited, in European Congress of Mathematics, Barcelona, July 10-14, 2000, Volume II (ed. C. Casacuberta, R. M. Miró-Roig, J. Verdera and S. Xambó-Descamps), Birkhäuser, Basel, 2001, pp. 267-274.

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.

Peter J. Cameron, Partitions and permutations, Discrete Math. 291 (2005), 45-54.

With any permutation g of a set Ω is associated a partition of Ω 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 Ω, or of partitions of n (the cardinality of Ω), 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, Discrete Math. 291 (2005), 41-43.

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 k fixed points, J. Group Theory 4 (2001), 45-51.

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.

Peter J. Cameron, Sequences realized by oligomorphic permutation groups, Journal of Integer Sequences 3 (2000), article 00.1.5.

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 Paul Erdős and his Mathematics, Vol. II, Bolyai Society Mathematical Studies 11, Budapest, 2002.

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

Peter Cameron and Wilfrid Hodges, Some combinatorics of imperfect information, J. Symbolic Logic 66 (2001), 673-684.

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.

Peter J. Cameron (editor), Problems on discrete metric spaces, European Journal of Combinatorics 21 (2000), 831-838.

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.

Peter J. Cameron, Homogeneous Cayley objects, European Journal of Combinatorics 21 (2000), 745-760.

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.

Peter J. Cameron, SGDs with 2-transitive automorphism group, J. Graph Theory 32 (1999), 229–233.

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.

Peter J. Cameron, An extremal problem related to biplanes, Australasian J. Combinatorics 20 (1999), 97-100.

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.

Journal paper

Peter J. Cameron, Some counting problems related to permutation groups, Discrete Math. 225 (2000), 77-92.

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.

Peter J. Cameron and Csaba Szabó, Independence algebras, J. London Math. Soc. (2) 91 (2000), 321-334.

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.

L. Babai and P. J. Cameron, Automorphisms and enumeration of switching classes of tournaments, Electronic J. Combinatorics 7(1) (2000), article #R38.

Two tournaments T₁ and T₂ on the same vertex set X are said to be switching equivalent if X has a subset Y such that T₂ arises from T₁ 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é).

Journal paper

E. A. Bender, P. J. Cameron, A. M. Odlyzko and B. L. Richmond, Connectedness, classes, and cycle index, Combinatorics, Probability and Computing 8 (1999), 31-43.

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.

Peter J. Cameron and Paul Erdős, Notes on sum-free and related sets, Combinatorics, Probability and Computing, 8 (1999), 95-107.

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.

Peter J. Cameron, A census of infinite distance-transitive graphs, Discrete Math. 192 (1998), 11-26.

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.

Peter J. Cameron, On an algebra related to orbit-counting, J. Group Theory 1 (1998), 173-179.

Neil J. Calkin and Peter J. Cameron, Almost odd random sum-free sets, Combinatorics, Probability and Computing 7 (1998), 27-32.

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

Peter J. Cameron, On the probability of connectedness, Discrete Mathematics 167/168 (1997), 173-185.

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.

Peter J. Cameron, The algebra of an age, in Model Theory of Groups and Automorphism Groups (ed. David M. Evans), LMS Lecture Notes 244, Cambridge University Press, 1997, pp. 173-185.

Associated with any oligomorphic permutation group G, there is a graded algebra A^G such that the dimension of its n-th homogeneous component is equal to the number of G-orbits on n-sets. I show that the algebra is a polynomial algebra (free commutative associative algebra) in some cases, and pose some questions about transitive extensions.

A. R. Calderbank, P. J. Cameron, W. M. Kantor and J. J. Seidel, Z₄-Kerdock Codes, Orthogonal Spreads, and Extremal Euclidean Line-Sets, Proc. London Math. Soc. (3) 75 (1997), 436-480.

When m is odd, spreads in an orthogonal vector space of type Ω⁺(2m+2,2) are related to binary Kerdock codes and extremal line-sets in R^2m+1> with prescribed angles. Spreads in a 2m-dimensional binary symplectic vector space are related to Kerdock codes over Z₄ and extremal line-sets in C^2m with prescribed angles. These connections involve binary, real and complex geometry associated with extraspecial 2-groups. A geometric map from symplectic to orthogonal spreads is shown to induce the Gray map from a corresponding Z₄-Kerdock code to its binary image. These geometric considerations lead to the construction of d(m)−1 inequivalent Z₄-linear Kerdock codes and d(m)−1 inequivalent Z₄-linear Preparata codes of length 2^m for any odd m, where d(m) denotes the number of divisors of m.

Peter J. Cameron, Aspects of cofinitary permutation groups, pp. 93-99 in Advances in Algebra and Model Theory (ed. M. Droste and R. Gobel), Gordon and Breach, 1997.

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.

Peter J. Cameron, Finite geometries after Aschbacher's theorem: PGL(n,q) from a Kleinian viewpoint, in Geometry, Combinatorial Designs and Related Structures (ed. J. W. P. Hirschfeld, S. S. Magliveras and M. J. de Resmini), LMS Lecture Notes 245, Cambridge University Press, 1997, pp. 43-61.

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.

Peter J. Cameron, Oligomorphic groups and homogeneous graphs, in Graph Symmetry (ed. G. Hahn and G. Sabidussi), Kluwer, Dordrecht, 1997, pp. 23-74.

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.

Peter J. Cameron, Graphs and first-order logic, Graph Connections (ed. L. W. Beineke and R. J. Wilson), Oxford University Press 1997, pp. 70-85.

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.

Peter J. Cameron, Graphs and groups, Graph Connections (ed. L. W. Beineke and R. J. Wilson), Oxford University Press 1997, pp. 128-140.

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.

Peter J. Cameron, The random graph, in The Mathematics of Paul Erdős II (ed. R. L. Graham and J. Nesetril), Springer, Berlin, 1996, pp. 333-351.

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.

Peter J. Cameron, Stories about groups and sequences, Designs, Codes, Cryptography 8 (1996), 109-134.

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.

Peter J. Cameron, Metric and topological aspects of the symmetric group of countable degree, European J. Combinatorics 17 (1996), 135-142.

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.

Peter J. Cameron, Cycle-closed permutation groups, J. Algebraic Combinatorics 5 (1996), 315-322.

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.

Peter J. Cameron, Cofinitary permutation groups, Bull. London Math. Soc. 28 (1996), 113-140.

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.

Peter J. Cameron, Sequence operators from groups, Linear Algebra and Applications 226-228 (1995), 109-113.

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.

P. J. Cameron and D. G. Fon-Der-Flaass, Bases for groups and matroids, Europ. J. Combinatorics 16 (1995), 537-544.

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.

Peter J. Cameron
6 December 2022