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