A skew morphism of a finite group $G$ is an element $\varphi$ of $\textrm{Sym}(G)$ preserving the identity element of $G$ and having the property that for each $a\in G$ there exists a non-negative integer $i_a$ such that $\varphi(ab)=\varphi(a)\varphi^{i_a}(b)$ for all $b\in G$. Skew morphisms play an important role in the study of regular Cayley maps. The problem of classifying skew morphisms for all finite cyclic groups is notoriously hard, with no such classification available to date. In this talk we show that if a skew morphism $\varphi$ of $\mathbb{Z}_n$ is not an automorphism of $\mathbb{Z}_n$, then it is uniquely determined by an element $h$ of $\mathbb{Z}_n$, a skew morphism $\alpha$ of $\mathbb{Z}_a$ where $a<n$, and a skew morphism $\beta$ of $\mathbb{Z}_b$ where either $b<n$, or $b=n$ and $\textrm{ord}(\beta)<\textrm{ord}(\varphi)$. Conversely, we also list necessary and sufficient conditions for a triple $(h,\alpha,\beta)$ to define a skew morphism of a given cyclic group. In particular, this gives a recursive characterisation of skew morphisms of finite cyclic groups.
The author acknowledges funding from the EU NextGenerationEU through the Recovery and Resilience Plan for Slovakia under the project No. 09I03-03-V04-00272.
The Nondeterministic Constraint Logic (NCL) framework (Hearn & Demaine; Theoret. Comput. Sci. 343(1-2); 2005) allows us to express any problem in PSPACE as the task of moving between fully or partially specified orientations of a simple cubic polyhedral graph having integral edge weights (of $1$ or $2$) and bounded bandwidth - i.e., a bounded gap between adjacent vertices in some linear ordering of the graph's vertex set - by way of sequentially reversing the orientations of directed edges under the constraint that all vertices have weighted in-degree at least $2$. Owing to its simple and intuitive nature, the NCL model has since become a cornerstone of PSPACE-completeness reductions for reconfiguration problems in graph theory, computational geometry, and formal models of puzzles and games.
In this talk, we discuss how the graph bandwidth constraint allowed for by the NCL model yields a natural encoding of NCL reachability problems as Wang tiling tasks for finite rectangular or toroidal areas. Concerning a specific application of this correspondence, we also show that the existence of linear time tiling algorithms for sequentially permissive (or ``brick'') Wang tile sets (Derouet-Jourdan, Mizoguchi, & Salvati; Mathematical Progress in Expressive Image Synthesis III. Mathematics for Industry 24; 2016), originally developed for modeling wall patterns, implies novel tractability results for the perfect matching reconfiguration problem (Bonamy et. al.; Proc. 44th MFCS; 2019) of finding restricted walks on the $1$-skeleton of the perfect matching polytope for a graph.
A nut graph is a simple graph for which the adjacency matrix has a single zero eigenvalue such that all non-zero kernel eigenvectors have no zero entry (i.e. are full). We show that every finite group can be represented as the group of automorphisms of infinitely many nut graphs. Moreover, such nut graphs exist even within the class of regular graphs.
This is joint work with Patrick W. Fowler.
In this talk I'll describe some recent discoveries (since 2022) about regular maps of small genus (in joint work with Primož Potočnik) and about finite quotients of triangle groups (in joint work with PhD student Darius Young).
As is well known, (ordinary) triangle groups of the form \(\Delta^+(k,l,m) = \langle\, x,y,z\ |\ x^k = y^l = z^m = xyz = 1\,\rangle\) (Equation) play an important role in the study of large automorphism groups of algebraic curves and compact Riemann surfaces, and of regular maps on orientable and non-orientable surfaces.
Much of the early part of the study of these things (dating back over 100 years) considered only small quotients of triangle groups, and subsequent work concentrated on finite simple quotients. But surprisingly, the recent determination of all orientably-regular maps of genus up to 1501 (by MC & PP) has shown that finite simple groups and finite insoluble groups account respectively for less than 0.1% and less than 7% of the associated quotients of ordinary triangle groups, while finite soluble quotients account for over 93%. Some other information is also interesting, such as the increasing proportion of orientably-regular maps of genus $2$ to given $g$ that are chiral. The long-standing question of what happens asymptotically (as $g \to \infty$) remains open.
Very little attention has been paid to soluble quotients, and as one step towards correcting this, a new theorem (by MC & DY, using a 1970 theorem by David Singerman) shows how every non-perfect hyperbolic ordinary triangle group has a smooth finite soluble quotient with derived length $c$ for some $c \le 3$, and has infinitely many such quotients with derived length $d$ for every $d > c$.
Also I will report on some work by Darius in 2024 in which he proved that the natural density (in the positive integers) of the set of orders of finite quotients of a triangle group $\Delta^+(k,l,m)$ is zero for every triple $(k,l,m)$. This work answers a question raised by Tom Tucker (who showed it holds when one of $k,l,m$ is coprime to the other two), and also completes and considerably extends an initial investigation by Larsen (2001), but avoids resorting to Larsen's use of the classification of finite simple groups.
Incidentally, it has also led to unexpected discoveries (by MC & Gabriel Verret & DY) about the densities of finite quotients of free products of two cyclic groups, and hence to the densities of orders of automorphism groups of regular maps of type $\{m,k\}$ for fixed $k$ and variable $q$ (or vice versa), and the densities of orders of finite locally-transitive graphs, and surprisingly, also about possibilities for the density of orders of finite quotients of a given finitely-generated group.
The mix of two maniplexes is the minimal maniplex that covers both. This construction has many important applications, such as finding the smallest regular cover of a maniplex. If one of the maniplexes is an abstract polytope, a natural question to ask is whether the mix is also a polytope. We describe here a general criterion for the polytopality of the mix which generalizes several previously-known polytopality criteria.
This is a joint work with Isabel Hubard.
Negami's conjecture states that a graph $X$ admits a planar cover if and only if $X$ is projective. In this talk, I will discuss a relaxation of this problem, where we replace the planar cover of $X$ by the more general notion of a weighted harmonic homomorphism from a planar graph to $X$. Remarkably, the existence of a harmonic homomorphism of certain degree from a planar graph to $X$ is equivalent to the non-existence of certain leaking non-abelian flows in $X$. The latter problem can be formulated and studied as a word problem in a finitely presented group associated to $X$. This gives us a new algebraic tool for tackling Negami's conjecture. Although there are known counterexamples to ``Negami's conjecture with harmonic homomorphisms'', we are nevertheless able to use our techniques to prove new results about the remaining open cases of Negami's conjecture. In particular, we show that $K_{1,2,2,2}$ has no $k$-fold planar cover when $k \not\equiv 0 \pmod 6$.
This talk is based on joint work with David E. Roberson and on related work of Slofstra and Zhang.
Collections of small mathematical objects are often used in the formation and testing of conjectures, and can also provide counterexamples to open problems. In general, the enumeration of discrete objects is computationally hard. However, additional structure and symmetries can aid in the implementation of common isomorph-free exhaustive generation algorithms. For many highly symmetrical discrete objects, their description as a finite group together with a generating set with certain properties is often useful computationally and theoretically (e.g., regular maps, maniplexes and Cayley graphs).
In this talk, we will see the application of an orderly generation algorithm to the enumeration of minimal generating sets of a given group. Simple group-theoretical observations will be used to improve on the basic algorithm, extending previous enumerations to groups of much larger order. This approach has been used to generate a complete list of minimal Cayley graphs on up to 511 vertices. I will also briefly mention applications to other highly symmetrical discrete objects, and the databases and software we are developing to make the resulting collections of objects available to a wider audience.
Recall that given a graph $\Gamma$, the girth of $\Gamma$ is the length of a shortest cycle in $\Gamma$. In graphs of finite girth, each vertex $v$ of $\Gamma$ can be associated with a non-decreasing sequence of integers, one integer for each edge incident with $v$, representing the number of girth cycles containing that edge (possibly $0$). If the sequences associated with the vertices of $\Gamma$ are all identical (and so $\Gamma$ is regular), we say that $\Gamma$ is girth-regular, and the shared sequence is said to be the signature of $\Gamma$. Note that all vertex-transitive graphs are necessarily girth-regular. The concept of girth-regularity was introduced by Potočnik and Vidali in 2019, who also classified cubic girth-regular graphs of girth at most $5$ and cubic vertex-transitive graphs of girth $6$ with respect to their signatures. In our work, we extend the latter to a classification of all cubic girth-regular graphs of girth $6$. We note that for most of attainable signatures, the only girth-regular graphs attaining given signature are the skeletons of maps of type $\{6,3\}$ on the torus or the Klein bottle.
This is a joint work with Robert Jajcay, Maruša Lekse and Primož Potočnik, and it is supported by grants VEGA 1/0437/23 and UK/1398/2025.
The notion of a directed strongly regular graph was introduced by 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,\lambda,\mu)$ is a regular directed graph on $n$ vertices with degree $k$, such that every vertex is incident with $t$ undirected edges, and the number of paths of length 2 directed from a vertex $u$ to another vertex $v$ is $\lambda$, if there is an arc from $u$ to $v$, and $\mu$ otherwise. Similarly as in the undirected case, the feasible parameter sets can behave very differently making the efforts for creating catalogues of such (di)graphs difficult.
In the talk we report about a systematic search for symmetric directed strongly regular graphs of small order.
This research was supported from the APVV Research grants 22-0005, 23-0076 and VEGA Research grants 1/0069/23 and 1/0011/25.
Since the classical classification of orientably regular embeddings of complete graphs due to James and Jones preceded the introduction of skew-morphisms, their role in these embeddings has never been fully investigated. In our talk, we plan to revisit these classical results from the point of view of skew-morphisms and to expand this approach to two closely related problems: orientably regular embeddings of complete graphs with multiple edges and half-regular orientable embeddings of complete graphs. The first of these problems has been recently addressed by Gyürki, Pavlíková and Širáň who have been able to classify orientably regular embeddings of complete graphs with multiple edges; yet without the use of skew-morphisms again. We propose to remedy this omission by considering skew-morphisms with extended power functions introduced by Jajcay and Hu. On the other hand, the study of half-regular Cayley maps initiated by Jajcay and Nedela relies on the use of skew-morphisms from its very beginning. Our aim is to apply the skew-morphism based theory to half-regular orientable embeddings of complete graphs with or without multiple edges, and to eventually obtain a classification of orientable half-regular embeddings of complete graphs similar to those of James and Jones and Gyürki, Pavlíková and Širáň.
This is a joint project with Stephen Ikechukwu Ifeanyi.
Graph constructions based on groups have proved invaluable in the search for graphs with given properties, especially in the degree-girth problem, aiming to find the smallest $k$-regular graph of girth $g$. One prominent example is lifting constructions, introduced by Gross and Tucker in 1987, which can be regarded as a generalisation of the well-known Cayley graphs. However, the introduction of $G$-graphs by Bretto and Faisant in 2005, as a new group-based construction that produces highly regular graphs by leveraging group coset structures, has raised a natural question about the relationship between these two approaches. In this talk, we compare the two constructions and derive a sufficient condition under which a $G$-graph can be obtained as a lift of a dipole. Using this result, we further generalise constructions of two families of near-cages of girth $6$ and $8$ to broader families.
This is a joint work with Štefan Gyürki and Jozef Širáň, and it is supported from the APVV Research grants 22-0005, 23-0076 and VEGA Research grants 1/0069/23 and 1/0011/25.
We will discuss the list of representatives of equivalence classes of group actions on surfaces of genera $g$, $2\leq g\leq 9$. I will explain some important examples from the list in details. I will also compare our classification with the known classifications of group actions on surfaces of genera $\leq 5$ and with Breuer's classification of group actions (derived using character theory). Note that any map $M$ of genus $g$ with $\operatorname{Aut}^+M\cong G$ can be viewed as a model of an action of $G$ on a surface $S_g$ with genus $g$. In particular, every action of $G$ on $S_g$ can be obtained by the construction of a Cayley map, and actions with triangular signatures are determined by regular hypermaps. In general, it is difficult to decide whether two Cayley maps determine actions that are topologically equivalent. On the other hand, the topological equivalence of groups with triangular signatures corresponds to the equivalence on orientably regular hyperemaps given by hypermap isomorphisms and dualities. This gives an evidence that the approach taken by Conder and others to classify orientably regular hypermaps is the right one.
This talk is based on a joint work with R. Nedela and M. Skyvová, for details see Journal of Pure and Applied Algebra 228(2024) 107578.
Let $\Gamma$ be a graph, and let $v$ be a vertex and $e$ an edge of $\Gamma$. The signature of $e$ is the number of girth cycles that contain it, while the signature of $v$ is the tuple of the signatures of all edges incident to it (ordered by size). We say that $\Gamma$ is girth-regular if every vertex in the graph has the same signature. This concept was introduced by Potočnik and Vidali in 2019 as a generalization of edge-girth-regularity, and they later used it to classify cubic vertex-transitive graphs of girth at most $6$. In this talk, we present a similar classification of cubic vertex-transitive graphs of girth $7$ based on their signatures, along with some corollaries of this classification.
This is joint work with Primož Potočnik and Micael Toledo.
Recently G. Jones and M. Mačaj classified the orientably regular hypermaps $\mathcal{H}$ for which the automorphism group $G$ acts primitively and faithfully on the vertices. They showed that they are in one-to-one correspondence with generalised Paley dessins, in which the black vertices are the elements of a finite field $F_q$, and $G$ is a subgroup of the affine group $AG_1(q)$. They also proved necessary and sufficient conditions for these hypermaps to be chiral.
We use these conditions to investigate the balance between reality and chirality for such hypermaps. Since we are dealing with infinite sets of hypermaps, the method of sampling is significant, and various approaches are possible. They all indicate that chirality predominates, though by different amounts. This is a joint work with G. Jones.
By the Riemann-Hurwitz bound, there are just finitely many groups that act conformally on a closed orientable surface $S_g$ of genus $g\geq 2$. With each such action of a group $G$ on $S_g$, one can associate the fundamental group $\pi(O)$ of the quotient orbifold $O=S_g/G$. It is well-known that $\pi(O)$ is isomorphic to a Fuchsian group $F$ determined completely by orbifold's signature. The Riemann existence theorem reduces the problem of the existence of an action of $G$ on $S_g$ to a group-theoretical problem of deciding whether there is a smooth epimorphism mapping $F$ onto the group $G$. Using computer algebra systems such as Magma or GAP, together with the library of small groups, the generation of all finite group actions on a surface of fixed small genus $g\geq 2$ becomes almost a routine procedure. The difficult part is to determine the classes of these actions with respect to several natural equivalences. One of the most important equivalences is the topological one defined as follows. For an orientable surface $S$ denote by $Hom^+(S)$ the group of orientation-preserving homeomorphisms. Two actions of a group $G$, given by embeddings $\epsilon_i: G \to Hom^+(S_i)$, $i =1, 2$, on possibly different surfaces $S_1$, $S_2$ of the same genus, are topologically equivalent if there is an intertwining orientation preserving homeomorphism $h: S_1\to S_2$ and an automorphism $a\in Aut(G)$ such that $\epsilon_2(g)h =h\epsilon_1(a(g))$, for every $g\in G$. In my talk the following problem is considered.
Problem 1. For a fixed small integer $g>1$, derive the list of actions of finite groups on an orientable surface of genus $g$, distinguished up to topological equivalence.
LLoyd proved that the above problem reduces to a purely group theoretical problem of determining representatives of equivalence classes on the set of smooth epimorphisms from a Fuchsian group $F$ to $G$ defined as follows: two such epimorphisms $\nu_1$, $\nu_2$ are equivalent if and only if there are automorphisms $\alpha\in Aut(F)$ and $a\in G$ such that $\nu_2=a\nu_1\alpha$. To achieve this, one needs to investigate the action of the automorphism group of a Fuchsian group on the set smooth epimorphisms $F\to G$. In order to apply LLoyd's theorem, one needs to derive a finite generating set of $Aut(F)$, where each generator is defined as a transformation of the standard generating set of $F$. Employing known results on generation of $Out(F)$ for surface groups (McCool 1996) and for Fuchsian groups of planar signature (Zieshang 1966), we were able to derive complete lists of finite group actions of genus $g\leq 9$ distinguished up to the topological equivalence.
This talk is based on a joint work with J. Karabáš and M. Skyvová, for details see Journal of Pure and Applied Algebra 228(2024) 107578.
In 2012 A. Blokhuis and A.E. Brower defined a graph on the flags of a biplane and proved that the graph corresponding to the unique $(11,5,2)$ is defined by its spectrum. We will look at these graphs for other biplanes, other graphs on flags of designs (symmetric and non-symmetric), some of their properties, and what we can say so far about their spectra.
This is a joint work with Octavio Baltasar Zapata-Fonseca.
References
Datasets containing lists of mathematical objects of interest are a valuable research tool as they can suggest possible theorems and provide counterexamples to existing conjectures. In algebraic graph theory, such datasets have a long history, going back to the 1930s and early versions of the Foster census of cubic symmetric graphs. In the field of highly symmetrical maps, early efforts to compile datasets of various kinds were made by several renowned mathematicians, including Brahana, Coxeter, and most notably Steve Wilson. In the modern computer era, this work was taken significantly further by Marston Conder, whose lists of all regular and chiral maps up to a given genus have long served as an invaluable resource for the community.
In my talk, I will present some recent joint work with Marston Conder that takes these censuses to a new level. Specifically, I will describe a census of all regular (both orientable and non-orientable) and chiral maps of genus up to 1.501 (1.502 in the non-orientable case), or with no more than 3,000 edges (6,000 edges in the orientable case). I will explain the techniques that enabled us to extend the existing censuses and illustrate some recent applications.
A complex nowhere-zero $r$-flow on a graph $G$ is a flow using complex numbers whose Euclidean norm lies in the interval $[1,r-1]$. The complex flow number of a bridgeless graph $G$, denoted by $\phi_{\mathbb{C}}(G)$, is the minimum of the real numbers $r$ such that $G$ admits a complex nowhere-zero $r$-flow. Complex (and, more generally, multidimensional) flows comprise an interesting generalisation of the classical integer and circular flows. However, the exact computation of $\phi_{\mathbb{C}}$ seems to be a difficult task even for very small and symmetric graphs, including the Petersen graph.
In this talk, we present two lower bounds on the complex flow number of cubic graphs: one general depending on the odd girth, and another for the infinite family of Isaacs' flower snarks. The proofs of these lower bounds are based on a convenient geometric representation of a complex flow by a set of suitable triangles in the plane. This representation also uncovers interesting connections to duals of the considered graphs embedded to other surfaces.
This is joint work with Davide Mattiolo, Giuseppe Mazzuoccolo and Gloria Tabarelli. Funded by the EU NextGenerationEU through the Recovery and Resilience Plan for Slovakia under the project No. 09I03-03-V05-00012.
In the classification of tilings of a surface by certain prototiles, the first step is usually the determination of all the possible combinations of the angles at vertices. For example, this is the first step in Rao’s classification of convex pentagons that can tile the plane. We discuss how this can be done for tilings of the sphere by angle congruent pentagons, and compare our approach to Rao's. Then we apply the results to get the classifications of some families of tilings of the sphere by angle congruent pentagons.
This is a joint work with Robert Barish and Hoi Ping Luk, and is supported by NSFC/RGC Joint Research Scheme N_HKUST607/23.