Recent preprints by Marston Conder


Summary


Paper information


Title: Semi-automated theorem proving: the impact of computers on research in pure mathematics
Author(s): Marston Conder
Status: Keynote address, First Asian Technology Conference in Mathematics, Singapore, December 1995
Length: 8 pages
Math Review Classification(s): 00A30, 01-08
Availability:
Postscript file, PDF file
Abstract:
There is no doubt that the use of computers in recent years has revolutionised many branches of science, not the least of these being mathematics. Even in pure mathematics, where often quite subtle and sophisticated arguments are required for the solution of problems, computers have become an invaluable, almost indispensible tool.
In this paper I will describe in more detail some aspects of the impact of computing on research in pure mathematics, and in particular on the use of specialist software to solve mathematical problems.
I will briefly discuss computer-based proofs with reference to two famous examples: the 4-colour theorem, and the non-existence of a projective plane of order 10, and will also mention a few of the major developments within mathematics that have resulted from the influence of computing. Finally I will outline some of the ways in which I have used computer software in my own research, with the aim of illustrating the potential of experimental approaches to questions in pure mathematics.


Title: Inner reflectors and non-orientable regular maps
Author(s): Marston Conder and Steve Wilson
Status: accepted for publication in a special issue of Discrete Mathematics
Length: 8 pages
Math Review Classification(s): 05C25, 57M15
Availability:
Postscript file, PDF file
Abstract:
Regular maps on non-orientable surfaces are considered with particular reference to the properties of inner reflectors, corresponding to symmetries of the 2-fold smooth orientable covering which project onto local reflections of the map itself. An example is given where no inner reflector is induced by an involution, and the existence of such involutions is related to questions of symmetry of coset diagrams for the symmetry group of the map.


Title: Explicit definition of the binary reflected Gray codes
Author(s): Marston Conder
Status: accepted for publication in Discrete Mathematics
Length: 6 pages
Math Review Classification(s): 94B25, 05A10
Availability:
Postscript file, PDF file
Abstract:
It is shown that for 1<=j<=n and 1<=k<=2^n, the jth letter of the kth word of the binary reflected Gray code of length n is equal to the parity of the binomial coefficient {2^n - 2^(n-j) - 1} C [2^n - 2^(n-j-1) - k/2] modulo 2. Also it is shown how this observation and the usual iterative definition of the binary reflected Gray codes are revealed in a modified version of Sierpinski's gasket (Pascal's triangle modulo 2).


Title: Embedding digraphs on orientable surfaces
Author(s): Paul Bonnington, Marston Conder, Patricia McKenna and Margaret Morton
Status: accepted for publication in Journal of Combinatorial Theory Series B
Length: 16 pages
Math Review Classification(s): 05C10, 57M15
Availability: Email one of the authors? Electronic copy not yet on-line
Abstract (abbreviated):
We consider a notion of embedding digraphs on orientable surfaces, applicable to digraphs in which the in-degree equals the out-degree at each vertex (Eulerian digraphs). A foundation is laid for the study of all Eulerian digraph embeddings. Results are proved which are analogous to those fundamental to the theory of undirected graph embeddings, such as Duke's theorem, and an infinite family of digraphs is given to demonstrate that the genus range for an embeddable digraph can be any non-negative integer. We show that it is possible to have genus range equal to 1, with arbitrarily large (minimum) genus, unlike in the undirected case. Also the difference between the minumum genera of a digraph and its underlying (undirected) graph is considered, along with the difference between the maximum genera. We say that a digraph is upper-embeddable if it can be embedded with just 2 or 3 regions (faces), and prove that every regular tournament is upper-embeddable.


Title: Applications and adaptations of the low index subgroups procedure
Author(s): Marston Conder and Peter Dobcsanyi
Status: accepted for publication in Mathematics of Computation
Length: 21 pages
Math Review Classification(s): 20F05, 20-04
Availability:
Postscript file, PDF file
Abstract:
The low-index subgroups procedure is an algorithm for finding all subgroups of up to a given index in a finitely-presented group $G$, and hence to determine all transitive permutation representations of $G$ of small degree. A number of significant applications of this algorithm are discussed, in particular to the construction of graphs and surfaces with large automorphism groups. Further, three useful adaptations of the procedure are described, along with parallelisation of the algorithm. In particular, one adaptation finds all {\it complements} of a given subgroup of finite index, and another finds all {\it normal} subgroups of small index in the group $G$. Significant recent applications of these are also described in some detail.


