List of talks and abstracts
Martin Bachratý:
Brown graphs and vertex transitivity
(a joint work with Jozef Širáň)
Brown graphs are a basis for construction of the largest currently
known graphs of diameter 2 and given maximum degree. As these graphs
are not vertex-transitive, it is natural to ask how one can obtain a
vertex-transitive graph from a Brown graph by adding as few edges as
possible. We investigate two ways of constructing vertex-transitive
graphs of diameter two from Brown graphs.
Antonio Breda d'Azevedo:
Reflexible to chiral ratio of regular maps with prime number of faces
(a joint work with Elisa Fernandes)
This talk addresses a standing question about the asymptotic behaviour of the
reflexible to chiral ratio of regular oriented maps. Two previous works, one by
Drmota and Nedela on oriented maps (regardless of genus and regularity)
and the other by Hubard and Leemans on regular polyhedra with Suzuki
automorphism groups, seems to sustain nil asymptotic ratios. Following a recent work by Maria Elisa Fernandes and myself we present in this tal the first example of a non-nil asymptotic ratio. For each positive integer
n and each prime p, we determine the number of reflexible and chiral regular
oriented maps with p faces of valency n, and compute the limit of the reflexible
to chiral ratio of the regular oriented maps with p faces. The limit depends on
p and for certain primes p we show that the limit can be 1, greater than 1 or
less than 1.
Domenico Antonino Catalano:
Regular pseudo-oriented maps and hypermaps of low genus
(a joint work with Antonio Breda and Rui Duarte)
Pseudo-orientable maps were introduced by Wilson in 1976 to describe non-orientable regular maps for which it is possible to assign opposite orientations to adjacent vertices. This property extends naturally to non-orientable and orientable hypermaps. In this talk we give a classification of regular pseudo-oriented maps and hypermaps of characteristic down to -3. With the help of GAP and its library of small groups, we extend the classification down to characteristic -11.
Thomas Connor:
C-groups constructed from almost simple groups of Suzuki type
(a joint work with Dimitri Leemans)
C-groups are quotients of Coxeter groups. During the last decade a lot of attention has been dedicated to the study of string C-groups (i.e. abstract regular polytopes), with many spectacular results. In partic- ular, a large interest is given to the string C-groups related to finite almost simple groups. In this talk, I will present some recent progress made toward the study of C-groups without the string diagram condition. I will detail the following theorem and sketch the main steps of the proof.
Theorem. Let G be a finite almost simple group of Suzuki type and let S be a set of involutions of G such that (G,S) is a C-group. Then G is simple and S has size 3. Moreover, for each G = Sz(q), there exist a string C-group representation and a non-string C-group representation of G.
Julie De Saedeleer:
Abstract regular polytopes whose full automorphism group is an almost simple group of $PSL(2, q)$-type
(a joint work with Thomas Connor and Dimitri Leemans)
I will present some resent research toward the study of abstract regular polytopes of PSL(2,q)-type. The case of PSL(2,q) and PGL(2,q) have been classified in the last decade by Leemans and Schulte, therefore, leading the way to the general case. We investigate this for all almost simple groups of PSL(2,q)-type, for q a prime power. We were able to constrain the list of such possible groups and bound the rank of a polytope for any of them.
In this talk I will discuss this research, which is joint work with Dimitri Leemans and Thomas Connor.
Shaofei Du:
2-Arc-Transitive Cyclic Covers of $K_{n,n}-nK_2$
(a joint work with Wenqin Xu)
In [J. Combin. Theory B 74 (1998) 276-290] and [J. Combin. Theory B 93 (2005) 73-93], Du et al. classified regular covers of complete graph whose fiber-preserving automorphism group acts 2-arc-transitively, and whose covering transformation group is either cyclic or isomorphic to $\mathbb{Z}_p^2$ or $\
\mathbb{Z}_p^3$ with $p$ a prime.
In this paper, a complete classification is achieved of all the regular covers of bipartite complete graphs minus a matching $K_{n,n}-nK_2$ with cyclic covering transformation groups, whose fibre-preserving automorphism groups act 2-arc-transitively.
Rui Duarte:
Coverings of regular hypermaps on the sphere and on the projective plane
A hypermap is a cellular embedding of a hypergraph in a compact connected surface. It is well known that there is a correspondence between hypermaps and cocompact subgroups of the free product $\Delta = C_2 * C_2 * C_2$. Hypermaps having the maximum possible number of symmetries are called regular and correspond to normal subgroups of $\Delta$. In this talk we give a partial classification of the hypermaps on the sphere and on the projective plane associated with subgroups which are normal in some subgroup of $\Delta$ (but may not be normal in $\Delta$).
Eduard Eiben:
$2$-connected equimatchable graphs on surfaces
(a joint work with Michal Kotrbčík)
A graph $G$ is equimatchable if any matching of $G$ is a subset of a maximum-size matching.
From a general description of equimatchable graphs in terms of Gallai-Edmonds decomposition it follows that any 2-connected equimatchable graph is either bipartite or factor-critical. In both cases, the Gallai-Edmonds decomposition gives little additional information about the structure of such graphs.
It is easy to see that
for any vertex $v$ of a
factor-critical equimatchable graph $G$ and a minimal matching $M$ that isolates $v$ the components of the graph $G\setminus(M\cup\{ v\})$ are all either complete or regular complete bipartite. We prove that for any $2$-connected factor-critical equimatchable graph $G$, the graph $G\setminus(M\cup\{ v\})$ has at most one
component, and use this result to establish that the maximum size of such graphs embeddable in the orientable surface of genus $g$ is $\Theta(\sqrt{g})$.
Moreover, for any nonnegative integers $g$ and $k$ we provide a construction of arbitrarily large $2$-connected equimatchable bipartite graphs with orientable genus $g$ and a genus embedding with face-width $k$.
María del Río Francos:
Flag graphs and symmetry type graphs
(a joint work with Isabel Hubard and Tomaz Pisanski)
A k-orbit map is a map with k orbits on its flags under the action of its automorphism group. Orbanic, Pellicer and Weiss studied k-orbit maps for k<5, and presented results on the medial and truncation of k-orbit maps. Combinatorially, each map is represented by its flag graph. We define a graph, called the symmetry type graph of the map, that relates the flag orbits of a map. We use the symmetry type graph on the results of medial and truncation by Orbanic, Pellicer and Weiss. This is, given a map M and its image M’, under an operation such as dual, Petrie, medial, truncation, leapfrog or chamfering, we find the relation between the symmetry type graph of M and the symmetry type graph of M’. Furthermore, we extend the notion of symmetry type graph to that of maniplexes and polytopes and make use of them to study k-orbit maniplexes and determine all face transitivities for 3- and 4-orbit maniplexes. Moreover, we give generators of the automorphism group of a polytope or a maniplex given its symmetry type graph. This work is part of the research conducted by the presenter for the fulfilment of the PhD.
Nick Gill:
Regular maps and finite simple groups
I describe joint work with M. Conder, J. Siran and I. Short. We are interested in how finite simple groups can crop up as automorphisms of regular maps. It turns out that by examining the prime factorization of the Euler characteristic of the associated surface we can immediately tell which finite simple groups are candidates as automorphism groups. We aim to use this fact to classify regular maps on surfaces with prime power Euler characteristic.
Jonathan L Gross:
Iterated Claws Have Real-Rooted Genus Polynomials
(a joint work with Toufik Mansour, Thomas W. Tucker, David G.L. Wang)
Abstract. We prove that the genus polynomials of the graphs called iterated claws are real-rooted. This continues our work directed toward the 25-year-old conjecture that the genus distribution of every graph is log-concave. We have previously established log-concavity for sequences of graphs constructed by iterative vertex-amalgamation or iterative edge-amalgamation of graphs that satisfy a commonly observable condition on their partitioned genus distributions, even though it had been proved previously that iterative amalgamation does not always preserve real-rootedness of the genus polynomial of the iterated graph. In this paper, the iteratedtopological operations are adding a claw and adding a 3-cycle, rather than vertex- or edge-amalgamation. Our analysis here illustrates some advantages of employing a matrix representation of the transposition of a set of productions.
Štefan Gyürki:
Two new infinite families and some sporadic examples of directed strongly regular graphs
(a joint work with Mikhail Klin)
The notion of a directed strongly regular graph (DSRG) was introduced by A. Duval in 1988 as one of the possible generalizations of classical strongly regular graphs to the directed case.
A directed strongly regular graph (DSRG) with parameters (n,k,μ,λ,t) is a
regular directed graph on n vertices with valency k, such that every vertex is incident with t
undirected edges, and the number of directed paths of length 2 from a vertex u to another vertex v is
λ, if there is an arc from u to v, and μ otherwise.
The adjacency matrix A=A(Γ) of a DSRG with parameters (n,k,μ,λ,t),
satisfies AJ=JA=kJ and A2=tI+λ A+μ(J-I-A).
It is clear that a DSRG with t=k is a
strongly regular graph, while with t=0 is a doubly regular tournament.
We present two constructions, which give a DSRG for all n≥ 2 with parameter sets
(2n2, 3n-2, 3, n-1, 2n-1) and (2n2, 4n-2, 6, n+2, 2n+2), respectively.
For the first parameter set there was known such a construction (Fiedler et al.)
just for the case when n is a prime power, while the second is completely new.
Both constructions can be described with the aid of Cayley digraphs over suitable groups,
but also may be viewed
as a kind of join of two isomorphic copies of lattice graphs of order n2.
Finally, we present several sporadic examples of DSRGs which can be constructed using voltage assignments,
or described as "nice" embeddings in the torus. Our courrent approach was inspired by attempts
to better understand new example of DSRG on 108 vertces, which was recently discovered by Leif Jorgensen [2].
For more information on DSRGs and references we recommend to visit the webpage of A.E. Brouwer and S. Hobart [1].
References
[1] A.E. Brouwer, S. Hobart, Tables of directed strongly regular graphs, (March 2013), http://homepages.cwi.nl/~aeb
[2] L.K. Jorgensen, Variations and generalizations of Moore Graphs, The International Workshop on Optimal Networks Topologies 2012, Bandung. Slides are available on http://people.math.aau.dk/~leif
Kan Hu:
Group Extensions and Coverings of Maps
We study cyclic regular coverings of the platonic maps, possibly branched simutaneously over face-centres and vertices. We show that such a covering belongs to a more general category which we call almost totally branched coverings. An almost totally branched covering between two orientably regular maps of types {n_i,m_i} (i=1,2) is extremal in the sense that the size of CT(p) is minimal in the class of regular coverings between orientably regular maps of such types. Several characterisations of almost totally branched coverings are presented. Applying this theory, we give a complete classification of almost totally branched coverings of the platonic maps with abelian covering transformation groups.
Veronika Hucíková:
Regular maps of a given type without external symetries
A map on an orientable surface is regular if its automorphism group is
transitive, and hence regular, on darts. Such a map has type {m,n} if the
vertex degrees and the face lengths are m and n; the type is hyperbolic if 1/m
+ 1/n < 1/2. If the operators of duality, Petrie-duality, or taking a power of
a regular map result in an isomorphic copy of the map, we speak of external
symmetries of the map. In particular, if the (-1)th power of a regular map is
isomorphic to the original map, the map is reflexible; otherwise it is chiral.
In the talk we will give an affirmative answer to the question of the existence
of a chiral regular map of any given hyperbolic type and address the more
general question of the existence of regular maps of a given hyperbolic type
without external symmetries. The method is based on designing `small`
non-regular maps whose monodromy groups are symmetric or alternating (and
satisfy some extra conditions) and identifying these groups with the regular
maps to be constructed.
This is a report on a joint work with M. Conder, R. Nedela and J. Siran.
Peter Hudák:
Light edges and paths in a 4-critical planar graphs
A graph $G$ is $k$-critical if $\chi(G)=k$ and $\chi(H)<\chi(G)$ for every proper sub-graph $H$ of $G$. It is well known that every planar graph is 4-colorable, therefore class of 4-critical planar graphs is extremal class of planar graphs (in sense of colorability). Koester proved that every 4-critical planar graph contains vertex of degree at most 4 and this bound is best possible. We will prove that every 4-critical planar graph contains an edge of low weight.
Fabrici and Jendroľ showed that if 3-connected planar graph $G$ contains $k$-vertex path as a subgraph then it contains $P_{k}$ such that $\Delta_{G} (P_{k})\leq 5k$. We will present similar theorem for 4-critical planar graphs and show that this bound is, in this case, exponential.
Gareth Aneurin Jones:
Umbrellas, and a hypermap of genus 2742118830047232000000000000000001
In certain combinatorial, geometric and topological categories, such as maps, hypermaps, polytopes and surface coverings, the objects can be identified with conjugacy classes of subgroups of a fixed finitely generated group $F$. The regular objects, those with greatest symmetry, correspond to normal subgroups $N$ of $F$, with their automorphism groups isomorphic to $F/N$. If $G$ is a finite group there are only finitely many such regular objects with automorphism group $G$. I shall explain how to enumerate them, how to represent them all as quotients of a single regular object, the umbrella $U(G)$ for $G$, and how the outer automorphism group of $F$ acts on them. For example, for the category of oriented hypermaps (= bipartite maps), $F$ is the free group of rank 2. In this case, if $G$ is a cyclic group of order $n$ then $U(G)$ is a regular embedding of the complete bipartite graph $K_{n,n}$ on a surface of genus $(n-1)(n-2)/2$. On the other hand, if $G$ is the alternating group $A_5$ then $U(G)$ has genus $2742118830047232000000000000000001$. For other non-abelian finite simple groups, the genus is significantly larger.
Ján Karabáš:
Discrete group actions on Riemann surfaces: construction, classification, and applications
(a joint work with Roman Nedela)
We consider the problem of classification of discrete actions of groups on Riemann surfaces of genus $g \geq 2$. The classification is done up to equivariance of actions, i.e. two actions are considered to be the same if there exist an automorphism of a discrete group such that the composition of the automorphism and a particular action equals to the second (equivariant) action. It is also possible to consider other kinds of equivalences studied in the fields of complex analysis or crystallography.
Lists of discrete group actions have many applications in different fields of mathematics, ranging from discrete mathematics, through complex analysis to the geometry. For exmaple, in the theory of maps one can use these lists to determine all highly symmetrical maps of fixed genus: regular maps, vertex-transitive maps, Cayley maps, or edge-transitive maps. The classification of actions of cyclic groups plays a crucial role for enumeration problems of combinatorial objects, i.e. maps, graphs, etc. Classification results can be used as an experimental material for further research, as well.
The classification of groups acting on the sphere is a classical part of crystallography. In the case of torus the situation is known in general, though there are infinitely many group actions. Thanks to the Riemann-Hurwitz equation (Hurwitz bound) we know that for higher genera there are just finitely many finite groups acting on a surface of a given genus. Published lists of actions go up to genus equal to five (Broughton; Bogopolskij; Kuribayashi and Kimura). For small genera, the the classification can be done with help of computer algebra systems. Using Magma we derived the list of actions of all discrete groups on Riemann surfaces of genus $2\leq g\leq 21$. Let us note that if one considers just actions of "large groups", the situation is different -- actions are known up to genus $g=301$ (602 in non-orientable case).
Pavel Klavík:
Polynomial-time Algorithm for Planar Regular Covers
(a joint work with Jiri Fiala, Jan Kratochvil, Roman Nedela)
We study the decision problem called the regular cover problem. The input gives graphs G and H, and we ask whether G regularly covers H. We show that for a planar input G the problem is solvable in polynomial-time. In general, it seems that the complexity of the regular cover problem is closely related to the graph isomorphism problem.
Our polynomial-time algorithm is based on structural results, similar to the paper of Negami on planar regular covers. We proceed the input graph by a series of reduction which behave nice with the respect to the automorphism group Aut(G).
Martin Knor:
Graphical models of hyperbolic fullerenes
Fullerenes can be modelled by cubic spherical maps of face-type $(5,6)$, that is, with pentagonal and hexagonal faces only. Any such map necessarily contains 12 pentagons and $a$ hexagons, where $a$ can be any integer number except 1. In the talk we consider analogous problem for orientable surfaces of higher genera. We study cubic polyhedral maps of face-type $(6,k)$, where $k\in\{7,8\}$ and we completely solve the problem of existence such maps with exactly $a$ hexagons.
Michal Kotrbčík:
Locally maximal embeddings
(a joint work with Martin Škoviera)
We introduce the concept of a locally maximal embedding of a graph as a
2-cell embedding on an orientable surface whose genus cannot be raised by
any elementary operation on the rotation system. We prove that several
natural choices of the elementary operation lead to the same class of
locally maximal embeddings. We further show that locally maximal
embeddings are characterised by the property that every vertex is incident
with at most two faces and derive a natural lower bound on the minimum
genus of a locally maximal embedding of a graph in terms of maximum number
of disjoint cycles and cycle rank. Locally maximal embeddings generalize
maximum-genus embeddings and we indicate the interplay among
minimum-genus, maximum-genus, and locally maximal embeddings.
JIn Ho Kwak:
Enumerating reflexible 2-cell embeddings of connected graphs
(a joint work with YanQuan Feng and JinXin Zhou)
Two 2-cell embeddings ı : X → S and j : X → S of a connected graph X into a closed orientable surface S are congruent if there are an orientation-preserving surface homeomorphism h on S and a graph automorphism γ of X such that ıh = γj. A 2-cell embedding of X is reflexible if it is congruent to its mirror image. In this paper we introduce a method for enumerating the congruence classes of reflexible 2-cell embeddings of graphs into closed orientable surfaces, and apply it to the complete graphs, the bouquets of circles, the dipoles and the wheel graphs to count their congruence classes of reflexible or nonreflexible (called chiral) embeddings.
Young Soo Kwon:
Regular embeddings of several graph products
In this talk, we will consider regular embeddings of several graph products like cartesian product, tensor product(weak product), strong product and lexicographic product and so on.
Dimitri Jean Jacques Leemans:
Enumeration of regular maps associated to a given group and an application to the O'Nan sporadic simple group
(a joint work with Thomas Connor)
Given a finite group G, we describe an algorithm that enumerates the regular maps for G using the knowledge of its table of ordinary characters and its subgroup lattice. To show that our algorithm is efficient, we use it to compute that, up to isomorphism, there are 796,772 regular maps whose rotational subgroup is the sporadic simple group of O'Nan and Sims.
Alexander Mednykh:
On the Riemann-Hurwitz formula for branched graph coverings
The aim of this report is to present a few versions of the
Riemann-Hurwitz formula for a regular branched covering of graphs. By
a graph, we mean a finite connected multigraph. The genus of a graph
is defined as the rank of the first homology group. We consider a finite
group acting on a graph, possibly with fixed and revised edges, and the
respective factor graph. Then, the obtained Riemann-Hurwitz formula
relates genus of the graph with genus of the factor graph and orders of
the vertex and edge stabilisers.
Seiya Negami:
Bipartite planar coverings and even embeddings of graphs on the projective plane
We shall give a topic around Planar Cover Conjecture, proposed by Negami in 1986; a connected graph can be embedded on the projective plane if and only if it has a finite planar covering. A 2-cell embedding of a graph on a closed surface is said to be even if every face is bounded by a closed walk of even length. We shall show that a 3-connected graph has an even embedding on the projective plane if and only if it has a finite bipartite planar covering and does not contain two disjoint odd cycles. If Planar Cover Conjecture is true, then the assumption of being 3-connected can be omitted. We shall follow the history of the conjecture to understand this.
Kenta Noguchi:
Congruence classes of monodromies
A triangulation $G$ on a surface $F^2$ is a map of a simple graph on $F^2$ such that every face is triangular.
An triangulation $G$ is said to be even if every vertex degree is even.
Let $G$ be an even triangulation on $F^2$.
A monodromy of G is a homomorphism $\sigma_G : \pi_1(F^2) \to S_3$, see [1].
It is an invariant of even triangulations on surfaces.
Congruence classes of monodromies are defined by homeomorphism on $F^2$,
but the number of them is not determined.
In this talk, we determine the number of congruence classes of monodromies on each surface, and investigate their characteristics.
[1] K. Kawarabayashi, A. Nakamoto and Y. Suzuki, N-flips in even triangulations on surfaces, J. Combin. Theory Ser. B 99(2009), 229--246.
Kenta Ozeki:
A necessary and sufficient condition for graphs on a surface to have a cyclic 4-coloring
(a joint work with Atsuhiro Nakamoto and Kenta Noguchi)
To attack the Four-Color Theorem, in 1880, Tait gave a necessary and sufficient
condition for plane triangulations to have a proper 4-vertex-coloring;
A plane triangulation G has a proper 4-vertex-coloring if and only if the dual of $G$ has a proper 3-edge-coloring. A cyclic coloring of a map $G$ on a surface $F^2$ is a vertex-coloring of $G$ such that any two vertices $x$ and $y$ receive different colors if $x$ and $y$ are incident with a common face of $G$.
In this talk, we extend the result by Tait to two directions, that is, considering maps on a non-spherical surface and cyclic 4-colorings.
This is a joint work with Atsuhiro Nakamoto (Yokohama National University) and
Kenta Noguchi (Keio University).
Sven Reichard:
Non-Schurian Three-Class Association Schemes
An association scheme is
Schurian if its basic relations are
the orbits of the action of a suitable permutation group on ordered
pairs of points (2-orbits in the sense of Wielandt). Thus each
transitive finite permutation group gives rise to a Schurian
scheme. For a non-Schurian scheme to exist we need some
"combinatorial coincidence".
An undirected graph of diameter d is distance-regular if it is
a basis graph of a d-class scheme. A scheme which has such a basis
graph is called metric. R. Mathon [1] described a class of
non-Schurian metric 3-class schemes related to suitable imprimitive
actions of the simple group G=PSL(2,q). The group has many
2-orbits, thick and thin. Each thick 2-orbit gives a
distance-regular graph ("Mathon graphs"). We call the association
scheme of this action of PSL(2,q) Mathon's master association
scheme.
Inspired by questions posed by Nevo-Thurston we give an alternative
description of the master association scheme in terms of symplectic
forms, and completely describe its structure constants. We show that
a cyclic group C acts naturally on the set of Mathon
graphs. Furthermore, choosing any difference set in C and merging
the corresponding graphs leads to a new infinite class of non-Schurian
3-class schemes.
The results presented here were obtained jointly with M. Klin.
[1] Mathon, R.
Lower bounds for Ramsey numbers and association schemes.
Journal of Combinatorial Theory, Series B 42, 122-127 (1987)
Egon Schulte:
Classification of Regular and Chiral Polytopes by Topology
The past three decades have seen a revival of interest in the study of polytopes and their symmetry. The most exciting new developments all center around the concept and theory of abstract polytopes. The lecture gives a survey of currently known topological classification results for regular and chiral polytopes, focusing in particular on the universal polytopes which are globally or locally toroidal. While there is a great deal known about toroidal regular polytopes, there is almost nothing known about the classification locally toroidal chiral polytopes.
Yusuke Suzuki:
Cube-contractions in $3$-Connected Quadrangulations
A 3-connected quadrangulation of a closed surface is said to be
$K'_3$-irreducible if each of a face-contraction and a cube-contraction
cannot be applied preserving the simplicity and the 3-connectedness.
We prove that a $K'_3$-irreducible quadrangulation of a closed surface
except the sphere and the projective plane is either (i) irreducible or (ii) obtained from an irreducible quadrangulation H by applying 4-cycle additions
to $F_0 \subseteq F(H)$. We also determine $K'_3$-irreducible quadrangulations
of the sphere and the projective plane individually. These results imply another generating theorems of 3-connected quadrangulations of closed surfaces.
Pavol Široczki:
On the dimension of graphs of Archimedean solids
(a joint work with Tomáš Madaras)
We study the dimension of graphs (that is the smallest integer $n$ such
that the graph has an unit-distance representation in the $n$-
dimensional euclidean space) of the Archimedean solids. For most of
these graphs (with the exception of the rhombicosidodecahedron and the
truncated icosidodecahedron, whose unit-distance embeddings
seem to be hard to find) we either show that they are unit-distance embeddable
in the euclidean plane or prove that such an embedding does not exist.
Katarína Škrovinová:
Linear fractional groups and Möbius regular maps
Möbius regular maps are non-orientable regular maps whose underlying graphs have edges of multiplicity 2 and every cycle of length 2 forms a central cycle of a Möbius band in the supporting surface of the map. We will present a classification of Möbius regular maps with automorphism group isomorphic to PSL(2,q) or PGL(2,q) using canonical generators of these groups.
Shoichi Tsuchiya:
Triangulations on the plane without spanning Halin subgraphs
(a joint work with Guantao Chen, Hikoe Enomoto, Kenta Ozeki)
A Halin graph, defined by Halin, is a plane graph $H=T∪C$ such that $T$ is a spanning tree of $H$ with no vertices of degree 2 where $|T|$ is at lease 4 and $C$ is a cycle whose vertex set is the set of leaves of $T$. In 1975, Lovasz and Plummer conjectured that "every 4-connected plane triangulation has a spanning Halin subgraph". In this talk, we disprove the conjecture.
Thomas Tucker:
The Infinite Motion Conjecture
(a joint work with Wilfried Imrich, Simon Smith, Mark Watkins)
The Infinite Motion Conjecture for graphs states that if the graph G is locally finite and every non-identity element of Aut(G) moves infinitely many vertices, then there is a non-empty subset with trivial (setwise) stabilizer, that is, G has distinguishing number two. The conjecture holds in many special cases: when Aut(G) is countable, when different vertices have different n-spheres for all n, when Aut(G) is primitive, when Aut(G) has a finite base. A variation of Cantor’s back-and-forth argument on the directed graph with vertex set the rationals and edge from r to s if r < s, shows the condition of local finiteness is necessary for directed graphs. No such example is known for undirected graphs.
Timothy Robert Walsh:
Generating nonisomorphic maps and hypermaps without storing them
In 1979, while working as a senior researcher in the Computing Centre of the USSR Academy of Sciences in Moscow, I used A.B. Lehman's code for rooted maps of any orientable genus to generate these maps. By imposing an order on the code-words and keeping only those that are maximal over all the words that code the same map with each semi-edge chosen as the root, I generated these maps up to orientation-preserving isomorphism, and by comparing each of them with the code-words for the map obtained by reversing the orientation, I generated these maps up to a generalized isomorphism that could be orientation-preserving or orientation-reversing. The limitations on the speed of the computer I was using and the time allowed for a run restricted me to generating these maps with up to only six edges. In 2011, by optimizing the algorithms and using a more powerful computer and more CPU time I was able to generate these maps with up to eleven edges. An average-case time-complexity analysis of the generation algorithms is included. And now, by using a genus-preserving bijection between hypermaps and bicoloured bipartite maps that I discovered in 1975 and the condition on the word coding a rooted map for the map to be bipartite, I generated hypermaps, both rooted and unrooted, with up to twelve darts.
Naer Wang:
Regular bipartite maps
A finite group $G$ is called transpositive if it is generated by two elements, say x and y, and there is an automorphism of $G$ transposing the generators. The triple $(G,x,y)$ will be called a transtriple. Two transtriples $(G_i,x_i,y_i) $ $(i=1,2)$ are equivalent if the assignment $x_1\to x_2$, $y_1\to y_2$ extends to a group isomorphism from $G_1$ to $G_2$. It follows that the equivalence classes of transpositive groups are in one-to-one correspondence with the isomorphism classes of regular bipartite maps. We consider the classification of regular bipartite maps with a nilponent orientation and color preserving automorphism group, or equivalently, the classification of nilpotent transpositive groups. We show that the classification problem can be reduced to the classification of transpositive $p$-groups. The transpositive $p$-groups of class 1 and class 2 are completely classified.
Asia Ivic Weiss:
Hereditary Polytopes
(a joint work with M. Mixer and E. Schulte)
Every regular polytope has the remarkable property that it inherits all symmetries of each of its facets. This property distinguishes a natural class of polytopes which are called hereditary. Regular polytopes are by definition hereditary, but the other polytopes in this class are interesting, have possible applications in modeling of structures, and have not been previously investigated. We establishe the basic theory of hereditary polytopes, focussing on the analysis and construction of hereditary polytopes with highly symmetric faces.
Min Yan:
Tiling of the sphere by congruent pentagons
Compared with extensive knowledge about the tiling of the plane, not much is known about the tilings of the sphere. A major result is the classification of edge-to-edge tilings of the sphere by congruent triangles. Sommerville initiated the classification in 1923, and the full classification was completed by Ueno and Agaoka in 2002.
The tiles in an edge-to-edge tilings of the sphere by congruent polygons must be triangles, quadrilaterals or pentagons. The pentagonal tilings should be relatively easier than the quadrilateral ones because 5 is another extreme among 3,4,5. However, the pentagon is more complicated than the triangle because the congruence in edges is not equlvalent to the congruence in angles. So we need to separately study the combinatorial, edge length, and angle aspects of the congruence.
We already know the complete classification of the minimal case of the tiling of the sphere by 12 congruent pentagons. In this talk, we will report what we know beyond the minimal case. Combinatorially, the next simplest case is what we call the earth map tilings, and the case is related to the distances between vertices of degree >3. For the edge length aspect, we studied the case when there is a tile such that all vertices have degree 3 and completely classified edge congruent earth map tilings. For the angle congruence aspect, we developed a systematic way of classifying the possible numerics in the angles combinations in pentagon and at various vertices. We also have some partial results on the geometrical (i.e., edge as well as angle) congruence, and showed that geometrically congruent tilings do not exists for certain edge length combinations.
Although pentagonal spherical tilings are much more complicated than triangular ones, what we learned so far makes us fairly optimistic that a complete classification can be achieved.