Graph Embeddings and Maps on Surfaces

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

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.

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.

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.

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

1. J. Czap, S. Jendroľ, F. Kardoš and J. Miškuf, Looseness of plane graphs (http://umv.science.upjs.sk/preprints/dokumenty/A3-2009.pdf)

In this talk, I give a classification of (orientable and nonorientable) regular embeddings of graphs of order $pq$, where $p$ and $q$ are primes.

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.

 

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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$.

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č.

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}$.

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:

1. All faces of RTH are geometrically isometric equilateral triangles.
2. RTH has no hidden symmetries.
3. ${\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$?

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.

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.

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.

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}$.

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.

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.

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.

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}

 

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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)

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)$.

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.