List of talks and abstracts
Marcel Abas:
On regular map homomorphisms
We say that a map homomorphism $f: M\to M'$ is \textit{regular} if there exists a subgroup
$\Gamma$ of $Aut(M)$ such that for any two flags $x_1, x_2$ of $M$ we have $f(x_1)=f(x_2)$ if and only if
$x_2=\varphi(x_1)$ for some map automorphism $\varphi\in \Gamma$. If $f: M\to M'$ and $f': M'\to M''$ are
regular homomorphisms, the homomorphism $\tilde f: M\to M''$ given by $\tilde f(x)=f'(f(x))$ can be regular as
well as non-regular.
If $\Gamma$ is a subgroup of $Aut(M)$ then the natural projection $f$ from $M$ to the quotient map $M/\Gamma$ is
a regular map homomorphism. In this contribution we show that if $\Gamma$ is the direct product of groups
$\Gamma_1$ and $\Gamma_2$ (subgroups of $Aut(M)$) then the homomorphisms
$f_{12}:M\to (M/\Gamma_1)/\Gamma_2$ and $f_{21}:M\to (M/\Gamma_2)/\Gamma_1$ are regular and the corresponding
quotient maps are isomorphic.\\
\textbf{Key words:} regular map homomorphism, quotient map
Antonio Breda d'Azevedo:
Primer hypermaps and their role in the classification of regular
hypermaps with p (prime) hyperfaces
A (face-)primer hypermap is a regular hypermap with no regular proper
quotients with the same number of hyperfaces.
Primer hypermaps are then regular hypermaps whose automorphism group
induce a faithful action on its hyperfaces.
This has been important in the classification of the orientably-regular
hypermaps with p (prime) hyperfaces. In this talk we speak about the
classification of primer hypermaps with p hyperfaces and the role that
primer hypermaps have in the previously mentioned classification.
Domenico Antonino Catalano:
On
the classification of regular embeddings of hypercubes.
The first non-trivial examples of regular
embeddings of hypercubes $Q_n$ were given in 1997 by Nedela and
Skoviera. If $n$ is odd, these are all the regular embeddings of $Q_n$
(Du, Kwak and Nedela 2007). If $n$ is even there are more examples
(Kwon, 2004), which give all the regular embeddings of $Q_{2m}$ if $m$
is odd (Xu, 2007). Recently, Nedela and I remarked that new examples
arises if $n$ is a multiple of 16. Finally, in a joint work with Conder,
Du, Kwon, Nedela and Wilson, we were able to prove that there are no
more examples at all, that is, all the regular embeddings of $Q_n$ are
classified.
Marston Conder:
Recent
progress in the study of regular maps on surfaces
I will give a summary of some recent
developments in the study of regular (and rotary) maps on surfaces.
These include: \newline (a) the determination of all such maps of Euler
characteristic $-1$ to -200; \newline (b) discovery that for infinitely
many $g > 1$, every rotary map on an orientable surface of genus $g$ is
reflexible; \newline (c) discovery that for infinitely many $g > 1$,
there is no regular map on an orientable surface of genus $g$ with
simple underlying graph; \newline (d) the equivalence between
reflexibility and the `anti-balanced' property of regular Cayley maps
for cyclic groups; \newline (e) a complete classification of all rotary
and regular embeddings of the $n$-dimensional cube graphs $Q_n$; and
\newline (f) a complete classification of all rotary and regular
embeddings of finite arc-transitive circulants (or, equivalently, of all
regular Cayley maps for finite cyclic groups). \newline Various parts of
these were obtained in joint work with Domenico Catalano, Shaofei Du,
Young Soo Kwon, Roman Nedela, Jozef Siran, Tom Tucker and Steve Wilson.
Július Czap:
Looseness
of Plane Graphs
All considered graphs are finite, loops and
multiple edges are allowed. Let $G=(V,E,F)$ be a connected plane graph
with the vertex set $V$, the edge set $E$ and the face set $F$.
A $k$-colouring of a graph $G$ is a mapping $\varphi : V
\rightarrow \{1,\dots,k\}$. \bigskip For a face $f\in F$ we define
$\varphi(f)$ to be the set of colours used on the vertices incident with
the face $f$. A face $f$ is called loose if $|\varphi (f)| \geq
3$.
Question: What is the minimum number of colours
$ls(G)$ that any surjective vertex colouring of a connected plane graph
$G$ with $ls(G)$ colours enforces a loose face?
The invariant
$ls(G)$ of a plane graph $G$ is called the looseness of $G$.
We prove that the looseness of a connected plane graph $G$
equals $2$ plus the maximum number of vertex disjoint cycles in the dual
graph $G^*$. \bigskip We also show upper bounds on the looseness of
graphs based on the edge connectivity, the girth of the dual graphs and
other basic graph invariants. Moreover, we present infinite classes of
graphs where these equalities are attained.
Bibliography
-
J. Czap, S. Jendroľ, F. Kardoš and J. Miškuf,
Looseness of plane graphs
(
http://umv.science.upjs.sk/preprints/dokumenty/A3-2009.pdf
)
Shaofei Du:
Regular
Embeddings of graphs of order $pq$
In this talk, I give a classification of
(orientable and nonorientable) regular embeddings of graphs of order
$pq$, where $p$ and $q$ are primes.
Rui Duarte:
Constructions
of bipartite and bipartite-regular hypermaps
A hypermap is bipartite if we can divide its
set of flags in two parts in such a way that each part is the union of
hypervertices, and consecutive hypervertices around a hyperedge or a
hyperface are contained in alternate parts. A bipartite hypermap is
bipartite-regular if its automorphism group acts transitively on each
set of flags. In this talk we will see some properties of the
constructions of bipartite hypermaps described algebraically by Breda
and Duarte that generalize the correspondence of Walsh between hypermaps
and bipartite maps. We will use these properties to show that not all
bipartite hypermaps are obtained using these constructions, and that all
surfaces have bipartite-regular hypermaps.
Rongquan Feng:
TBA
Yan-Quan Feng:
Tetravalent
half-arc-transitive graphs of order $2pq$
A graph is half-arc-transitive if its
automorphism group acts transitively on its vertex set, edge set, but
not arc set. In this talk, we classify tetravalent half-arc-transitive
graphs of order $2pq$, where $p$ and $q$ are primes.
tefan Gyürki:
Goal-minimally
$k$-diametric graphs from finite fields
An undirected graph $G$ with diameter $k$ is said to be goal-minimally $k$-diametric ($k$-GMD
for short)
if for every edge $uv$ of $G$, the distance $d_{G-uv}(x,y)$ is greater then $k$ if and only if
$\{x,y\}=\{u,v\}$.
Such graphs were introduced by Ky\v s \cite{ky} in 1980. He constructed such graphs for $k=1,2,3,4$, and $6$
and conjectured that $k$-GMD graphs exist for all $k$.
Graphs with described property were also studied by
Gliviak and Plesn\'\i k \cite{gp} in 2006.
Plesn\'\i k \cite{pl} gave several examples of $k$-GMD graphs for $k=5,7,8,10,12$, and $14$.
Recently, Gy\"urki \cite{gu} has constructed some 9-GMD and 13-GMD graphs by voltage assignments and lifts.
Inspired by Conder's construction of Cayley near-cages (see \cite{co}),
we have studied a family of cubic Cayley graphs in $PSL(2,q)$. As a result
we obtained over ninety new $k$-GMD graphs, including graph for
$k=12$, $16\leq k\leq 26$, except of $k=17$ and 25.
Petr Hlinĕný:
Planar
emulators: On a surprising fall of Fellows' conjecture, and beyond
A {\em cover} of a graph is a locally bijective homomorphism.
Applications in topological graph theory led Seiya Negami to studying
the problem of existence of a (finite) planar cover of a graph.
Along results relating the existence of double or regular planar covers
to embeddability in the projective plane, he conjectured in 1988:
A connected graph has a finite planar cover if and only if it
embeds in the projective plane.
Independently of Negami, Mike Fellows studied planar emulators of graphs
in his 1985 thesis.
An {\em emulator} of a graph is a locally {\em surjective} homomorphism.
He formulated the following conjecture in 1988:
A connected graph has a finite planar emulator if and only if it
has a finite planar cover.
In view of the latter, researchers have so far concentrated mostly
on planar covers and Negami's conjecture.
However, a surprising recent result has proved that Fellows' conjecture
is false (while Negami's one remains open).
\medskip\noindent{\bf Theorem (Rieck and Yamashita, 2008)}.
The graphs $K_{4,5}-4e$ and $K_{1,2,2,2}$ do have finite planar
emulators.
\medskip
Subsequently to this result, Chimani and Hlin\v{e}n\'y have constructed
planar emulators for another graphs which are known not to have
finite planar covers.
In view of this recent development, it appears desirable to study
the ``minimal differences'' between the classes of graphs having finite
planar emulators and planar covers.
We consider particularly interesting the questions whether the graph
$K_7-C_4$ has a finite planar emulator, and whether
there is an {infinite} nontrivial family of {\em non-projective} graphs
having finite planar emulators.
Robert Jajcay:
Notes
on balanced regular covers of regular Cayley maps
We only consider orientable embeddings, and
orientation preserving automorphisms of maps. Hence, a {\em regular map}
is sometimes called a {\em rotary map} by other authors. It is a map
whose group of orientation preserving automorphisms acts regularly on
the oriented edges, {\em arcs}, of the map. Recently, Cai Heng Li proved
the following:
Theorem. Let ${\cal M}$ be a regular map. Then
there is a normal cover $\tilde{\cal M}$ of ${\cal M}$ which is a
balanced regular Cayley map.
We call the balanced map
generated by non-involutions {\em balanced of Type I}, and the balanced
map generated by an orbit of involutions {\em balanced of Type II}. We
note that the balanced map constructed by Li is of Type II. In our talk,
we investigate Li's construction in the special case when the underlying
map ${\cal M}$ is a regular Cayley map $ CM(G,X,p) $. In this case, the
structure of the automorphism group of the map is well understood, and
is a product of the underlying group and a skew-morphism of the Cayley
map. We take advantage of this description and further refine the
results of Li. This is joint work with Shaofei Du. The first author is
supported in part by the project APVV-0111-07.
Stanislav Jendroľ:
Facial
strong parity vertex colouring of plane graphs
We consider vertex colourings of simple
$2$-connected plane graphs $G$. A vertex colouring is a strong parity
vertex colouring of $G$ if for each face $\alpha$ and each colour $c$,
no vertex or an odd number of vertices incident with $\alpha$ are
coloured with $c$. The minimum number of colours used in such a
colouring of $G$ is denoted by $\chi_s(G)$. In our talk we will provide
several upper bounds of the form $\chi_s (G) \leq K$ for some families
of graphs $G$, giving evidence to the conjecture that this parameter can
be bounded by a constant in general.
Gareth Aneurin Jones:
Classification
and Galois conjugacy of Hamming maps
I will show that for each $d\geq 1$ the
$d$-dimensional Hamming graph $H(d,q)$ has an orientably regular surface
embedding if and only if $q$ is a prime power $p^e$. If $q>2$ then there
are up to isomorphism $\phi(q-1)/e$ such maps, all constructed as Cayley
maps for a $d$-dimensional vector space over the field $F_q$. (The
corresponding result for the hypercubes $Q_d=H(d,2)$ has been obtained
separately by a number of others, with a totally different
classification.) I will show that for each such pair $d, q$ the
corresponding Bely\u{\i} pairs are conjugate under the action of the
absolute Galois group ${\rm Gal}\,\overline{\bf Q}$, and I shall
describe their minimal field of definition.
Toby Kenney:
Equivalence
in terms of paths between inputs and outputs of a family of planar
graphs
A collection of equations arising from some
category-theoretic considerations turn out to be exactly the equations
which characterise when two directed planar graphs in a certain family
induce the same relation that relates an input vertex (one which is not
the target of any edge) to an output vertex (one which is not the source
of any edge) if there is a path between them. We explain how to show
that these equations do characterise this, and some interesting points
on the way.
Mikhail Klin:
A new family of antipodal distance regular covers
of complete graphs
We will begin from a brief overview of the main concepts,
paying special attention to a few well-known small examples
and discussing the theorem of A.E.Brouwer
about the pseudo-geometrical distance regular covers
of complete graphs.
This will be followed by a consideration
of Godsil-Hensel theory and a short survey of
known constructions.
Our own interest to antipodal DRGs was revived
when we succeeded to construct new examples
on 108 and 135 vertices in the course of experimentation
with the computer packages COCO and GAP.
As a by-product of our analysis
of these examples a new method
for the construction of antipodal covers was suggested.
Starting from every generalized Hadamard matrix of order $n$
over a group $G$ we construct
a skew-symmetric generalized Hadamard matrix of order $n^2$
over the same group.
This gives rise to infinite sequences of regular,
antipodal distance regular covers of complete graphs.
The Godsil-Hensel parameters of these covers
are $(n^{2^k}, |G|, \frac{n^{2^k}}{|G|})$.
One of the smallest examples comes
from the $6\times 6$ generalized Hadamard matrix over $C_3$.
The first member in the infinite series of DRGs
determined by this matrix has parameters $(36,3,12)$
and provides the new example on 108 vertices.
We will also discuss links of the new example on 135 vertices
with the generalized quadrangle $GQ(2,2)$ of order 2.
This is a joint work with Christian Pech.
Martin Knor:
Orientable
triangular embeddings of complete graphs and complete tripartite graphs
We prove that there are infinite families of
odd numbers $w$, such that there are at least $w^{w^2\big(a-o(1)\big)}$
nonisomorphic face 2-colourable triangulations by complete tripartite
graph $K_{w,w,w}$, where $a$ is a constant depending on the family. This
implies that there are infinite families of $z$, such that there are at
least $z^{z^2\big(c-o(1)\big)}$ nonisomorphic face 2-colourable
triangulations by $K_z$ on an orientable surface, $c$ being a constant.
The result is, up to the constant $c$, the best possible.
Istvan Kovacs:
On the enumeration of skew-morphisms of cyclic groups
In the talk we consider the problem of enumerating all skew-morphisms of finite
cyclic groups $Z_n$. Under certain restriction on the skew-morphisms,
this problem is equivalent to the enumeration of objects like regular
embeddings of the complete bipartite graph $K_{n,n}$ in orientable surfaces,
or regular Cayley maps over $Z_n$. In our approach we utilize the Schur-rings over
$Z_n$ which are induced by the skew-morphisms. For certain orders $n$, the induced Schur-rings
are determined, and formulas are derived for the total number of skew-morphisms.
This is a joint work with R. Nedela.
Klavdija Kutnar:
Half-arc-transitive graphs of order $4p$ and accompanying combinatorial structures
The study of half-arc-transitive graphs has been the focus of
attention for many years.
A reasonable characterization of the entire class of these graphs is
presently beyond
our reach, pointing the research to certain subclasses satisfying
additional constrains,
such as for example having specific orders or valencies.
It is known that there is no half-arc-transitive graph of order $p$
and $2p$, where $p$ is
a prime. Furthermore, Alspach and Xu (J. Algebraic Combin, 1994)
classified half-arc-transitive
graphs of order $3p$, in particular all such graphs are metacirculants.
Surprisingly the situation for half-arc-transitive graphs of order
$4p$ is much more
complex with existence of a "sporadic family" of such graphs which
are not metacirculants.
In this talk we will present the construction of this family of graphs
and discuss
the current situation with regards to a possible complete classification of
half-arc-transitive graphs of order $4p$.
Boštjan Kuzman:
On tetravalent bicirculants
A bicirculant is a graph that admits an automorphism with exactly two
orbits of equal size. Some recent results regarding the classification
of all tetravalent edge-transitive bicirculants will be presented.
Joint work with S. Wilson, I. Kovacs and A. Malnič.
Young Soo Kwon:
Classification of orientably regular embeddings of folded $n$-cube $FH(n)$
The folded $n$-cube $FH(n)$ is the graph of order $2^n$ whose vertices can be labelled as the
$n$-length sequences of 0's and 1's, two vertices being adjacent whenever their labels differs in just one digit
or all digits. Or equivalently, $FH(n)$ is a quotient graph of $(n+1)$-cubes $Q_{n+1}$ by antipodal relation. It
is known that the automorphism group of the folded $n$-cube $FH(n)$ is isomorphic to $\mathbb{Z}_2^n \rtimes
S_{n+1}$ which is isomorphic to the quotient group $Aut(Q_{n+1}) / \langle e_0 +e_1 + \cdots + e_n \rangle$. In
this talk, we will consider classification of orientably regular embeddings of folded $n$-cube $FH(n)$ on the
basis of classification of orientably regular embeddings of $(n+1)$-cube $Q_{n+1}$.
Serge Lawrencenko:
New
regular 2-dimensional polyhedra
Coxeter's paradigm suggests that we should
geometrically realize in (Euclidean) space not only the abstract
(combinatorial or topological) object in question but also its
automorphims as symmetries of its geometric model in that space. In this
research the abstract object is an abstract 2-complex $K$ homeomorphic
to a 2-dimensional surface which corresponds to a topological map on
that surface. Polyhedral realization of the automorphism groups of
regular maps on 2-dimensional surfaces in high dimensions will make a
good contribution to Coxeter's paradigm.
Let $P$ be a polyhedron
realizing $K$ in $n$-space. The full symmetry group ${\rm Sym}\,(P)$ is
the set of all Euclidean isometries of $n$-space that leave $P$
invariant. The automorphisms of $K$ not realized geometrically are
called {\em hidden symmetries} of $P$. By the {\em abstract toroidal
hexadecahedron}, ATH, we mean the triangulation of the torus with the
graph $K_{2,2,2,2}$. \
Theorem There exists a regular toroidal
hexadecahedron, RTH, which is a geometric realization of ATH in 4-space.
Its regularity properties are as follows:
- All faces of RTH are
geometrically isometric equilateral triangles.
- RTH has no hidden
symmetries.
- ${\rm Sym}\,(RTH)$ is vertex-transitive.
The Theorem suggests a general definition of a regular 2-dimensional
polyhedron. If we allow 2-dimensional polyhedra in higher dimensions,
there may be found many more new regular 2-dimensional polyhedra. \\
Lemma. Each triangulation $T$ of the 2-dimensional orientable
closed surface of genus $(n-3)(n-4)/12$ with the complete graph $K_n$
($n \equiv 0$, 3, 4, or 7 modulo 12) can be geometrically realized as a
2-dimensional polyhedron $P=P(T)$ in $n$-space with all faces
represented by geometrically isometric equilateral triangles.
Are there any automorphisms of $T$ that are not realized
as symmetries of $P$?
Cai-Heng Li:
Basic
regular maps
A regular map is called basic if it has no
non-trivial normal quotient; equivalently, if its automorphism group
acts on the vertex set quasiprimitively. Then each regular map is a
normal multi-cover of a basic regular map. In this talk, I will describe
the characterisation of basic regular maps, obtained jointly with Jozef
Siran. Then I will present a characterisation of regular maps with odd
number of vertices.
Valery Liskovets:
Enumeration
of vertex-valency restricted planar maps
Known enumeration results for rooted planar
maps with diverse restrictions on valencies of vertices are first
surveyed in short. We discuss various types of valency restrictions. In
general, as is well known, eulerian maps are well tractable
enumeratively in many interesting particular cases, unlike maps with
odd-valent vertices. We concentrate mainly on the enumeration of {\it
non-eulerian} planar maps of two types: rooted {\it unicursal} maps
(i.e. ones with exactly 2 odd-valent vertices) and {\it unrooted
regular} maps of odd valency. Some open questions are posed, and some
recent results are considered.
Martin Mačaj:
Regular
$t$-balanced Cayley maps from cyclic and Abelian groups
We use known algebraic characterizations of
$t$-automorphisms and $\mathbb Z_2$ extenstions to define a "direct
product" of regular $t$-balanced Cayley maps. We also present some
decomposition results for regular $t$-balanced Cayley maps from cyclic
and Abelian groups.
Tomáš Madaras:
On
local properties of 1-planar graphs with specified minimum degree and
girth
A graph is called {\em 1-planar} if there
exists a drawing $D(G)$ of $G$ in the plane such that each edge of
$D(G)$ contains at most one crossing point. We present selected results
on local structure of 1-planar graphs with given minimum degree and
girth. In particular, we show that each 1-planar graph of minimum degree
7 contains a pair of adjacent 7-vertices, and a copy of $K_4$, $C_5$ and
two other small graphs with vertices of small degree; further, we show
that each 1-planar graph of minimum degree at least 5 and girth 4
contains a 5-vertex adjacent to an $\leq 6$-vertex, and a light copy of
$C_4$ and $K_{1,4}$.
Aleksander Malnič:
Semiregular subgroups and blocks of imprimitivity in transitive groups
Let $\Gamma$ be a (generalized) orbital (di)graph associated
with a transitive permutation group $G$ acting on a finite set $X$.
If $G$ contains an abelian semiregular subgroup, then the spectral
properties of $\Gamma$ can be studied in terms of complex irreducible characters
of $H$ and the spectral properties of the quotient digraph $\Gamma/H$.
The results and techniques developed here can be used in several ways.
One is
finding specific blocks of imprimitivity of $G$, namely those arising from the kernel
of the representation of $G$ on the eigenspaces of $\Gamma$; quasiprimitivity of actions
can be studied along these lines by considering all
(generalized) orbital digraphs.
Classifying certain families of transitive graphs arising as regular covers
(without using the classification of finite simple groups) is another.
For instance, by this approach one can classify arc-transitive abelian bi-Cayley graphs with one
matching; in particular, there is a short proof of an old theorem of Frucht, Graver and Watkins
who classified arc-transitive generalized Petersen graphs by purely combinatorial methods.
Joint work with Istv\'{a}n Kov\'{a}cs, Dragan Maru\v si\v c, and \v Stefko Miklavi\v c.
Dragan Marušič:
Looking back and ahead: three open problems in vertex-transitive graphs
We will give a short overview and discuss possible future directions
with regards to the following long standing open problems:
(i) existence of semiregular automorphisms in vertex-transitive graphs;
(ii) existence of Hamilton cycles in Cayley graphs; and
(iii) existence of strongly regular bicirculants and their relation,
in particular,
to primitive groups of degree twice an odd prime.
Alexander Mednykh:
Enumeration
of maps and coverings with given propeties
In this lecture we give a new method for
counting maps on Riemann surfaces and coverings of manifolds with
prescribed properties. In particular we describe how to count
reflexible, self-dual and Petri-dual maps and coverings.
Misha Muzychuk:
On
1-regular dihedrants
A dihedrant is a Cayley graph ${\rm
Cay}(D_{2n},S)$ over a dihedral group. If $G\leq {\rm Aut}({\rm
Cay}(D_{2n},S))$ acts regularly on the set of arcs of ${\rm
Cay}(S,D_{2n})$, then ${\rm Cay}(D_n,S)$ is called $G$-1-regular
dihedrant. In our talk we will present recent results about
$G$-1-regular dihedrants. Among them the classification of $G$-1-regular
dihedrants with trivial kernel. This is joint work with I.Kovacs and
D.Maru{\u s}i{\u c}
Roman Nedela:
Schur
rings and regular embeddings of graphs
Daniel Pellicer:
Regular
covers of the uniform tessellations of the plane
All polyhedra can be seen as quotients of
regular polyhedra. We shall discuss the presentation of the uniform
tessellations of the plane as quotients of regular polyhedra. In
particular, we shall discuss the minimal regular cover of the
tessellation 3.6.3.6 by hexagons and triangles.
Tomaž Pisanski:
Enumeration of Toroidal Polyhexes; Towards a Closed-Form Solution
A closed-form solution is presented to the enumeration problem of
toroidal polyhexes and its validity is proved. It is shown that
the question of under what conditions
toroidal polyhexes
are considered isomorphic may be answered in more than one
legitimate way. This explains why some numbers computed in the past do
not agree with each other.
This is a joint work with Edward Kirby and Roger Mallion.
Invaluable contributions from Paul Pollak are gratefully acknowledged.
Ilya Ponomarenko:
On
the automorphism group of a circulant graph
A polynomial-time algorithm for finding the
automorphism group of a circulant graph is constructed. The correctness
of the algorithm is based on a generalization of the Burnside-Schur
theorem (on permutation groups having a regular cyclic subgroup) in the
class of the automorphism groups of circulants.
Cristina Sarti:
Dessins
associated with Projective Spaces and Frobenius Compatibility
Embeddings of bipartite graphs in Riemann
surfaces result in dessin d'enfants, determining in a unique way the
conformal and algebraic structure of the curve. In this talk we will
present a possible way to construct dessins d'enfants, starting from
projective spaces over finite fields. The construction relies on the
existence of difference sets describing the incidence pattern of points
and hyperplanes belonging to projective spaces. We will see that, under
some conditions, we may order the elements of the difference sets in a
way compatible with Frobenius automorphisms of the finite field
(Frobenius compatibility). Using difference sets with their elements
ordered in such a way, we construct dessins with 'nice' properties such
as a larger automorphism group.
Brigitte Servatius:
k-plane
matroids and flattening conjectures
Recent explorations of matroids with counting
etc. have explored variations of the 'molecular conjecture': that
certain types of geometric specialization do not reduce the generic rank
of a structure. The core conjecture by Tay and Whiteley, for which a
proof was just announced by Katoh and Tanigawa says that for a
generically rigid (independent) body and hinge structure in 3-space with
two bodies at each hinge, making all hinges of a body concurrent (polar:
all coplanar) will produce a generically rigid (independent) body and
hinge molecular (polar plate) framework. Here we explore k-plane
matroids in connection with various related conjectures.
Ondrej uch:
Groups
acting on Klein bottle
In this talk we describe how finite discrete groups acting on Klein bottle arise. This subject
was
previously considered by Babai in the context of proof of Babai's conjecture. Unlike Babai, we will consider
group actions on the universal cover of Klein bottle. We will also discuss Babai's families of vertex transitive
maps on Klein bottle and show that they are all in fact Cayley maps.
Jozef iráň:
Non-orientable regular maps of a given type
It is well known that for any $m$ and $n$ such that $1/m+1/n\le 1/2$
there exist infinitely many finite, orientable, regular maps (reflexible or
not) of type $\{ m,n\}$, that is, of valence $n$ and face length $m$. We will
discuss ways to extend this result to non-orientable regular maps.
Robin Thomas:
Three-coloring
triangle-free graphs on surfaces
For every surface $S$ we describe a linear-time
algorithm that computes the chromatic number of an input triangle-free
graph drawn in $S$. The new contribution here is deciding whether $G$ is
$3$-colorable, and has three main ingredients. The first is a coloring
extension theorem that makes use of disjoint paths in order to construct
a coloring. The notion of ``winding number" of a $3$-coloring plays an
important role. The second ingredient is a theorem bounding the number
and sizes of faces of size at least five in $4$-critical triangle-free
graphs on a fixed surface, a generalization of a theorem of Thomassen.
Third, we use the notion of bounded expansion of Nesetril and Ossona de
Mendez to implement the algorithm to run in linear time. This is joint
work with Zdenek Dvorak and Daniel Kral.
Thomas Tucker:
Gapfilling for Symmetric Genus
Given a finite group $A$, the {\em symmetric genus} $\sigma(A)$ (respectively, {\em strong
symmetric genus} $\sigma^0(A)$) is the minimum $g$ such that $A$ acts on a surface of genus $g$ (respectively,
acts preserving orientation). May and Zimmerman showed that for every $g$, there is a group $A$ with
$\sigma^0(A)=g$; that is, there are no gaps for $\sigma^0$. They used the family $D_m\times Z_n$, but these
groups all act on the torus (not preserving orientation) so cannot be used to fill gaps for $\sigma$. It is
shown that the only possible gaps for $\sigma$ occur for $g\equiv 8,14$ mod $18$ such that the prime
factorization of $g-1$ contains some prime $p \equiv 5$ mod $6$ with an odd exponent. The first such possible
gap is $g=86$. Five different families of groups are used, two related to the classification of regular maps of
genus $p+1$ where $p$ is prime. This is joint work with Marston Conder.
Timothy Robert Walsh:
Structure
and Enumeration of Two-Connected Graphs with Presribed Three-Connected
Components
This is joint work with Andrei Gagarin, Gilbert
Labelle and the late Pierre Leroux. We adapt the classical decomposition
of 2-connected multigraphs into 3-connected components to simple graphs
(no loops or multiple edges) so that the 3-connected components are
either 3-connected graphs or polygons. We also modify the classical
formula for the cycle index of a composite graph, each of whose
component graphs is rooted at a vertex and attached by its root to a
vertex of the core graph, to a composite graph, each of whose component
graphs is rooted at two vertices and replaces an edge of the core graph.
We thus count labeled and unlabeled 2-connected graphs all of whose
3-connected components that are 3-connected graphs belong to a given
class of such graphs. If this class is empty, we obtain series-parallel
graphs. Otherwise we use the 3-connected planar graphs generated by the
program Plantri to count various isomorphisms classes of 2-connected
graphs including planar graphs and non-planar toroidal K(3,3)-free
graphs, with or without vertices of degree 2.
Stephen Edwin Wilson:
LR
Structures from Cycle Structures
LR structures are cycle decompositions of
tetravalent graphs which are characterized by having local "swappers",
symmetries which leave one cycle at a vertex pointwise fixed while
reversing the other cycle there. Suitable LR structures correspond
one-to-one to semisymmetric tetravalent graphs of girth 4. In this talk,
we describe how a symmetric cycle decomposition gives rise to two LR
structures with twice as many vertices. We show how this construction
gives rise to the two semisymmetric graphs with smallest symmetry groups
(80 elements each). (Joint work with Primo\v z Poto\v cnik)
Ute Wolf:
The
action of the mapping class group on the pants complex of a surface
For any compact surface $S = \Sigma_{g,b}$ of
genus $g$ with $b$ boundary components, there is a cell complex attached
to $S$, namely the {\em pants complex}. The mapping class group
$\operatorname{Mod}(S)$ of $S$ acts cocompactly on this complex. In my talk I will
analyze this action, calculating stabilizers and orbits, and I will use
these data to find a presentation of $\operatorname{Mod}(S)$.
Jürgen Wolfart:
Multiple
Uniform Dessins and Quaternion Algebras
It is well known that {\em dessins d'enfants},
i.e. maps or hypermaps on orientable compact surfaces, determine
uniquely a complex or conformal structure on these surfaces, even an
algebraic structure as an algebraic curve defined over a number field.
On the other hand, infinitely many different dessins belong to the same
Riemann surface. How are they related? \\ We are far from a general
answer to this question. But it becomes easier if we restrict the
question to {\em uniform} dessins, i.e. where all valencies of faces
(resp. white vertices resp. black vertices) are the same. The talk
reports about a common project with Ernesto Girondo and David Torres
(UAM Madrid) leading to a better understanding why and which Riemann
surfaces may have several non--equivalent uniform dessins of the same
type and how many of them. The crucial tools are hyperbolic geometry,
Fuchsian groups, and the arithmetic of quaternion algebras.