|
Peter Cameron's abstracts |
Peter J. Cameron, Groups with right-invariant multiorders
A Cayley object for a group G is a structure on which G acts regularly as a group of automorphisms. The main theorem asserts that a necessary and sufficient condition for the free abelian group G of rank m to have the generic n-tuple of linear orders as a Cayley object is that m>n. The background to this theorem is discussed. The proof uses Kronecker's Theorem on diophantine approximation.
Peter Cameron, Claude Laflamme, Maurice Pouzet, Sam Tarzi, Robert Woodrow, Overgroups of the Automorphism Group of the Rado Graph
We are interested in overgroups of the automorphism group of the Rado graph. One class of such overgroups is completely understood; this is the class of reducts. In this article we tie recent work on various other natural overgroups, in particular establishing group connections between them and the reducts.
João Araújo, Wolfram Bentz and Peter J. Cameron, Groups synchronizing a transformation of non-uniform kernel
This paper concerns the general problem of classifying the deterministic automata that admit a synchronizing (or reset) word. (For our purposes it is irrelevant if the automata have initial or finite states.) Our departure point is the study of the transition semigroup associated to the automaton and then we take advantage of the enormous and very deep progress made during the last decades on the theory of permutation groups, their geometry and combinatorial structure. Our main results provide infinite families of automata admitting a synchronizing (or reset) word.
Let X be a finiote set and let G be a primitive group of permutations on X. It is well known (by some recent results proved by P. M. Neumann) that for some such G and some singular transformations t of uniform kernel (that is, all blocks have the same number of elements), the semigroup ⟨G,g⟩ does not generate a constant map. We say that a primitive group G on X is almost synchronizing if G together with any map of non-uniform kernel generates a constant. In this paper we provide two methods to build almost synchronizing groups and provide several families of such groups.
The paper ends with a number of problems likely to attract the attention of experts in computer science, combinatorics and geometry, groups and semigroups, linear algebra and matrix theory.
João Araújo, Peter J. Cameron, James Mitchell and Max Neunhöffer, The classification of normalizing groups
Let X be a finite set such that |X| = n. Let Tn and Sn denote respectively the transformation monoid and the symmetric group on n points. Given a∈Tn\Sn, we say that a group G ≤ Sn is a-normalizing if ⟨a,G⟩\G = ⟨g−1ag | g∈G⟩. If G is a-normalizing for all a∈Tn\Sn, 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.
João Araújo and Peter J. Cameron, Two generalizations of homogeneity in groups with applications to regular semigroups
Let X be a finite set such that |X|=n and let i≤j≤n. A group G≤Sn 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≤Sn 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.
Peter J. Cameron, Aftermath
I take a quick overview at the recent development of combinatorics and its current directions, as a discipline in its own right, as part of mathematics, and as part of science and wider society.
R. A. Bailey and Peter J. Cameron, Using graphs to find the best block designs
A statistician designing an experiment wants to get as much information as possible from the data gathered. Often this means the most precise estimate possible (that is, an estimate with minimum possible variance) of the unknown parameters. If there are several parameters, this can be interpreted in many ways: do we want to minimize the average variance, or the maximum variance, or the volume of a confidence region for the parameters?
In the case of block designs, these optimality criteria can be calculated from the concurrence graph of the design, and in many cases from its Laplacian eigenvalues. The Levi graph can also be used. The various criteria turn out to be closely connected with other properties of the graph as a network, such as number of spanning trees, isoperimetric number, and the sum of the resistances between pairs of vertices when the graph is regarded as an electrical network.
In this chapter, we discuss the notions of optimality for incomplete-block designs, explain the graph-theoretic connections, and prove some old and new results about optimality.
P. J. Cameron and D. A. Preece, Three-factor decompositions of Un with the generators in arithmetic progression
Irrespective of whether n is prime, prime power with exponent >1, or composite, the group Un of units of Zn can sometimes be obtained as the direct product of cyclic groups generated by x, x+k and x+2k, for x,k∈Zn. Indeed, for many values of n, many distinct 3-factor decompositions of this type exist. The circumstances in which such decompositions exist are examined. Many decompositions have additional interesting properties. We also look briefly at decompositions of the multiplicative groups of finite fields.
Peter J. Cameron and Maximilien Gadouleau, Remoteness of permutation codes
We define a new parameter, called remoteness, of a subset of a finite metric space. It is related to domination and is, in a sense, dual to covering radius. We study this parameter in the symmetric group (with the Hamming metric, where the distance between two permutations is the number of positions in which they differ). We obtain a number of results for sets and groups of permutations. In particular, the remoteness of a transitive permutation group of degree n is either n or n−1, and we give a number of results about which possibility occurs, though without resolving the question completely.
Peter J. Cameron, Maximilien Gadouleau and Søren Riis, Combinatorial representations
This paper introduces combinatorial representations, which generalise the notion of linear representations of matroids. We show that any family of subsets of the same cardinality has a combinatorial representation via matrices. We then prove that any graph is representable over all alphabets of size larger than some number depending on the graph. We also provide a characterisation of families representable over a given alphabet. Then, we associate a rank function and a rank operator to any representation which help us determine some criteria for the functions used in a representation. While linearly representable matroids can be viewed as having representations via matrices with only one row, we conclude this paper by an investigation of representations via matrices with only two rows.
Peter J. Cameron, Dixon's Theorem and random synchronization
A transformation monoid on a set Ω is called synchronizing if it contains an element of rank 1 (that is, mapping the whole of Ω to a single point). In this paper, I tackle the question: given n and k, what is the probability that the submonoid of the full transformation monoid Tn generated by k random transformations is synchronizing?
The question has some similarities with a similar question about the probability that the subgroup of Sn 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 Tn. I develop a very close connection between transformation monoids and graphs, from which we obtain a description of non-synchronizing monoids as endomorphism monoids of graphs satisfying some very strong conditions. However, counting such graphs, and dealing with the intersections of their endomorphism monoids, seems difficult.
Peter J. Cameron, Christian Krattenthaler and Thomas W. Müller, Decomposable functors and the exponential principle, II
We develop a new setting for the exponential principle in the context of multisort species, where indecomposable objects are generated intrinsically instead of being given in advance. Our approach uses the language of functors and natural transformations (composition operators), and we show that, somewhat surprisingly, a single axiom for the composition already suffices to guarantee validity of the exponential formula. We provide various illustrations of our theory, among which are applications to the enumeration of (semi-)magic squares and (higher-dimensional) cubes.
Peter J. Cameron, Christian Krattenthaler and Thomas W. Müller, A note on higher-dimensional magic matrices
We provide exact and asymptotic formulae for the number of unrestricted, respectively indecomposable, d-dimensional matrices where the sum of all matrix entries with one coordinate fixed equals 2.
Adam Bohn, Peter J. Cameron and Peter Müller, Galois groups of multivariate Tutte polynomials
The multivariate Tutte polynomial Z^M of a matroid M is a generalisation of the standard two-variable version, obtained by assigning a separate variable ve to each element e of the ground set. It encodes the full structure of M. Let v = {ve}, 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.
P. J. Cameron (editor), Problems from BCC22
These problems were mostly presented at the problem session at the 22nd British Combinatorial Conference at St Andrews, on 10 July 2009. I have removed two problems that were solved before or during the session; problems which have been subsequently solved are retained and given a number which should not change and can be used to refer to them. Solved problems will not appear in the published version but will remain in this document with some indication of the solution.
P. J. Cameron, Generating a group by a transversal
I answer a question of Vivek Jain by showing that, if H is a core-free subgroup of a finite group G, then there is a transversal for H in G which generates G. The result can be strengthened in a couple of ways: we may assume that the representative of the coset H is the identity; or we may relax the condition that H is core-free (but not too far). The crucial ingredient in the proof is a theorem of Whiston on the maximum size of an independent set in the symmetric group.
P. J. Cameron and V. Yildiz, Counting false values in truth tables of propositional formulae connected by implication
In this note we count the number of rows fn with the value "false" in the truth tables of all bracketed formulae with n variables connected by the binary connective of implication. We find a recurrence and an asymptotic formulae for fn. We also show that the ratio of false rows to the total number of rows converges to the constant (3-√3)/6.
P. J. Cameron and D. A. Preece, Three-factor decompositions of Un with the three generators in arithmetic progression
Irrespective of whether n is prime, prime power with exponent >1, or composite, the group Un of units of Zn can sometimes be obtained as
Un = (x) × (x+k) × (x+2k),where x,k in Zn. 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, and decompositions with more than three factors.
Robert F. Bailey and Peter J. Cameron, Base size, metric dimension and other invariants of groups and graphs
The base size of a permutation group, and the metric dimension of a graph, are both well-studied parameters which are closely related. We survey results on the relationship between the two, and with other, related parameters of groups, graphs, coherent configurations and association schemes. We also present some new results, including on the base sizes of wreath products in the product action, and on the metric dimension of Johnson and Kneser graphs.
Peter J. Cameron and Shamik Ghosh, The power graph of a finite group, submitted to Discrete Math.
The power graph of a group is the graph whose vertex set is the group, two elements being adjacent if one is a power of the other. We observe that non-isomorphic finite groups may have isomorphic power graphs, but that finite abelian groups with isomorphic power graphs must be isomorphic. We conjecture that two finite groups with isomorphic power graphs have the same number of elements of each order. We also show that the only finite group whose automorphism group is the same as that of its power graph is the Klein group of order 4.
Tatiana Gateva-Ivanova and Peter Cameron, Multipermutation solutions of the Yang–Baxter equation
Set-theoretic solutions of the Yang–Baxter equation form a meeting-ground of mathematical physics, algebra and combinatorics. Such a solution consists of a set X and a function r: X×X → X×X which satisfies the braid relation. We examine solutions here mainly from the point of view of finite permutation groups: a solution gives rise to a map from X to the symmetric group Sym(X) on X satisfying certain conditions.
Our results include many new constructions based on strong twisted union and wreath product, with an investigation of retracts and the multipermutation level and the solvable length of the groups defined by the solutions; and new results about decompositions and factorisations of the groups defined by invariant subsets of the solution.
R. A. Bailey and Peter J. Cameron, Combinatorics of optimal designs, Surveys in Combinatorics 2009 (ed. S. Huczynska, J. D. Mitchell and C. M. Roney-Dougal), London Math. Soc. Lecture Notes 365, Cambridge University Press 2009, pp. 19-73.
To a combinatorialist, a design is usually a 2-design (or balanced incomplete-block design). However, 2-designs do not necessarily exist in all cases where a statistician might wish to use one to design an experiment. As a result, statisticians need to consider structures much more general than the combinatorialist's designs, and to decide which one is "best" in a given situation. This leads to the theory of optimal design. There are several concepts of optimality, and no general consensus about which one to use in any particular situation.
For block designs with fixed block size k, all these optimality criteria are determined by a graph, the concurrence graph of the design, and more specifically, by the eigenvalues of the Laplacian matrix of the graph. It turns out that the optimality criteria most used by statisticians correspond to properties of this graph which are interesting in other contexts: D-optimality involves maximizing the number of spanning trees; A-optimality involves minimizing the sum of resistances between all pairs of terminals (when the graph is regarded as an electrical circuit, with each edge being a one-ohm resistor); and E-optimality involves maximizing the smallest eigenvalue of the Laplacian (the corresponding graphs are likely to have good expansion and random walk properties). If you are familiar with these properties, you may expect that related "nice" properties such as regularity and large girth (or even symmetry) may tend to hold; some of our examples may come as a surprise!
The aim of this paper is to point out that the optimal design point of view unifies various topics in graph theory and design theory, and suggests some interesting open problems to which combinatorialists of all kinds might turn their expertise. We describe in some detail both the statistical background and the mathematics of various topics such as Laplace eigenvalues of graphs.
Peter J. Cameron, Decompositions of complete multipartite graphs, Discrete Math. 309 (2009), 4185-4186; doi: 10.1016/j.disc.2008.10.021
This paper answers a recent question of Dobson and Marušič by partitioning the edge set of a complete multipartite graph into two parts, both of which are edge sets of arc-transitive graphs, one primitive and the other imprimitive. The first member of the infinite family is the one constructed by Dobson and Marušič.
Peter J. Cameron, Oligomorphic permutation groups, to appear in Perspectives in Mathematical Sciences, ed. N.S.N. Sastry, Mohan Delampady, B. Rajeev and T.S.S.R.K. Rao, Indian Statistical Institute.
A permutation group G (acting on a set Omega, usually infinite) is said to be oligomorphic if G has only finitely many orbits on Omegan (the set of n-tuples of elements of Omega). Such groups have traditionally been linked with model theory and combinatorial enumeration; more recently their group-theoretic properties have been studied, and links with graded algebras, Ramsey theory, topological dynamics, and other areas have emerged.
This paper is a short summary of the subject, concentrating on the enumerative and algebraic aspects but with an account of group-theoretic properties. The first section gives an introduction to permutation groups and to some of the more specific topics we require, and the second describes the links to model theory and enumeration. We give a spread of examples, describe results on the growth rate of the counting functions, discuss a graded algebra associated with an oligomorphic group, and finally discuss group-theoretic properties such as simplicity, the small index property, and "almost-freeness".
Peter J. Cameron, Daniel Johannsen, Thomas Prellberg and Pascal Schweitzer, Counting defective parking functions, Electronic J. Combinatorics 15(1) (2008), #R92 (15pp).
Suppose that n drivers each choose a preferred parking space in a linear car park with m spaces. Each driver goes to the chosen space and parks there if it is free, and otherwise takes the first available space with larger number (if any). If all drivers park successfully, the sequence of choices is called a parking function. In general, if k drivers fail to park, we have a defective parking function of defect k. Let cp(n,m,k) be the number of such functions.
In this paper, we establish a recurrence relation for the numbers cp(n,m,k), and express this as an equation for a three-variable generating function. We solve this equation using the kernel method, and extract the coefficients explicitly: it turns out that the cumulative totals are partial sums in Abel's binomial identity. Finally, we compute the asymptotics of cp(n,m,k). In particular, for the case m=n, if choices are made independently at random, the limiting distribution of the defect (the number of drivers who fail to park), scaled by the square root of n, is the Rayleigh distribution. On the other hand, in case m=omega(n), the probability that all spaces are occupied tends asymptotically to one.
Peter J. Cameron and Ross Applegate, Orbits on n-tuples, Communications in Algebra 37 (2009), 269-275; doi: 10.1080/00927870802243739
A transitive (infinite) permutation group which has m orbits on ordered pairs of distinct points has at least mn-1 orbits on ordered n-tuples. This is best possible, and groups attaining the bound can be characterised.
Peter J. Cameron and Priscila A. Kazanidis, Cores of symmetric graphs, J. Australian Math. Soc. 85 (2008), 145-154; doi: 10.1017/S1446788708000815
The core of a graph Γ is the smallest graph Δ which is homomorphically equivalent to Γ (that is, there exist homomorphisms in both directions). The core of Γ is unique up to isomorphism and is an induced subgraph of Γ.
We give a construction in some sense dual to the core. The hull of a graph Γ is a graph containing Γ as a spanning subgraph, admitting all the endomorphisms of Γ, and having as core a complete graph of the same order as the core of Γ. This construction is related to the notion of a synchronizing permutation group which arises in semigroup theory; we provide some more insight by characterizing these permutation groups in terms of graphs.
It is known that the core of a vertex-transitive graph is vertex-transitive. In some cases we can make stronger statements: for example, if Γ is a nonedge-transitive graph, we show that either the core of Γ is complete, or Γ is its own core.
Rank 3 graphs are nonedge-transitive. We examine some families of these to decide which of the two alternatives for the core actually holds. We will see that this question is very difficult, being equivalent in some cases to unsolved questions in finite geometry (for example, about spreads, ovoids, and partitions into ovoids in polar spaces).
Peter J. Cameron, A generalisation of t-designs, Discrete Math. 309 (2009), 4835-4842; doi: 10.1016/j.disc.2008.07.005
This paper defines a class of designs which generalise t-designs, resolvable designs, and orthogonal arrays. For the parameters t=2, k=3 and λ=1, the designs in the class consist of Steiner triple systems, Latin squares, and 1-factorisations of complete graphs. For other values of t and k, we obtain t-designs, Kirkman systems, large sets of Steiner triple systems, sets of mutually orthogonal Latin squares, and (with a further generalisation) resolvable 2-designs and indeed much more general partitions of designs, as well as orthogonal arrays over variable-length alphabets.
The Markov chain method of Jacobson and Matthews for choosing a random Latin square extends naturally to Steiner triple systems and 1-factorisations of complete graphs, and indeed to all designs in our class with t=2, k=3, and arbitrary λ, although little is known about its convergence or even its connectedness.
Peter J. Cameron and Sam Tarzi, Filters, topologies and groups from the random graph.
We investigate the filter generated by vertex neighbourhoods in the countable random graph R, and two related topologies, with emphasis on their automorphism groups. These include a number of highly transitive groups containing Aut(R).
Peter Cameron and Natalia Iyudu, Graphs of relations and Hilbert series, J. Symbolic Comput. 42 (2007), 1066-1078.
We discuss certain combinatorial and counting problems related to quadratic algebras. First we confirm the Anick conjecture on the minimal Hilbert series for algebras given by n generators and n(n-1)/2 relations for n≤7. Then we investigate the combinatorial structure of the coloured graph associated with the relations of an RIT algebra. Precise descriptions of graphs (maps) corresponding to algebras with maximal Hilbert series are given in certain cases. As a consequence it turns out, for example, that an RIT algebra may have a maximal Hilbert series only if the components of the graph associated with each colour are pairwise 2-isomorphic.
Robert F. Bailey and Peter J. Cameron, On the single-orbit conjecture for uncoverings-by-bases, J. Group Theory 11 (2008), 845-850; doi: 10.1515/JGT.2008.053
Let G be a permutation group acting on a finite set Omega. An uncovering-by-bases (or UBB) for B is a set U of bases for G such that any r-subsets of Omega is disjoint from at least one base in U, where r = [(d-1)/2], for d the minimum degree of G. The single-orbit conjecture asserts that for any finite permutation group G there exists a UBB for G contained in a single orbit of G on its irredundant bases. We prove a case of this conjecture, for when G is k-transitive and has a base of size k+1. Furthermore, in the restricted case when G is primitive and has a base of size 2, we show how to construct a UBB of minimum possible size.
Peter J. Cameron and Sam Tarzi, On the automorphism group of the m-coloured random graph.
Let Rm be the (unique) universal homogeneous m-edge-coloured countable complete graph (m≥2), and Gm its group of colour-preserving automorphisms. The group Gm was shown to be simple by John Truss. We examine the automorphism group of Gm, and show that it is the group of permutations of Rm which induce permutations on the colours, and hence an extension of Gm by the symmetric group of degree m. We show further that the extension splits if and only if m is odd, and in the case where m is even and not divisible by 8 we find the smallest supplement for Gm in its automorphism group.
Peter Cameron, Thomas Prellberg and Dudley Stark, Asymptotic enumeration of 2-covers and line graphs, Discrete Math., in press; doi: 10.1016/j.disc.2008.09.008
In this paper we find asymptotic enumerations for the number of line graphs on n labelled vertices and for different types of related combinatorial objects called 2-covers.
We find that the number of 2-covers, sn, and proper 2-covers, tn, on [n] both have asymptotic growth
B2n2-nexp(-½log(2n/log n))where B2n is the 2n-th Bell number, while the number of restricted 2-covers, un, restricted, proper 2-covers vn, and line graphs ln all have growth
B2n2-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.
P. J. Cameron, Root systems and optimal block designs, Michigan Math. J. 58 (2009), 181-194; doi: 10.1307/mmj/1242071687
Motivated by a question of C.-S. Cheng on optimal block designs, this paper describes the symmetric matrices with entries 0, +1 and -1, zero diagonal, least eigenvalue strictly greater than -2, and constant row sum. I also describe briefly the motivation for the question.
P. J. Cameron (editor), Problems from CGCS.
Most of these problems were presented at the conference on Combinatorics, Geometry and Computer Science, held at CIRM, Luminy, 2-4 May 2007. I have added one problem on a similar theme after the meeting.
The problems have been arranged so that those with similar themes occur together as far as possible.
P. J. Cameron, Permutation codes.
There are many analogies between subsets and permutations of a set, and in particular between sets of subsets and sets of permutations. The theories share many features, but there are also big differences. This paper is a survey of old and new results about sets (and groups) of permutations, concentrating on the analogies and on the relations to coding theory. Several open problems are described.
It is a pleasure to dedicate this paper to Michel Deza, who was a pioneer in the investigation of permutations from this point of view.
R. A. Bailey and P. J. Cameron, What is a design? How should we classify them? Designs, Codes, Crypt 44 (2007), 223-238; doi: 10.1007/s10623-007-9092-3
In 2001, the United Kingdom Engineering and Physical Sciences Research Council awarded the authors of this paper and Leonard Soicher a grant for "A Web-based resource for design theory". Planning how to put a catalogue of designs on the web forced us to think about the questions which are posed in the title of this paper.
P. J. Cameron and A. Rudvalis, A design and a geometry for the Fischer group Fi22, Designs, Codes, Crypt. 44 (2007), 11-14; doi: 10.1007/s10623-007-9041-1
The Fischer group Fi22 acts as a rank 3 group of automorphisms of a symmetric 2-(14080,1444,148) design. This design does not have a doubly transitive automorphism group, since there is a partial linear space with lines of size 4 defined combinatorially from the design and preserved by its automorphism group. We investigate this geometry and determine the structure of various subspaces of it.
C. Buchheim, P. J. Cameron and T. Wu, On the subgroup distance problem, Discrete Math. 309 (2009), 962-968; doi: 10.1016/j.disc.2008.01.036
We investigate the computational complexity of finding an element of a permutation group H contained in Sn with minimal distance to a given element pi in Sn, for different metrics on Sn. 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 lp distance, Lee's distance, Kendall's tau, and Ulam's distance. Moreover, we give an NP-hardness proof for the linfty distance using a different reduction idea. Finally, we settle the complexity of the corresponding fixed-parameter and maximization problems.
Peter J. Cameron and D. Lockett, Posets, homomorphisms and homogeneity, Discrete Math., in press; doi: 10.1016/j.disc.2009.04.027
Jarik Nešetřil suggested to the first author the investigation of notions of homogeneity for relational structures, where "isomorphism" is replaced by "homomorphism" in the definition. Here we look in detail at what happens for posets. For the strict order, all five generalisations of homogeneity coincide, and we give a characterisation of the countable structures that arise. For the non-strict order, there is an additional class. The "generic poset" plays an important role in the investigation.
Peter J. Cameron and Leonard H. Soicher, Block intersection polynomials, Bull. London Math. Soc. 39 (2007), 559-564; doi: 10.1112/blms/bdm034
We introduce the block intersection polynomial, which is constructed using certain information about a block design with respect to a subset S of its point-set, and then provides further information about the number of blocks intersecting S in exactly i points, for i = 0,...,|S|. We also discuss some applications of block intersection polynomials, including bounding the multiplicity of a block in a t-(v,k,λ) design and in a resolvable t-(v,k,λ) design.
P. J. Cameron and S. Tarzi, Limits of cubes, Topology and its Applications 155 (2008), 1454-1461.
The celebrated Urysohn space is the completion of a countable universal homogeneous metric space which can itself be built as a direct limit of finite metric spaces. It is our purpose in this paper to give another example of a space constructed in this way, where the finite spaces are scaled cubes. The resulting countable space provides a context for a direct limit of finite symmetric groups with strictly diagonal embeddings, acting naturally on a module which additively is the "Nim field" (the quadratic closure of the field of order 2). Its completion is familiar in another guise: it is the set of Lebesgue-measurable subsets of the unit interval modulo null sets. We describe the isometry groups of these spaces and some interesting subgroups, and give some generalisations and speculations.
P. J. Cameron, A. Montanaro, M. W. Newman, S. Severini and A. Winter, On the quantum chromatic number of a graph, Electronic Journal of Combinatorics 14(1) (2007), #R82 (15pp).
We investigate the notion of quantum chromatic number of a graph, which is the minimal number of colours necessary in a protocol in which two separated provers can convince an interrogator with certainty that they have a colouring of the graph.
After discussing this notion from first principles, we go on to establish relations with the clique number and orthogonal representations of the graph. We also prove several general facts about this graph parameter and find large separations between the clique number and the quantum chromatic number by looking at random graphs. Finally, we show that there can be no separation between classical and quantum chromatic number if the latter is 2, nor if it is 3 in a restricted quantum model; on the other hand we exhibit a graph on 18 vertices and 44 edges with chromatic number 5 and quantum chromatic number 4.
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.
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.
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.
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.
We show that the number of monochromatic solutions of the equation x1α1x2α2...xrαr=g in a 2-coloring of a finite group G, where α1,...,α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.
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.
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.
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.
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!
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 xi 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.
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.
A random preorder on n elements consists of linearly ordered equivalence classes called blocks. We investigate the block structure of a preorder chosen uniformly at random from all preorders on n elements as n tends to infinity.
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.
A graph is said to be reduced if no two vertices have the same set of neighbours. It is well known that for a given natural number r, there are finitely many reduced graphs of rank r. Let m(r) denote the number of vertices of the largest reduced graph of rank r. We present two constructions (the first due to Kotlov and Lovász in 1996) which show that for positive r,
m(r) ≥ 2(r+2)/2-1 if r is even,and we conjecture that the bounds are attained.
m(r) ≥ 5.2(r-3)/2-1 if r is odd,
It is known that a number of important graph-theoretic parameters are bounded by a function of the rank of a graph and the rank is bounded by a function of the number t of negative eigenvalues. We present deeper insight in this matter.
We also report on the determination of all reduced graphs with rank at most 7, and give information of the classification by rank and signature up to rank 7. This also gives (at least implicitly) an exact enumeration of all graphs with rank at most 7. We have also determined the largest reduced graphs of rank 8.
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.
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.
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 GX is transitive on X. Next we use this result to deduce a complete classification of these groups for k>2.
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.
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.
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 Qr for r=1,2, each having an inherent partition Fr (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 F1=U1 or F2=E2, and to the wreath product if F1=E1 and F2=U2, where Er and Ur are the relation of equality and the universal relation on Qr. We calculate the character table of the crested product, and show that if the two schemes Q1 and Q2 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.
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.
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.
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.
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=pn.
We introduce the concept of orbit-homogeneity of permutation groups: a group G is orbit t-homogeneous if two sets of cardinality t lie in the same orbit of G whenever their intersections with each G-orbit have the same cardinality. For transitive groups, this coincides with the usual notion of t-homogeneity. This concept is also compatible with the idea of partition transitivity introduced by Martin and Sagan.
We show that any group generated by orbit t-homogeneous subgroups is orbit t-homogeneous, and that the condition becomes stronger as t increases up to [n/2], where n is the degree. So any group G has a unique maximal orbit t-homogeneous subgroup Omegat(G), and Omegat(G) ≤ Omegat-1(G).
We also give some structural results for orbit t-homogeneous groups and a number of examples.
We establish and comment on a surprising relationship between the behaviour modulo a prime p of the number sn(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 sn(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.
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 Sn 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.
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 Xm=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.
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.
Let Sn be the symmetric group on the set X = {1,2,..., n}. A subset S of Sn is intersecting if for any two permutations g and h in S, g(x)=h(x) for some x in X (that is, g and h agree on x). M. Deza and P. Frankl proved that if S is intersecting then |S| <= (n-1)!. This bound is met by taking S to be a coset of a stabiliser of a point. We show that these are the only largest intersecting sets of permutations.
A set U is amorphous if every subset of U is finite or cofinite; an amorphous set is bounded if there is a natural number n such that every non-trivial partition of U has all but finitely many parts of size m, for some m≤n. Our main result asserts that, if U is bounded amorphous, then the symmetric group on U modulo the group of finitary permutations is isomorphic to a finite group, and that every finite group can occur in this situation. We also obtain some results about the structure of the finitary symmetric group on an amorphous set. Our results depend heavily on the classification of bounded amorphous sets by John Truss.
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.
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.
Julius Whiston showed that the size of an independent generating set in the symmetric group Sn 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 Sn for n>6.
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.
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".
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.
It is usually assumed that an infinite design is a design with infinitely many points. This encompasses a myriad of structures, some nice and others not. In this paper we consider examples of structures that we would not like to call designs, and investigate additional conditions that exclude such anomalous structures. In particular, we expect a design to be regular, the complement of a design to be a design, and a t-design to be an s design for all s less than t. These are all properties that can be taken for granted with finite designs, and for infinite Steiner systems. We present a new definition of an infinite t-design, and give examples of structures that satisfy this definition. We note that infinite designs considered in the literature to date satisfy our definition. We show that infinite design theory does not always mirror finite design theory; for example, there are designs with v > b.
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.
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 Q8 as the unique non-abelian group T such that a diagonal group with eight factors T is generously transitive.
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 v1, v2 depends only on whether or not v1 and v2 are adjacent in the graph.
The only strongly regular graphs that are known to be n-e.c. for large n are the Paley graphs. Recently D. G. Fon-Der-Flaass has found prolific constructions of strongly regular graphs using affine designs. He notes that some of these constructions were also studied by Wallis. By taking the affine designs to be Hadamard designs obtained from Paley tournaments, we use probabilistic methods to show that many non-isomorphic strongly regular n-e.c. graphs of order (q+1)2 exist whenever q is a prime power at least 16n222n and congruent to 3 mod 4.
Strongly regular graphs form an important class of graphs which lie somewhere between the highly structured and the apparently random. This chapter gives an introduction to these graphs with pointers to more detailed surveys of particular topics.
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.
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=22n and k=22n-1±2n-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).
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.
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.
This paper presents a tapas of results on fixed points and cycles in permutation groups, arising in such disparate areas as matrix group recognition, Brauer groups, Latin squares, and relational databases.
DVI or PostScript
The random graph, or Rado's graph (the unique countable homogeneous graph) has made an appearance in many parts of mathematics since its first occurrences in the early 1960s. In this paper I will discuss some old and new results on this remarkable structure.
DVI or PostScript
There is a natural bijection between representable matroids and linear codes over a given field, which is not as well known as it ought to be. An early result on this is Greene's theorem asserting that the weight enumerator of the code is a specialisation of the Tutte polynomial of the matroid. This connection also throws light on the minimal trellis for decoding a given code, and gives new results (and easier proofs of old results) on trellis complexity.
DVI or PostScript
With any permutation g of a set Omega is associated a partition of Omega into the cycles of g. What information do we get about a group G of permutations if we know either the set or the multiset of partitions of Omega, or of partitions of n (the cardinality of Omega), which arise as the cycle partitions of its elements? Some partial answers to these questions are given.
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.
In this note I prove an asymptotic structure theorem for groups with the property that any non-identity element fixes exactly k points. I also look briefly at the infinite analogue, and at a conjectured analogue for groups with prescribed sets of fixed-point numbers.
DVI or PostScript
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.
This paper is a survey of some combinatorial problems related to permutations and permutation groups. It is inspired by the work of Paul Erdős in two ways. One one hand, I present some partial extensions of the seminal work of Erdős and Turán on random permutations, to groups other than the symmetric group. On the other, many of the topics considered can be regarded as analogues for sets of permutations of results on set-systems (or hypergraphs) springing from the Erdős-Ko-Rado theorem.
I begin with the celebrated Orbit-Counting Lemma, and a generalisation which connect orbits of a group on n-tuples with the probability generating function for fixed points of its elements. Various results and problems on derangements (fixed-point-free elements) are also given. In the next section, I turn from fixed points to cycles. Observing that the cycle index is the probability generating function for cycle structure, we recover the earlier theorem, as well as a recent result of Parker. Next I survey some extremal results for sets or groups of permutations with prescribed distances (distance being defined in terms of fixed points). After a brief discussion of the semilattice of subpermutations (partial permutations), I conclude with a concept to replace that of "random permutation" in the infinite case: for countable sets, there is a unique such object (this is the analogue of the Erdős-Rényi theorem on the countable random graph).
AMS 05 A 05
Note: An update on the problems in this paper is available here.
We can use the compositional semantics of Hodges to show that any compositional semantics for logics of imperfect information must obey certain constraints on the number of semantically inequivalent formulas. As a corollary, there is no compositional semantics for the "independence-friendly" logic of Hintikka and Sandu (henceforth IF) in which the interpretation in a structure A of each 1-ary formula is a subset of the domain of A (Corollary 14 proves this and more). After a fashion, this rescues a claim of Hintikka and provides the proof which he lacked:
... there is no realistic hope of formulating compositional truth-conditions for [sentences of IF], even though I have not given a strict impossibility proof to that effect.One curious spinoff is that there is a structure of cardinality 6 on which the logic of Hintikka and Sandu gives nearly eight million inequivalent formulas in one free variable (which is more than the population of Finland).
AMS 03 B 60
These problems were presented at the Third International Conference on Discrete Metric Spaces, held at CIRM, Luminy, France, 15-18 September 1998. The names of the originators of a problem are given where these are known and different from the presenter of the problem at the conference.
AMS 52 C 99
DVI or PostScript
We examine a number of countable homogeneous relational structures with the aim of deciding which countable groups can act regularly on them. Since a group X acts regularly on a graph G if and only if G is a Cayley graph for X, we will extend the terminology and say that M is a Cayley object for X if X acts regularly on M. We consider, among other things, graphs, hypergraphs, metric spaces and total orders.
AMS 20 B 07
DVI or PostScript
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 Kn (partitions of the edge set into subsets each of which consists of disjoint edges covering all but one point) which admit 2-transitive groups.
AMS 05 B 30
DVI or PostScript
The existence problem for biplanes has proved to be intractable: only finitely many are known. However, it can be turned into an extremal problem, on which some progress can be made.
AMS 05 B 05
DVI or PostScript
This paper discusses investigations of sequences of natural numbers which count the orbits of an infinite permutation group on n-sets or n-tuples. It surveys known results on the growth rates, cycle index techniques, and an interpretation as the Hilbert series of a graded algebra, with a possible application to the question of smoothness of growth. I suggest that these orbit-counting sequences are sufficiently special to be interesting but sufficiently common to support a general theory.
AMS 20 B 07, 05 A 15
DVI or PostScript
An independence algebra is an algebra A in which the subalgebras satisfy the exchange axiom, and any map from a basis of A into A extends to an endomorphism. Independence algebras fall into two classes; the first are specified by a set X, a group G, and a G-space C. The second are much more restricted; we show that the subalgebra lattice is a projective or affine geometry, and give a complete classification of the finite algebras.
AMS 08 A 05
DVI or PostScript
Two tournaments T1 and T2 on the same vertex set X are said to be switching equivalent if X has a subset Y such that T2 arises from T1 by switching all arcs between Y and its complement in X. The main result of this paper is a characterisation of the abstract finite groups which are full automorphism groups of switching classes of tournaments: they are those whose Sylow 2-subgroups are cyclic or dihedral. Moreover, if G is such a group, then there is a switching class C, with Aut(C) isomorphic to G, such that every subgroup of G of odd order is the full automorphism group of some tournament in C.
Unlike previous results of this type, we do not give an explicit construction, but only an existence proof. The proof follows as a special case of a result on the full automorphism group of random G-invariant digraphs selected from a certain class of probability distributions.
We also show that a permutation group G, acting on a set X, is contained in the automorphism group of some switching class of tournaments with vertex set X if and only if the Sylow 2-subgroups of G are cyclic or dihedral and act semiregularly on X. Applying this result to individual permutations leads to an enumeration of switching classes, of switching classes admitting odd permutations, and of tournaments in a switching class.
We conclude by remarking that both the class of switching classes of finite tournaments, and the class of "local orders" (that is, tournaments switching-equivalent to linear orders), give rise to countably infinite structures with interesting autmorphism groups (by a theorem of Fraïssé).
AMS 20B25; also 05C20, 05C25, 05C30, 05E99
DVI or PostScript
This paper begins with the observation that half of all graphs containing no induced path of length 3 are disconnected. We generalize this in several directions. First, we give necessary and sufficient conditions (in terms of generating functions) for the probability of connectedness in a suitable class of graphs to tend to a limit strictly between zero and one. Next we give a general framework in which this and related questions can be posed, involving operations on classes of finite structures. Finally, we discuss briefly an algebra associated with such a class of structures, and give a conjecture about its structure.
AMS 05 A 16
Our main topic is the number of subsets of [1,n] which are maximal with respect to some condition such as being sum-free, having no number dividing another, etc. We also investigate some related questions.
AMS 11 P 99
This paper describes some classes of infinite distance-transitive graphs. It has no pretensions to give a complete list, but concentrates on graphs which have no finite analogues.
AMS 05 C 25
With any permutation group G on an infinite set Omega is associated a graded algebra AG (the algebra of G-invariants in the reduced incidence algebra of finite subsets of Omega). The dimension of the n-th homogeneous component of AG is equal to the number of orbits of G on n-subsets of Omega. If it happens that G is the automorphism group of a homogeneous structure M, then this is the number of unlabelled n-element substructures of M. Many combinatorial enumeration problems fit into this framework.
I conjectured 20 years ago that, if G has no finite orbits on Omega, then AG is an integral domain (and even has the stronger property that a specific quotient is an integral domain). I shall say that G is entire if AG is an integral domain, and strongly entire if the stronger property holds. These properties have (rather subtle) consequences for the enumeration problems. The conjecture is still open; but in this paper I prove that, if G is transitive on Omega and the point stabiliser H is (strongly) entire, then G is (strongly) entire.
AMS 20 B 07
We show that, if S1 is a strongly complete sum-free set of positive integers and if S0 is a finite sum-free set, then with positive probability a random sum-free set U contains S0 and is contained in S0 union S1. As a corollary we show that with positive probability, 2 is the only even element of a random sum-free set.
AMS 11 P 99
Given a class of structures with a notion of connectedness (satisfying some reasonable assumptions), we consider the limit (as n tends to infinity) of the probability that a random (labelled or unlabelled) n-element structure in the class is connected. The paper consists of three parts: a specific example, N-free posets, where the limiting probability of connectedness is the golden ratio; an investigation of the relation between this question and the growth rate of the number of structures in the class; and a generalisation of the problem to other combinatorial constructions motivated in part by the group-theoretic constructions of direct and wreath product.
AMS 05 A 16
Associated with any oligomorphic permutation group G, there is a graded algebra AG 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.
AMS 03 C 35
When m is odd, spreads in an orthogonal vector space of type Omega+(2m+2,2) are related to binary Kerdock codes and extremal line-sets in R2m+1 with prescribed angles. Spreads in a 2m-dimensional binary symplectic vector space are related to Kerdock codes over Z4 and extremal line-sets in C2m 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 Z4-Kerdock code to its binary image. These geometric considerations lead to the construction of d(m)-1 inequivalent Z4-linear Kerdock codes and d(m)-1 inequivalent Z4-linear Preparata codes of length 2m for any odd m, where d(m) denotes the number of divisors of m.
AMS 94 B 27
A permutation group is cofinitary if any non-identity element fixes only finitely many points. In this article, I discuss two aspects of the theory of cofinitary permutation groups, one topological, the other combinatorial. Several open problems are included.
AMS 20 B 07
Studying the geometry of a group G leads us to questions about its maximal subgroups and primitive permutation representations (the G-invariant relations and similar structures, the base size, recognition problems, and so on). Taking the point of view that finite projective geometry is the geometry of the groups PGL(n,q), Aschbacher's theorem gives us eight natural families of geometric objects, with greater or smaller degrees of familiarity. This paper presents some speculations on how the subject could develop from this point of view.
AMS 51 E 20
These notes are, in a sense, an elaboration on the comments on pages 232-234 of the book on Distance-transitive Graphs by Brouwer, Cohen and Neumaier. Apart from these brief comments, the book is exclusively concerned with finite graphs. Many of these finite graphs are geometrically defined, and involve a finite field and sometimes a finite dimension. By allowing one or both of these parameters to be infinite, we often obtain infinite distance-transitive graphs. However, entirely new phenomena occur in the infinite case, which have no finite analogues.
In these notes, I discuss infinite graphs (and other structures) with a large amount of symmetry. The discussion concentrates on the purely infinite phenomena, though we glance briefly at the infinite versions of finite graphs. The celebrated "random graph" is typical of the new situation; the first section summarises some of the remarkable properties of this graph. Following this, we survey some basic material from permutation groups and model theory. Then we discuss various constructions and characterisations of infinite highly symmetric graphs, and connections with several topics in finite combinatorics, including random graphs, enumeration, and graph reconstruction.
AMS 05 C 25
This chapter concerns some connections between graph theory and first-order logic. After an introduction to first-order logic and a discussion of which graph properties are first-order, we consider various logical concepts such as aleph_0-categoricity and homogeneity for graphs, and present a couple of theorems about finite graphs requiring logical techniques in their proofs. The chapter concludes with a discussion of a recent construction method due to Hrushovski related to sparse random graphs.
AMS 05 C 99
In this chapter, the connections between a graph and its automorphism group are described. The main themes are that most graphs have very little symmetry; abstract automorphism groups can be prescribed independently of most graph-theoretic properties; vertex-transitivity, however, entails various structural properties; and still higher degrees of symmetry can be expected to lead to a complete classification.
AMS 05 C 25
Erdős and Rényi showed the paradoxical result that there is a unique (and highly symmetric) countably infinite random graph. This graph, and its automorphism group, form the subject of the present survey.
AMS 05 C 80
The main theme of this paper is that counting orbits of an infinite permutation group on finite subsets or tuples is very closely related to combinatorial enumeration. This point of view ties together various disparate "stories", concerning two-graphs, circular orders, Stirling numbers, series-reduced trees, etc.
AMS 05 A 99
There is a natural topology on the symmetric group on an infinite set Omega. If Omega is countable, the topology is derived from a metric, and the group is complete. This paper gives an account of this topology, including translations of topological concepts for permutation groups, the use of Baire category and Haar measure, and some results about cofinitary permutation groups which are motivated by the combinatorics of finite symmetric groups.
AMS 20 B 07
A finite permutation group is cycle-closed if it contains all the cycles of all of its elements. It is shown by elementary means that the cycle-closed groups are precisely the direct products of symmetric groups and cyclic groups of prime order. Moreover, from any group, a cycle-closed group is reached in at most three steps, a step consisting of adding all cycles of all group elements. For infinite groups, there are several possible generalisations. Some analogues of the finite result are proved.
AMS 20 B 07
A permutation group is cofinitary if any non-identity element fixes only finitely many points. This paper presents a survey of such groups. The paper has four parts. Sections 1-5 develop some basic theory, concerning groups with finite orbits, topology, maximality, and normal subgroups. Sections 6-10 give a variety of constructions, both direct and from geometry, combinatorial group theory, trees, and homogeneous relational structures. Sections 11-15 present some generalisations of sharply k-transitive groups, including an orbit-counting result with a character-theoretic flavour. The final section treats some miscellaneous topics. Several open problems are mentioned.
AMS 20 B 07
This note is inspired by the paper Some Canonical Sequences of Integers by Bernstein and Sloane. The main observation is that seven of the operators defined in that paper have natural interpretations in terms of counting orbits of groups, providing a pattern which is completed by five further operators. Some of their eigen-sequences also have group-theoretic meaning.
AMS 20 B 07
In this paper, we give two equivalent conditions for the irredundant bases of a permutation group to be the bases of a matroid. (These are deduced from a more general result on families of sets.) If they hold, then the group acts geometrically on the matroid, in the sense that the fixed points of any element form a flat. Some partial results towards a classification of such permutation groups are given. Further, if G acts geometrically on a perfect matroid design, there is a formula for the number of G-orbits on bases in terms of the cardinalities of flats and the numbers of G-orbits on tuples. This reduces, in a particular case, to the inversion formula for Stirling numbers.
AMS 20 B 05
Peter J. Cameron
27 July 2009