Title: Normal subgroups of low index in the modular group and other Hecke groups
Author(s): Marston Conder and Peter Dobcsanyi
Status: accepted for publication in "Combinatorial Group Theory, Number Theory and Discrete Groups" (ed. B. Fine, A. Gaglione & D. Spellman), Contemporary Mathematics series, American Mathematical Society
Length: 23 pages
Math Review Classification(s): 20F05
Availability:
Postscript file, PDF file
Abstract:
An account is given of the determination of all normal subgroups of index up to 1500 in the modular group PSL(2,Z) \cong C2*C3, and all normal subgroups of index up to 500 in the Hecke groups Hq = C2*Cq for 4 <= q <= 12, using an adaptation of the low index subgroups algorithm.


Title: Determination of all regular maps of small genus
Author(s): Marston Conder and Peter Dobcsanyi
Status: accepted for publication in Journal of Combinatorial Theory Series B
Length: 20 pages
Math Review Classification(s): 05C25, 57M15
Availability:
Postscript file , PDF file
Abstract:
Complete lists are given of all reflexible orientable regular maps of genus $2$ to $15$, all non-orientable regular maps of genus $4$ to $30$, and all (orientable) rotary but chiral (irreflexible) maps of genus $2$ to $15$ inclusive. On each list the maps are classified according to genus and type (viz. $\{p,q\}$ where every face is incident with $p$ edges and every vertex is incident with $q$ edges). The complete lists were determined with the help of a parallel program which finds all normal subgroups of low index in a finitely-presented group.


Title: Trivalent symmetric graphs on up to 768 vertices
Author(s): Marston Conder and Peter Dobcsanyi
Status: accepted for publication in J. Combinatorial Mathematics & Combinatorial Computing
Length: 24 pages
Math Review Classification(s): 05C25, 20B25, 20F05
Availability:
Postscript file, PDF file
Abstract:
A complete list is given of all finite trivalent arc-transitive connected graphs on up to 768 vertices, completing and extending the Foster census. Several previously undiscovered graphs appear, including one on 448 vertices which is the smallest trivalent arc-transitive graph having no automorphism of order 2 which reverses an arc. The graphs on the list are classified according to type (as described by Djokovic and Miller in terms of group amalgams), and were produced with the help of a parallel program which finds all normal subgroups of low index in a finitely-presented group. Further properties of each graph are also given: its girth, diameter, Hamiltonicity, and whether or not it is bipartite.


Title: A tetravalent half-arc-transitive graph with nonabelian vertex stabilizer
Author(s): Marston Conder and Dragan Marusic
Status: accepted for publication in Journal of Combinatorial Theory, Series B
Length: 12 pages
Math Review Classification(s): 05C, 20B
Availability:
Postscript file, PDF file
Abstract:
A construction is given of a 4-valent half-arc-transitive graph with vertex stabilizer isomorphic to the dihedral group D_8. The graph has 10752 vertices and is the first known example of a 4-valent half-arc-transitive graph with nonabelian vertex stabilizer.


Title: On extendability of group actions on compact Riemann surfaces
Author(s): Emilio Bujalance, Javier Cirre and Marston Conder
Status: accepted for publication in Transactions of the American Mathematical Society
Length: 29 pages
Math Review Classification(s): 14H, 20F, 30F
Availability:
Postscript file, PDF file
Abstract:
The question of whether a given group $G$ which acts faithfully on a compact Riemann surface $X$ of genus $g\ge 2$ is the full group of automorphisms of $X$ (or some other such surface of the same genus) is considered. Conditions are derived for the extendability of the action of the group $G$ in terms of a concrete partial presentation for $G$ associated with the relevant branching data, using Singerman's list of signatures of Fuchsian groups which are not finitely maximal. By way of illustration, the results are applied to the special case where $G$ is a non-cyclic abelian group.


Title: Two-arc closed subsets of graphs
Author(s): Marston Conder and Cheryl Praeger
Status: accepted for publication in Journal of Graph Theory
Length: 19 pages
Math Review Classification(s): 05C, 20B
Availability:
Postscript file , PDF file
Abstract:
A subset of vertices of a graph is said to be 2-arc closed if it contains every vertex that is adjacent to at least two vertices in the subset. In this paper, 2-arc closed subsets generated by pairs of vertices at distance at most 2 are studied. Several questions are posed about the structure of such subsets and the relationships between two such subsets, and examples are given from the class of partition graphs.


Title: Hurwitz groups with given centre
Author(s): Marston Conder
Status: accepted for publication in Bull. London Math. Society
Length: 6 pages
Math Review Classification(s): 20F, 57M
Availability:
Postscript file, dvi file, PDF file
Abstract:
A Hurwitz group is any non-trivial finite group which can be (2,3,7)-generated, that is, generated by elements $x$ and $y$ satisfying the relations $x^2 = y^3 = (xy)^7 = 1$. In this short paper a complete answer is given to a 1965 question by John Leech, showing that the centre of a Hurwitz group can be any given finite abelian group. The proof is based on a recent theorem of Lucchini, Tamburini and Wilson which states that the special linear group SL$_n(q)$ is a Hurwitz group for every integer $n \ge 287$ and every prime-power $q$.


Title: Group actions on graph, maps and surfaces with maximum symmetry
Author(s): Marston Conder
Status: invited survey article, published in the Proceedings of the Groups St Andrews conference in Oxford (August 2001)
Length: 29 pages
Math Review Classification(s): 05C, 20F, 57M
Availability:
Postscript file, dvi file, PDF file
Abstract:
This is a summary of a short course of lectures given at the Groups St Andrews conference in Oxford, August 2001, on the significant role of combinatorial group theory in the study of objects possessing a high degree of symmetry. Topics include group actions on closed surfaces, regular maps, and finite $s$-arc-transitive graphs for large values of $s$. A brief description of the use of Schreier coset graphs and computational methods for handling finitely-presented groups and their images is also given.


Title: Bounds for the number of automorphisms of a compact non-orientable surface
Author(s): Marston Conder, Colin Maclachlan, Sanja Todorovic Vasiljevic and Steve Wilson
Status: accepted for publication in Journal of the London Mathematical Society
Length: 22 pages
Math Review Classification(s): 20F, 57M
Availability:
Postscript file, dvi file, PDF file
Abstract:
In this paper it is shown that for every positive integer $p> 2$, there exists a compact non-orientable surface of genus $p$ with at least $4p$ automorphisms if $p$ is odd, or at least $8(p-2)$ automorphisms if $p$ is even, with improvements on $4p$ for $p \not\equiv 3$ mod 12. Further, these bounds are shown to be sharp (in that no larger group of automorphisms exists with genus $p$) for infinitely many values of $p$ in each congruence class modulo 12, with the possible (but unlikely) exception of 3 mod 12.


Title: The Ljubljana graph
Author(s): Marston Conder, Aleksander Malnic, Dragan Marusic, Tomaz Pisanski and Primoz Potocnik
Status: accepted for publication (as "The edge- but not vertex-transitive cubic graph on 112 vertices") for Journal of Graph Theory
Length: 15 pages
Math Review Classification(s): 05C, 20B
Availability:
Postscript file, PDF file
Abstract:
A detailed description is given of a recently-discovered edge- but not vertex-transitive trivalent graph on 112 vertices, which turns out to be the third smallest example of such a semisymmetric cubic graph. This graph is called the Ljubljana graph by the authors, although it is believed that its existence may have been known by R.M. Foster. With the help of some advanced theory of covering graphs, various properties of this graph are analysed, including a connection with the Heawood graph which can be described using ideals over polynomial rings.


Title: Constructive recognition of PSL(2,q)
Author(s): Marston Conder, Charles Leedham-Green and Eamonn O'Brien
Status: accepted for publication in the Transactions of the American Mathematical Society
Length: 19 pages
Math Review Classification(s): 20C
Availability:
Postscript file, dvi file, PDF file
Abstract:
Existing black box and other algorithms for explicitly recognising groups of Lie type over GF(q) have asymptotic running times which are polynomial in q, whereas the input size involves only log q. This has represented a serious obstruction to the efficient recognition of such groups.
Recently, Brooksbank and Kantor devised new explicit recognition algorithms for classical groups; these run in time that is polynomial in the size of the input, given an oracle that recognises PSL(2,q) explicitly.
The present paper, in conjunction with an earlier paper by the first two authors, provides such an oracle. The earlier paper produced an algorithm for explicitly recognising SL(2,q) in its natural representation in polynomial time, given a discrete logarithm oracle for GF(q). The algorithm presented here takes as input a generating set for a subgroup G of GL(d,F) that is isomorphic modulo scalars to PSL(2,q), where F is a finite field of the same characteristic as GF(q); it returns the natural representation of G modulo scalars. Since a faithful projective representation of PSL(2,q) in cross characteristic, or a faithful permutation representation of this group, is necessarily of size that is polynomial in q rather than in log q, elementary algorithms will recognise PSL(2,q) explicitly in polynomial time in these cases.
Given a discrete logarithm oracle for GF(q), our algorithm thus provides the required polynomial time oracle for recognising PSL(2,q) explicitly in the remaining case, namely for representations in the natural characteristic.
This leads to a partial solution of a question posed by Babai and Shalev: if G is a matrix group in characteristic p, determine in polynomial time whether or not O_p(G) is trivial.


Title: Regular t-balanced Cayley maps
Author(s): Marston Conder, Robert Jajcay and Tom Tucker
Status: accepted for publication in Journal of Combinatorial Theory, Series B
Length: 24 pages
Math Review Classification(s): 05C, 57M
Availability:
Postscript file, dvi file, PDF file
Abstract:
The concept of a t-balanced Cayley map is a natural generalization of the previously studied notions of balanced and anti-balanced Cayley maps (the terms coined by Siran and Skoviera (1992)). We develop a general theory of t-balanced Cayley maps based on the use of skew-morphisms of groups (Jajcay and Siran (2002)), and apply our results to the specific case of regular Cayley maps of abelian groups.


Title: Regular Cayley maps for finite abelian groups
Author(s): Marston Conder, Robert Jajcay and Tom Tucker
Status: accepted for publication in Journal of Algebraic Combinatorics
Length: 32 pages
Math Review Classification(s): 05C, 57M
Availability:
Postscript file, dvi file, PDF file
Abstract:
A regular Cayley map for a group A is an orientable map whose orientation-preserving automorphism group acts regularly on the directed edge set and has a subgroup isomorphic to A that acts regularly on the vertex set. This paper studies regular Cayley maps for finite abelian groups.


Title: Derived subgroups of products of an abelian and a cyclic subgroup
Author(s): Marston Conder and Marty Isaacs
Status: accepted for publication in the Journal of the London Mathematical Society
Length: 18 pages
Math Review Classification(s): 20D40, 20E34
Availability:
Postscript file, dvi file, PDF file
Abstract:
Let G be a finite group and suppose that G = AB, where A and B are abelian subgroups. By a Theorem of N.Ito, the derived subgroup G' is known to be abelian. If either of the subgroups A or B is cyclic, then more can be said. In this paper it is shown, for example, that G'/(G' \cap A) is isomorphic to a subgroup of B in this case.


Title: Small volume compact hyperbolic 4-manifolds
Author(s): Marston Conder and Colin Maclachlan
Status: accepted for publication in the Proceedings of the American Mathematical Society
Length: 12 pages
Math Review Classification(s): 57M50, 20F55 (primary), 51M20, 20B40 (secondary)
Availability:
Postscript file, dvi file, PDF file
Abstract:
We prove the existence of a compact non-orientable hyperbolic 4-manifold of volume $32\pi^{2}/3$ and a compact orientable hyperbolic 4-manifold of volume $64\pi^{2}/3$, obtainable from torsion-free subgroups of small index in the Coxeter group [5,3,3,3]. At the time of writing these are the smallest volumes of any known compact hyperbolic 4-manifolds.


Title: A counterexample to Fishburn's conjecture
Author(s): Marston Conder and Arkadii Slinko
Status: accepted for publication in Journal of Mathematical Psychology
Length: 15 pages
Math Review Classification(s): 60A05 (primary), 06A99 (secondary)
Availability:
Postscript file, PDF file, dvi file
Abstract:
Kraft, Pratt and Seidenberg (1959) provided an infinite set of axioms which, when taken together with de Finetti's axiom, gives a necessary and sufficient set of "cancellation" conditions for representability of an ordering relation on subsets of a set by an order-preserving probability measure. Fishburn (1996) defined f(n) to be the smallest positive integer k such that every comparative probability ordering on an n-element set which satisfies the cancellation conditions C4,...,Ck is representable. By the work of Kraft, Pratt and Seidenberg (1959) and Fishburn (1996, 1997), it is known that n-1 <= f(n) <= n+1 for all n >= 5. Also Fishburn proved that f(5) = 4, and conjectured that f(n) = n-1 for all n >= 5. In this paper we confirm that f(6) = 5, but give counter-examples to Fishburn's conjecture for n = 7, showing that f(7) >= 7. We summarise, correct and extend many of the known results on this topic, including the notion of "almost representability", and offer an amended version of Fishburn's conjecture.


Title: A census of semisymmetric cubic graphs on up to 768 vertices
Author(s): Marston Conder, Aleksander Malnic, Dragan Marusic and Primoz Potocnik
Status: accepted for publication in Journal of Algebraic Combinatorics
Length: 45 pages
Math Review Classification(s): 05C25, 20B25, 20F05
Availability:
Postscript file, dvi file, PDF file
Abstract:
A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs.
For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers.
A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having $K_{1,3}$ as a normal quotient is investigated in detail.


Title: Rankings of multisets and discrete cones
Author(s): Marston Conder, Simon Marshall and Arkadii Slinko
Status: accepted for publication in 'Order'
Length: 25 pages
Math Review Classification(s): 60A05 (primary), 06A99 (secondary)
Availability:
Postscript file, dvi file, PDF file
Abstract:
We study additive representability of orders on multisets (of size k drawn from a set of size n) which satisfy the condition of Independence of Equal Submultisets (IES) introduced by Sertel and Slinko (2002). Here we take a geometric view of those orders, and relate them to certain combinatorial objects which we call discrete cones. Following Fishburn (1996) and Conder & Slinko (2003), we define functions f(n,k) and g(n,k) which measure the maximal possible deviation of an arbitrary order satisfying the IES and an arbitrary almost representable order satisfying the IES, respectively, from a representable order. We prove that g(n,k) = n-1 whenever n >= 3 and (n,k) is not (5,2). In the exceptional case, g(5,2) = 3. We also prove that g(n,k) <= f(n,k) <= n and establish that for small n and k the functions f(n,k) and g(n,k) coincide.


Title: Highly transitive imprimitivities
Author(s): Marston Conder and Vaughan Jones
Status: accepted for publication in Journal of Algebra
Length: 14 pages
Math Review Classification(s): 20B10 (primary), 46L37 (secondary)
Availability:
Postscript file, dvi file, PDF file
Abstract:
Some new observations are made about imprimitive permutation groups associated with subfactors of von Neuman algebras. Of particular interest are examples of a group $G$ containing two maximal subgroups $H$ and $K$ such that $G \ne HK$, and such that the action of $G$ on the space of cosets of $H \cap K$ has small rank (few suborbits). The rank 6 case turns out to correspond to the action of the collineation group on flags of a Desarguesian projective plane, and a special case of interest for rank 7 corresponds to the action of a 4-transitive group on ordered pairs of distinct points. Some other new (and unexpected) fundamental properties of groups are described along the way.


Title: Minimal covers for maximal antichains of interval orders
Author(s): Alain Vandal, Marston Conder and Robert Gentleman
Status: accepted for publication in Ars Combinatoria
Length: 33 pages
Math Review Classification(s): 06A06 (primary), 91C05 (secondary)
Availability:
PDF file
Abstract:
We address the problem of determining all sets which form minimal covers of maximal cliques for interval graphs. We produce an algorithm enumerating all minimal covers using the inclusion-minimal elements of the interval order, as well as an independence Metropolis sampler. We characterize maximal removable sets, which are the complements of minimal covers, and produce a distinct algorithm to enumerate them. We use this last characterization to provide bounds on the maximum number of minimal covers for an interval order with a given number of maximal cliques, and present some simulation results on the number of minimal covers in different settings.


Title: Efficient presentations for the Mathieu simple group M_{22} and its cover
Author(s): Marston Conder, George Havas and Colin Ramsay
Status: published in proceedings of Conference on Finite Geometries, Groups and Computation (Pingree Park, Colorado, September 2004)
Length: 9 pages
Math Review Classification(s): 20-04, 20D05, 20D06, 20D08, 20F05
Availability:
PDF file, dvi file
Abstract:
Questions about the efficiency of finite simple groups and their covering groups have been the subject of much research. We provide new efficient presentations for the Mathieu simple group M_{22} and its cover, including the shortest known efficient presentation for M_{22} and a somewhat longer presentation which is very suitable for computation.


Title: Maximal symmetry groups of hyperbolic 3-manifolds
Author(s): Marston Conder, Gaven Martin and Anna Torstensson
Status: accepted for publication in New Zealand Journal of Mathematics
Length: 26 pages
Math Review Classification(s): 20B25, 57M60
Availability:
PDF file, dvi file
Abstract:
Every finite group acts as the full isometry group of some compact hyperbolic 3-manifold. In this paper we study those finite groups which act maximally, that is when the ratio |Iso^+(M)|/vol(M) is maximal among all such manifolds. In two dimensions maximal symmetry groups are called Hurwitz groups, and arise as quotients of the (2,3,7)-triangle group. Here we study quotients of the minimal co-volume lattice \Gamma of hyperbolic isometries in three dimensions, and its orientation-preserving subgroup \Gamma^+, and we establish results analogous to those obtained for Hurwitz groups. In particular, we show that for every prime p there is some q = p^k such that either PSL(2,q) or PGL(2,q) is quotient of \Gamma^+, and that for all but finitely many n, the alternating group A_n and the symmetric group S_n are quotients of \Gamma and also quotients of \Gamma^+, by torsion-free normal subgroups. We also describe all torsion-free subgroups of index up to 120 in \Gamma^+ (and index up to 240 in \Gamma), and explain how other infinite families of quotients of \Gamma and \Gamma^+ can be constructed.


Title: Symmetric cubic graphs of small girth
Author(s): Marston Conder and Roman Nedela
Status: accepted for publication in Journal of Combinatorial Theory, Series B
Length: 14 pages
Math Review Classification(s): 05C25, 20B25
Availability:
PDF file, dvi file
Abstract:
A graph \Gamma is called symmetric if its automorphism group acts transitively on the arcs of \Gamma, and s-regular if its automorphism group acts regularly on the set of s-arcs of \Gamma. Tutte (1947, 1959) showed that every cubic finite symmetric cubic graph is s-regular for some s <= 5. We show that a symmetric cubic graph of girth at most 9 is either 1-regular or 2'-regular (following the notation of Djokovic), or belongs to a small family of exceptional graphs. On the other hand, we show that there are infinitely many 3-regular cubic graphs of girth 10, so that the statement for girth at most 9 cannot be improved to cubic graphs of larger girth. Also we give a characterisation of the 1- or 2'-regular cubic graphs of girth g <= 9, proving that with five exceptions these are closely related with quotients of the triangle group \Delta(2,3,g) in each case, or of the group < x,y | x^2 = y^3 = [x,y]^4 = 1 > in the case g = 8. All the 3-transitive cubic graphs and exceptional 1- and 2-regular cubic graphs of girth at most 9 appear in the list of cubic symmetric graphs up to 768 vertices produced by Conder and Dobcsanyi (2002); the largest is the 3-regular graph F570 of order 570 (and girth 9). The proofs of the main results are computer-assisted.


Title: A more detailed classification of symmetric cubic graphs
Author(s): Marston Conder and Roman Nedela
Status: accepted for publication in Journal of Algebra
Length: 23 pages
Math Review Classification(s): 05C25, 20B25
Availability:
PDF file, dvi file
Abstract:
A graph \Gamma is called symmetric if its automorphism group acts transitively on the arcs of \Gamma, and s-regular if its automorphism group acts regularly on the set of s-arcs of \Gamma. Tutte (1947, 1959) showed that every cubic finite symmetric cubic graph is s-regular for some s <= 5. Djokovic and Miller (1980) proved that there are seven types of arc-transitive group action on finite cubic graphs, characterised by the stabilisers of a vertex and an edge. A given finite symmetric cubic graph, however, may admit more than one type of arc-transitive group action. In this paper we determine exactly which combinations of types are possible. Some combinations are easily eliminated by existing theory, and others can be eliminated by elementary extensions of that theory. The remaining combinations give 17 classes of finite symmetric cubic graph, and for each of these, we prove the class is infinite, and determine at least one representative. For at least 14 of these 17 classes the representative we give has the minimum possible number of vertices (and we show that in two of these 14 cases every graph in the class is a cover of the smallest representative), while for the other three classes, we give the smallest examples known to us. In an Appendix, we give a table showing the class of every symmetric cubic graph on up to 768 vertices.


Title: Short presentations for alternating and symmetric groups
Author(s): John Bray, Marston Conder, Charles Leedham-Green and Eamonn O'Brien
Status: accepted for publication in Transactions of the American Math. Society
Length: 9 pages
Math Review Classification(s): 20F05, 20B30
Availability:
PDF file
Abstract:
We derive new families of presentations (by generators and relations) for the alternating and symmetric groups of finite degree n. These include presentations of length that are linear in log n, and 2-generator presentations with a bounded number of relations independent of n.


Title: Pseudo-real Riemann surfaces and chiral regular maps
Author(s): Emilio Bujalance, Marston Conder and Antonio Costa
Status: accepted for publication in Transactions of the American Math. Society
Length: 17 pages
Math Review Classification(s): 30F10, 20B25, 57M60
Availability:
PDF file, dvi file
Abstract:
A Riemann surface is called pseudo-real if it admits anticonformal automorphisms but no anticonformal involution. We study general properties of the automorphism groups of these surfaces and the related uniformizing NEC groups. In particular, we prove that there are pseudo-real Riemann surfaces of every genus g > 1. Also we study pseudo-real surfaces of genus 2 and 3, and pseudo-real cyclic p-gonal Riemann surfaces, in detail. Further, we consider the maximal order of the automorphism group of a pseudo-real Riemann surface (relative to its genus), and we establish a connection between pseudo-real surfaces with maximal automorphism group, and chiral 3-valent regular maps. Finally we show there exist pseudo-real surfaces with automorphism group of maximal order for infinitely many genera, by proving the existence of concrete infinite families of chiral regular maps of type {3,k} for k > 6.


Title: Constructions for chiral polytopes
Author(s): Marston Conder, Isabel Hubard and Tomaz Pisanski
Status: accepted for publication in the Journal of the London Mathematical Society
Length: 19 pages
Math Review Classification(s): 52B15, 20B25
Availability:
PDF file, dvi file
Abstract:
An abstract polytope of rank n is said to be chiral if its automorphism group has two orbits on flags, with adjacent flags lying in different orbits. In this paper, we describe a method for constructing finite chiral n-polytopes, by seeking particular normal subgroups of the orientation-preserving subgroup of n-generator Coxeter group (having the property that the subgroup is not normalized by any reflection and is therefore not normal in the full Coxeter group). This technique is used to identify the smallest examples of chiral 3- and 4-polytopes, in both the self-dual and non self-dual cases, and then to give the first known examples of finite chiral 5-polytopes, again in both the self-dual and non self-dual cases.


Title: Flippable pairs and subset comparisons in comparative probability orderings
Author(s): Robin Christian, Marston Conder and Arkadii Slinko
Status: accepted for publication in 'Order'
Length: 24 pages
Math Review Classification(s): 60A05, 06A07
Availability:
PDF file, dvi file
Abstract:
We show that every additively representable comparative probability order on n atoms is determined by at least n-1 binary subset comparisons. We show that there are many orders of this kind, not just the lexicographic order. These results provide answers to two questions of Fishburn et al (2002). We also study the flip relation on the class of all comparative probability orders introduced by Maclagan. We generalise an important theorem of Fishburn, Pekec and Reeds, by showing that in any minimal set of comparisons that determine a comparative probability order, all comparisons are flippable. By calculating the characteristics of the flip relation for n = 6 we discover that the regions in the corresponding hyperplane arrangement can have no more than 13 faces and that there are 20 regions with 13 faces. All the neighbours of the 20 comparative probability orders which correspond to those regions are representable. Finally we define a class of simple games with complete desirability relation for which its strong desirability relation is acyclic, and show that the flip relation carries all the information about these games. We show that for n up to 6 these games are weighted majority games.


Title: Regular maps and hypermaps of Euler characteristic -1 to -200
Author(s): Marston Conder
Status: accepted for publication in Journal of Combinatorial Theory, Series B
Length: 6 pages
Math Review Classification(s): 05C25, 57M15
Availability:
PDF file, dvi file, Postscript file
Abstract:
This paper describes the determination of all orientably-regular maps and hypermaps of genus 2 to 101, and all non-orientable regular maps and hypermaps of genus 3 to 202. It extends the lists obtained by Conder and Dobcsanyi (2001) of all such maps of Euler characteristic -1 to -28, and corrects errors made in those lists for the vertex- or face-multiplicities of 14 'cantankerous' non-orientable regular maps. Also some discoveries are announced about the genus spectrum of orientably-regular but chiral maps, and the genus spectrum of orientably-regular maps having no multiple edges, made possible by observations of patterns in the extension of these lists to higher genera.


Title: Comparative probability orders and the flip relation
Author(s): Marston Conder, Dominic Searles and Arkadii Slinko
Status: accepted for publication in proceedings of 5th International Symposium on Imprecise Probabilities and their Applications (Prague, 2007)
Length: 21 pages
Math Review Classification(s): 60A05, 91B08 (primary), 06A07, 91A12, 91E99 (secondary)
Availability:
PDF file
Abstract:
In this paper we study the flip relation on the set of comparative probability orders on n atoms introduced by Maclagan (1999). With this relation the set of all comparative probability orders becomes a graph G_n. Firstly, we prove that any comparative probability order with an underlying probability measure is uniquely determined by the set of its neighbours in G_n. This theorem generalises the theorem of Fishburn, Peke\v c and Reeds (2002). We show that the existence of the underlying probability measure is essential for the validity of this result. Secondly, we obtain the numerical characteristics of the flip relation in G_6. Thirdly, we prove that a comparative probability order on n atoms can have in G_n up to F_{n+1} neighbours, where F_n is the nth Fibonacci number. We conjecture that this number is maximal possible. This partly answers a question posed by Maclagan.


Title: Reflexibility of regular Cayley maps for abelian groups
Author(s): Marston Conder, Young Soo Kwon and Jozef Siran
Status: accepted for publication in Journal of Combinatorial Theory, Series B
Length: 10 pages
Math Review Classification(s): 05C10, 05C25, 57M15
Availability:
PDF file, dvi file, Postscript file
Abstract:
In this paper, properties of reflexible Cayley maps for abelian groups are investigated, and as a result, it is shown that a regular Cayley map of valency greater than 2 for a cyclic group is reflexible if and only if it is anti-balanced.


Title: The genera, reflexibility and simplicity of regular maps
Author(s): Marston Conder, Jozef Siran and Tom Tucker
Status: accepted for publication in Journal of the European Math. Society
Length: 23 pages
Math Review Classification(s): 05C25, 57M15
Availability:
PDF file
Abstract:
This paper uses combinatorial group theory to help answer some long-standing questions about the genera of orientable surfaces that carry particular kinds of regular maps. By classifying all orientably-regular maps whose automorphism group has order coprime to g-1, where g is the genus, all orientably-regular maps of genus p+1 for p prime are determined. As a consequence, it is shown that orientable surfaces of infinitely many genera carry no regular map that is chiral (irreflexible), and that orientable surfaces of infinitely many genera carry no reflexible regular map with simple underlying graph. Another consequence is a simpler proof of the Breda-Nedela-Siran classification of non-orientable regular maps of Euler characteristic -p where p is prime.


Title: On symmetries of Cayley graphs and the graphs underlying regular maps
Author(s): Marston Conder
Status: accepted for publication in Journal of Algebra
Length: 19 pages
Math Review Classification(s): 05C25, 20B25, 57M15
Availability:
PDF file, dvi file, Postscript file
Abstract:
By definition, Cayley graphs are vertex-transitive, and graphs underlying regular or orientably-regular maps (on surfaces) are arc-transitive. This paper addresses questions about how large the automorphism groups of such graphs can be. In particular, it is shown how to construct 3-valent Cayley graphs that are 5-arc-transitive (in answer to a question by Cai Heng Li), and Cayley graphs of valency 1+3^t that are 7-arc-transitive, for all t > 0. The same approach can be taken in considering the graphs underlying regular or orientably-regular maps, leading to classifications of all such maps having a 1-, 4- or 5-arc-regular 3-valent underlying graph (in answer to questions by Cheryl Praeger and Sanming Zhou).


Title: Combinatorial and computational group-theoretic methods in the study of graphs, maps and polytopes with maximal symmetry
Author(s): Marston Conder
Status: accepted for publication in "Applications of Group Theory to Combinatorics" (ed. J. Koolen, J.H. Kwak & M.Y. Xu), Taylor & Francis
Length: 14 pages
Math Review Classification(s): 20B25 (primary), 05C25, 20F05, 52B15, 57M60 (secondary)
Availability:
PDF file
Abstract:
This paper gives a brief summary of various aspects of combinatorial group theory and associated computational methods, with special reference to finitely-presented groups and their applications, found useful in the study of graphs, maps and polytopes having maximal symmetry. Recent results include the determination of all arc-transitive cubic graphs on up to 2048 vertices, and of all regular maps of genus 2 to 100, and construction of the first known examples of finite chiral 5-polytopes. Moreover, patterns in the maps data have led to new theorems about the genus spectrum of chiral maps and regular maps with simple underlying graph.


Title: Regular hypermaps over projective linear groups
Author(s): Marston Conder, Primoz Potocnik and Jozef Siran
Status: accepted for publication in Journal of the Australian Math. Society
Length: 19 pages
Math Review Classification(s): 05C25, 20B25, 20F05, 57M15
Availability:
PDF file, dvi file, Postscript file
Abstract:
An enumeration result for orientably-regular hypermaps of a given type with automorphism groups isomorphic to PSL(2,q) or PGL(2,q) can be extracted from a 1969 paper by Sah. We extend the investigation to orientable reflexible hypermaps and to non-orientable regular hypermaps, providing many more details about the associated computations and explicit generating sets for the associated groups.


Title: Regular maps with almost Sylow-cyclic automorphism groups, and classification of regular maps with Euler characteristic -p^2
Author(s): Marston Conder, Primoz Potocnik and Jozef Siran
Status: preprint, submitted for publication
Length: 25 pages
Math Review Classification(s): 05C25, 20B25, 57M15
Availability:
PDF file, dvi file, Postscript file
Abstract:
A regular map M is a cellular decomposition of a surface such that its automorphism group Aut(M) acts transitively on the flags of M. It can be shown that if a Sylow subgroup P of Aut(M) has order coprime to the Euler characteristic of the supporting surface, then P is cyclic or dihedral. This observation motivates the topic of the current paper, where we study regular maps whose automorphism groups have the property that all their Sylow subgroups contain a cyclic subgroup of index at most 2. The main result of the paper is a complete classification of such maps. As an application, we show that no regular maps of Euler characteristic -p^2 exist for p a prime greater than 7.


Last updated: 24 December 2007