Algebraic Graph Theory

International Webinar

Aim of the Webinar:

Our aim is to provide a forum for sharing results and collaboration among researchers within the area of Algebraic Graph Theory and related fields; regardless of their geographical location or traveling constraints.

We welcome (and solicit) presentations by all speakers interested in reaching out to the AGT community. Anyone wishing to present should write to one of the organizers. Survey presentations and broad range talks possibly opening new directions for research and collaboration are also of interest.

We very much encourage presentations by researchers at the beginning of their careers as well as by women and anyone seeking a friendly collaborative audience.

All the talks will take place over the Zoom platform on a bi-weekly basis (at least for the beginning). We plan to collect and post the presentations and record the sessions for later use. The presentations and the links for the recordings will permanently remain posted at this site.

Although we will accept presentations from speakers not willing to provide their presentation slides and/or not allowing recording their presentations, we hope that most speakers will choose to share and to contribute to a friendly, cooperative and productive atmosphere of our webinar.

Schedule of Presentations:


☛☛☛ May 24, 7pm CEST = 5pm UTC, Tomo Pisanski,
Grunbaum incidence calculus revisited

To watch and participate in Tomo's talk, click on the title.
Meeting ID: 925 4558 6220
Passcode: 117532

Abstract: Configurations became a hot topic of mathematical research already in the 19th century. Several prominent and lesser known mathematicians, such as Fano, Mobius, Kantor, Pappus, Desargues, Pasch, Miquel, Kummer, Klein, Grey, Martinetti, Steinitz, Levi, Menger, Reye, etc., are associated with particular configurations or with the general concepts concerning the study of configurations. Some of them stumbled upon configurations while pursuing research in other mathematical topics. For instance, the Desargues configuration appears as a byproduct of the Desargues theorem in projective geometry. Other mathematicians were interested in parameters for which configurations exist. At the turn of the millennium Branko Grunbaum became interested in the problem, for which values of n there exists a geometric (n_4) configuration. He reduced this problem to a small, finite number of open cases. Nowadays, only the case n = 23 remains open. In his work on this problem Grunbaum developed and used certain techniques that we may call compositions. Compositions form a fundamental tool in the synthetic approach to configurations. They constitute a class of operations that turn input parameters into a new configuration. There are primarily two such classes of operations, depending on the nature of parameters. In case of integer parameters, the so-called families of configurations are constructed, eg. cyclic and polycyclic configurations. On the other hand, the operations of Grunbaum incidence calculus are typical synthetic methods that compose large configurations from smaller ones.
In this talk we revisit the Grunbaum incidence calculus and its applications to the problem of existence of combinatorial, geometric and some other species of configurations. In particular, we indicate how we are using it in our own past research and in our current work in progress with several colleagues, mainly with Leah Berman and Gabor Gevay.

May 10, 7pm CEST = 5pm UTC, Alex Lubotzky,
Good locally testable codes

To view the recording of Alex's talk, click on the title. To see the slides, click here.

Abstract: An error-correcting code is locally testable (LTC) if there is a random tester that reads only a small number of bits of a given word and decides whether the word is in the code, or at least close to it. A long-standing problem asks if there exists such a code that also satisfies the golden standards of coding theory: constant rate and constant distance. Unlike the classical situation in coding theory, random codes are not LTC, so this problem is a challenge of a new kind. We construct such codes based on what we call (Ramanujan) Left/Right Cayley square complexes. These are 2-dimensional versions of the expander codes constructed by Sipser and Spielman (1996).
The main result and lecture will be self-contained. But we hope also to explain how the seminal work Howard Garland ( 1972) on the cohomology of quotients of the Bruhat-Tits buildings of p-adic Lie group has led to this construction (even though it is not used at the end).
Based on joint work with I. Dinur, S. Evra, R. Livne, and S. Mozes.

April 26, 7pm CEST = 5pm UTC, Grahame Erskine,
The cage problem for cubic graphs

To view the recording of Grahame's talk, click on the title. To see the slides, click here.

Abstract: The cage problem in extremal graph theory seeks to find the smallest possible d-regular graph of given girth g. As the girth g becomes large, the best constructions we have are asymptotically very far from the theoretical bound. Many of these constructions are algebraic in nature, being based on Cayley graphs or other graphs derived from groups; or on systems of equations defined over finite fields.
I will describe a recent construction for graphs of valency 3 which resulted in a number of new record smallest graphs. This method was originally based on 3-uniform hypergraphs, but it turns out (as is often the case in this problem) that our method is closely related to previous constructions based on groups. I will describe these connections and discuss the challenges remaining in the cage problem for cubic graphs.
This is joint work with James Tuite (Open University).

April 12, 7pm CEST = 5pm UTC, Alejandra Ramos Rivera,
Symmetric substructures in tetravalent edge-transitive bicirculant graphs

To view the recording of Alejandra's talk, click on the title. To see the slides, click here.

Abstract: In this talk we explore some interesting substructures of edge-transitive bicirculant tetravalent graphs: Consistent cycles, Cycle structures, Semitransitive Orientations and Rotary Maps.
For each edge-transitive bicirculant tetravalent graph, we will determine all such substructures. Additionally, we will illustrate how to obtain cubic vertex-transitive graphs from the cycle structures of these tetravalent graphs.
The results presented are joint work with Steve Wilson, Micael Toledo and Primoz Potocnik.

March 29, 7pm CEST = 5pm UTC, Misha Muzychuk,
Generalised dihedral CI-groups

To view the recording of Misha's talk, click on the title. To see the slides, click here.

Abstract: A finite group R is called a CI-group if two Cayley graphs over R are isomorphic iff they are isomorphic by an automorphism of R. It was known that a generalized dihedral group Dih(A) is a CI-group only if A is a direct product of elementary abelian groups of odd order. In my talk a new restriction on the structure of A will be presented, namely: if Dih(A) is a CI-group, then for every odd prime p the Sylow p-subgroup of A has order p, or 9.
This is joint work with Edward Dobson and Pablo Spiga.

March 15, 7pm CET = 6pm UTC, Jeroen Schillewaert,
Constructing highly regular expanders from hyperbolic Coxeter groups

To view the recording of Jeroen's talk, click on the title. To see the slides, click here.

Abstract: Given a string Coxeter system (W,S), we construct highly regular quotients of the 1-skeleton of its universal polytope P, which form an infinite family of expander graphs when (W,S) is indefinite and P has finite vertex links. The regularity of the graphs in this family depends on the Coxeter diagram of (W,S). The expansion stems from superapproximation applied to (W,S). This construction is also extended to cover Wythoffian polytopes. As a direct application, we obtain several notable families of expander graphs with high levels of regularity, answering in particular a question posed by Chapman, Linial and Peled positively.
The presented results are joint work with Marston Conder, Alex Lubotzky and Francois Thilmany.

March 1, 7pm CET = 6pm UTC, Maria Elisa Fernandes,
Faithful transitive permutation representations of regular polytopes

To view the recording of Maria Elisa's talk, click on the title. To see the slides, click here.

Abstract: Every finite group can be represented by a group of permutations acting faithfully on a set of points.The cardinality of this set, which is the degree, is not uniquely determined. The problem we have in mind is:
What are the possible degrees of a faithful transitive permutation representation of a given finite group?
We started by considering groups of automorphisms of the toroidal regular maps, then toroidal hypermaps and after, we considered the groups of automorphisms of the known finite universal locally toroidal regular polytopes of type [4,4,4].
In this talk I will give the results we have achieved so far, which were not always as expected. This can soon be found in Claudio Piedade's PhD thesis.

February 15, 7pm CET = 6pm UTC, Gareth A. Jones,
Maps and maximal subgroups

To view the recording of Gareth's talk, click on the title. To see the slides, click here.

Abstract: In 1933 Bernhard Neumann used permutations to construct uncountably many conjugacy classes of subgroups of ${\rm SL}_2(\mathbb Z)$ which act regularly on the primitive elements of $\mathbb Z^2$. Their images in the modular group $\Gamma={\rm PSL}_2(\mathbb Z)\cong {\rm C}_3*{\rm C}_2$ are maximal nonparabolic subgroups, i.e.~maximal with respect to containing no elements with a single fixed point in ${\mathbb P}^1({\mathbb Q})$. Further examples of such subgroups were later found by Magnus, Tretkoff, and Brenner and Lyndon.
I shall use planar maps to strengthen and extend their results by constructing uncountably many conjugacy classes of subgroups of $\Gamma$ which are maximal (as subgroups of $\Gamma$) {\sl and\/} nonparabolic. For example, all except one of Neumann's classes of subgroups are maximal. These subgroups all act regularly on the Farey graph, so this is a Cayley graph for all of them.
A similar construction gives, for all $p\ge 3$, $q\ge 2$, uncountably many conjugacy classes of subgroups of the triangle group $\Delta(p,q,\infty)\cong {\rm C}_p*{\rm C}_q$ which are maximal and nonparabolic. As a consequence, given any integer $p\ge 3$, every countable group is isomorphic to the automorphism group of uncountably many non-isomorphic $p$-valent maps on surfaces. I shall give evidence to support conjectures that every non-elementary Fuchsian group has uncountably many conjugacy classes of maximal subgroups, and hence that a similar realisation result holds for hypermaps of any given hyperbolic type.

February 1, 7pm CET = 6pm UTC, Roman Nedela,
On Equivalence of Discrete Groups

To view the recording of Roman's talk, click on the title. To see the slides, click here.

Abstract: Let S be an orientable surface of genus g. Denote by Hom+(S) its group of orientation-preserving homeomorphisms. We say that a finite group G acts on S if there is monomorphism e: G -> Hom+(S). Every action may be constructed by means of a pair of Fuchsian groups K < Gamma < PSL(2,R) acting discontinuosly on the upper half plane U and an epimorphism f: Gamma -> G with kernel K, where K is a surface group. Such an epimorphism will be called order preserving . The epimorphism f is constructed from e and a homeomorphism U/K cong S. Two such actions are equivalent if and only if there is an automorphism a in Aut+(Gamma) and an automorphism b in Aut(G) such that the respective order preserving epimorphisms satisfy the relation e'=b(e a).
In my talk I will discuss the problem of determining of equivalence classes of discrete actions. In particular, we investigate the action of Aut+(Gamma) on the set of epimorphisms Epi(Gamma,G) for a finite group G and a Fuchsian group Gamma. In case of planar Fuchsian groups, that means groups with signature (0;m_1,...,m_r), we present a complete answer giving rise to an algorithm constructing the equivalence classes. I present a list of such actions of small genera. In the general case, we have a partial result.
Joint work with M. Skyvova and J. Karabas.

Census of planar discrete group actions: Genus 2, Genus 3, Genus 4, Genus 5, Genus 6,

January 18, 7pm CET = 6pm UTC, Gordon Williams,
Prisms Aren't Boring

To view the recording of Gordon's talk, click on the title. To see the slides, click here.

Abstract: From a geometric standpoint, prisms are relatively easy to conceptualize, even when formed over polytopes of high rank. The construction of a prism over an abstract polytope, map, or maniplex also has a rather natural description (Gleason and Hubard's discussion in [1] is quite nice, where it is an instructive example of a type of product). Since the prism operation seems comparatively easy to describe, one might be tempted to describe the prism operation as being somewhat boring. However, once one tries to understand the relationship between prisms and other polytopes, life gets a lot more interesting.
In this talk we are going to explore prisms over abstract polytopes from the perspective of regular covering theory, where the goal is to identify the minimal regular abstract polytope that covers a given polytope. In [2], the connection groups of prisms over polygons were described in some detail, and a consequence of a result in [3] is that prisms over polygons always have a unique minimal regular cover. In this talk, we'll prove a very general result about a family of prisms of higher rank that always possess a unique minimal regular cover, describe a conjecture about when even more do, and discuss some examples of some prisms over polytopes that likely don't. Along the way we'll discuss connections to the theory of maps and maniplexes, the importance of the connection group of a polytope in thinking about this kind of question, and some of the new computational tools we've been working on.
This is joint work with Gabriel Cunningham and Mark Mixer, and incorporates some results Cunningham and I developed with Daniel Pellicer.
[1] I. Gleason and I. Hubard. Products of abstract polytopes. J. Combin. Theory Ser. A, 157, 287-320, 2018.
[2] M. I. Hartley, D. Pellicer, and G. I. Williams. Minimal covers of the prisms and antiprisms. Discr. Math., 312(20), 3046-3058, October 2012.
[3] B. Monson, D. Pellicer, and G. I. Williams. Mixing and monodromy of abstract polytopes. Trans. of the AMS, 366, 2651-2681, 2014.

January 4, 7pm CET = 6pm UTC, Domenico Catalano,
Which simple groups are automorphism groups of chiral maps (or not)

To view the recording of Domenico's talk, click on the title. To see the slides, click here.

Abstract: During and after the classification of finite simple groups, many papers of many authors appear giving geometric and algebraic characterizations of them.
In this talk, we focus our attention (and interest) in the relation of finite simple groups with maps, restricting us to regular maps and regular oriented maps (orientably-regular maps).


December 21, 7pm CET = 6pm UTC, Tatiana Jajcayova,
On the interplay between global and local symmetries

To view the recording of Tanya's talk, click on the title. To see the slides, click here.

Abstract: While algebraic graph theorists tend to focus on graphs possessing many symmetries, the majority of graphs are asymmetric, i.e., having no non-trivial symmetries at all. In our talk, we attempt to reconcile these two seemingly opposing views, and we will argue that asymmetric and highly symmetric graphs are not that far apart as it may seem. In this, we rely on the concept of a partial isomorphism which is an isomorphism between two induced subgraphs of a graph (which may or may not extend to a global automorphism of the entire graph).
We will begin by reviewing a number of classical problems that include partial isomorphisms and automorphisms, we will include examples which demonstrate the close connection between asymmetric and highly symmetric graphs, and then we will present the framework of inverse semigroups of partial automorphisms of graphs that unite the two classes. We conclude with some recent results concerning inverse semigroups of partial automorphisms of graphs which are parallel to the classical result of Frucht showing that each finite abstract group is isomorphic to the automorphism group of some finite graph and to the concept of Graphical Regular Representations.

December 7, 7pm CET = 6pm UTC, Peter Cameron,
Graphs defined on groups

To view the recording of Peter's talk, click on the title. To see the slides, click here.

Abstract: There are a number of different graphs defined on a group reflecting the group structure in some way, and invariant under automorphisms of the group. The oldest of these is the commuting graph, which was implicit in the seminal paper by Brauer and Fowler in 1955; others include the power graph, enhanced power graph, nilpotence and solvability graphs, generating graph, and independence graph. Most of these can be fitted into a hierarchy. There has recently been an upsurge of interest in these graphs, so I cannot give a complete account; but some interesting questions concern the hierarchy, and the question of which groups have the property that two of the graphs coincide on that group. Among classes of groups that can be defined in this way are EPPO groups, groups with cyclic or generalized quaternion Sylow subgroups, 2-Engel groups, and Dedekind groups.

November 23, 7pm CET = 6pm UTC, Gabriel Verret,
Local actions and eigenspaces of vertex-transitive graphs

To view the recording of Gabriel's talk, click on the title. To see the slides, click here.

Abstract: When studying families of vertex-transitive graphs, it is often important to have control on the size of vertex-stabilisers of the automorphism groups. It turns out that the "local" action of the automorphism group plays a crucial role. I'll explain this connection, describe some known results and another more recent connection with the size of the eigenspaces of such graphs over finite fields.

November 9, 7pm CET = 6pm UTC, Andrea Svob,
Construction of graphs from groups

To view the recording of Andrea's talk, click on the title. To see the slides, click here.

Abstract: In this talk, a method for constructing regular graphs from groups will be explained. Some of the constructed graphs will be strongly regular. In the first part of the talk we will give a construction of transitive incidence structures and graphs. In the second part we will extend and generalize the method to obtain non-transitive graphs. The methods will be followed up with various examples.

October 26, 7pm CEST, Micael Toledo,
On the automorphisms of cubic vertex transitive graphs

To view the recording of Micael's talk, click on the title. To see the slides, click here.

Abstract: Automorphisms of cubic vertex transitive graphs exhibit a flurry of interesting properties. This allows us to study cubic vertex transitive graphs that admit an automorphism of relatively large order (relative to the order of the graph). We present theoretical results and an application.

October 12, 10am CEST, Brian Alspach, Exploring F(1,2)-invariant Graphs.

To view the recording of Brian's talk, click on the title. To see the slides, click here.

Abstract: A trivalent vertex-transitive graph X is F(1,2)-invariant if it admits a partition of its edge set into a 2-factor F and a 1-factor I such that the partition is invariant under the automorphism group of X. We describe the F(1,2)-invariant graphs whose 2-factor is either a single cycle or composed of two cycles. We also mention some possible future directions one might take.

September 28, 7pm CEST = 5pm UTC, Martin Skoviera, Geometric approach to Berge's conjecture.

To view the recording of Martin's talk, click on the title. To see the slides, click here.

Abstract: A fascinating conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. Since three perfect matchings suffice only when the graph is 3-edge-colourable, the remaining cubic graphs fall into two classes: those that can be covered with four perfect matchings, and those that need at least five.
Understanding the cubic graphs that require more than four perfect matchings to cover their edges is therefore fundamental for any potential approach that might lead to proving or disproving Berge's conjecture. A significant obstacle for this has been the fact that examples of cubic graphs that cannot be covered with four perfect matchings are extremely rare and difficult to find.
In the talk we outline a theory that describes coverings with four perfect matchings as flows whose flow values represent points and outflow patterns represent lines of a configuration six lines spanned by four points of the 3-dimensional projective space over the 2-element field in general position. This theory provides a powerful tool for investigating the graphs that do not admit such a cover and leads to a number of new results. Among them are, for instance, unification all known examples and constructions into a single family, offering a great variety of new constructions, or disproving conjectures that attribute certain properties to cubic graphs that cannot be covered with four perfect matchings.
The talk is based on several recently published papers (and some forthcoming ones) co-authored by Edita Macajova.

June 8, 7pm CET, Asia Ivic Weiss, Overview and recent contributions to the evolution of regular polyhedra and polytopes

To view the recording of Asia's talk, click on the title. To see the slides, click here.

Abstract: We give an up-to-date status on the classification of geometric polyhedra with high degree of symmetry, and discuss the realization theory of abstract regular polytopes. We also introduce the concept of a hypertope (a generalization of a polytope which in turn generalizes the concept of a map and hypermap to higher rank objects). We investigate locally spherical hypertopes of spherical, euclidean, and hyperbolic types and finite hypertopes arising from them giving some examples and summarizing the known results.

May 25, 7pm CET, Klara Stokes, Constructions of combinatorial configurations

To view the recording of Klara's talk, click on the title. To see the slides, click here.

Abstract: A combinatorial configuration of points and lines is an incidence geometry with two types with properties that mimic the properties of geometric configurations of points and lines. The study of geometric configurations is a classical topic in geometry, but the combinatorics precede the geometry; to every geometric configuration there is associated a combinatorial configuration. In this talk I will survey a number of constructions of configurations, with a special focus on constructions that use graphs in some way.

May 11, 7pm CET, Martin Bachraty, Skew morphisms of finite groups

To view the recording of Martin's talk, click on the title. To see the slides, click here.

Abstract: Skew morphisms, which generalise automorphisms for groups, are related to regular Cayley maps, and also to finite groups with a complementary factorisation G = BC, where C is cyclic and core-free in G. In this talk, I will outline the connections between these three concepts, and then explain what is currently known about skew morphisms for various families of finite groups.

April 27, 7pm CET, Wilfried Imrich, On the cost of asymmetrizing graphs

To view the recording of Wilfried's talk, click on the title. To see the slides, click here.

Abstract: A coloring of the vertex set of a graph G is asymmetrizing or distinguishing if it is only preserved by the identity automorphism. When two colors suffice, then the vertex set V(G) of G can be partitioned into two sets, each of which is only preserved by the identity automorphism. The minimum cardinality of such a set is the 2-distinguishing cost r(G) of G.
For infinite graphs r(G) may be infinite. In that case one looks for sparse asymmetrizing sets and defines a 2-distinguishing density.
Closely related to these parameters is the motion m(G) of a graph G. It is the minimum number of vertices moved by each nonidentity automorphism.
The talk treats the relationship between these parameters in general and in more detail for trees, graphs of maximum valence 3, and vertex transitive cubic graphs.

April 13, 7pm CET, Tom Tucker, What Is a Map?

To view the recording of Tom's talk, click on the title. To see the slides, click here.

Abstract: This talk presents a history of the different ways mathematicians have viewed maps. The list of past mathematicians includes Euclid, Euler, Fricke-Klein, Riemann, Heawood, Whitney, Coxeter-Moser, Ringel-Youngs, Tutte, Groethendieck. The methods include geometry (spherical, euclidean, or hyperbolic), Riemann surfaces, incidence structures, polytopes, graph theory, covering spaces, edge-colored graphs, permutation groups, combinatorial and finite group theory. The history is complicated by a lack of agreement on terminology and notation. Of particular interest is a slew of approaches occurring between 1974 and 1982. Several members in the audience for this talk have played key roles.

March 30, 7pm CET, Ted Dobson, Recognizing vertex-transitive digraphs which are wreath products, double coset digraphs, and generalized wreath products

To view the recording of Ted's talk, click on the title. To see the slides, click here.

Abstract: It is known that a Cayley digraph $\Cay(A,S)$ of an abelian group $A$ is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $B\le A$ such that $S\setminus B$ is a union of cosets of $B$ in $A$. We generalize this result to Cayley digraphs $\Cay(G,S)$ of nonabelian groups $G$ by showing that such a digraph is isomorphic to a nontrivial wreath product if and only if there is a proper nontrivial subgroup $H\le G$ such that $S\setminus H$ is a union of double cosets of $H$ in $G$. This result is proven in the more general situation of a double coset digraph. We then give applications of this result, which include showing the problem of determining automorphism groups of vertex-transitive digraphs is equivalent to the problem of determining automorphism groups of Cayley digraphs, and extending the definition of generalized wreath product digraphs to double coset digraphs of all groups $G$.

March 16, 8:15pm CET, Leah Berman, Configurations of Points and Lines

To view the recording of Leah's talk, click on the title. To see the slides, click here.

Abstract: An (n_k) configuration is a collection of n points and n lines, in which each point lies on k of the lines, and each line passes through k of the points. When the points and lines are actual points and straight lines in the Euclidean plane, the configuration is a geometric configuration. This talk will provide a survey of interesting results and open questions about configurations, focusing on configurations with high levels of geometric symmetry.

March 2, 7pm, Antonio Montero, Highly symmetric polytopes with prescribed local combinatorics

To view the recording of Tero's talk, click on the title. To see the slides, click here.

Abstract: Convex polyhedra and tilings of the Euclidean or hyperbolic plane can be thought of as a family of polygons glued together along their edges. This idea extends to higher dimensions: a 4-dimensional cube can be thought of as a family of 3-dimensional cubes glued together along their 2-dimensional faces. This way of thinking of polytopes gives rise to some natural questions: given a n-dimensional polytope K, can we build a (n+1)-dimensional polytope P such that all the facets (maximal proper faces of P) are isomorphic to K? how many of such P can we build? Usually the geometry plays an important role in these questions.
In the talk we will explore variants of this question in the context of abstract polytopes, where the geometry is less relevant. In particular, we are interested in the situation where prescribed symmetry conditions are imposed on P.

February 16, 7pm, Marston Conder, Regular and chiral maps with given valency or given type

To view the recording of Marston's talk, click on the title. To see the slides, click here.

Abstract: A map is 2-cell embedding of a connected graph in a closed surface, breaking up the surface to simply-connected regions called faces. The map is called `regular' if its automorphism group has a single orbit on flags (which are like incident vertex-edge-face triples), or `orientably-regular' if the surface is orientable and the automorphism group of the map has a single orbit on arcs (incident vertex-edge pairs). If a map of the latter kind admits no reflections (e.g. fixing an arc but swapping the two faces incident with it), then the map is called `chiral'. In such maps with a high degree of symmetry, all vertices have the same valency, say k, and all faces have the same size, say m, and then we call the ordered pair {m,k} the `type' of the map.

Writing a section of a forthcoming book on such maps (with Gareth Jones, Jozef Siran and Tom Tucker) has prompted me to review and extend what is known about regular and chiral maps with given valency k, or with given type {m,k}, including what happens in the special case where the automorphism group is isomorphic to an alternating or symmetric group. I will summarise findings in this talk.

February 2, 7pm, Klavdija Kutnar, Vertex-transitive graphs: from derangements to rigid cells

To view the recording of Klavdija's talk, click on the title. To see the slides, click here.

Abstract: When dealing with symmetry of combinatorial objects -- or in any other setting for that matter -- one will inexorably come across two different kinds of nonidentity automorphisms of these objects: those fixing as large as possible subset of points, on the one hand, and those fixing no points at all on the other.
For example, given a graph X and an automorphism a of X, we let Fix(a) be the set of all those vertices of X which are fixed by a. When Fix(a) is empty, then a is called a derangement, and furthermore, it is said to be semiregular if all of its cycles in the cycle decomposition are of the same length. When Fix(a) is non-empty, then an a-rigid cell is a connected component of the subgraph induced by Fix(a). In this lecture, I will aim for two goals:
G1: give a complete description of rigid cells in cubic arc-transitive graphs, and
G2: discuss some recent developments in regards to the problem of deciding which cubic arc-transitive graphs admit the so called simplicial automorphisms, that is, semiregular auto-morphisms whose quotient ``multigraphs'' are in fact simple graphs -- a special case of the well known semiregularity problem regarding existence of semiregular automorphisms in vertex-transitive graphs.

January 19, 7pm, Jozef Siran, Cayley graphs in the degree-diameter problem

To view the recording of Jozef's talk, click on the title. To see the slides, click here.

Abstract: The degree-diameter problem is to determine the largest order n(d,k) of a graph of a given maximum degree d and diameter k. We will survey constructions of largest currently known Cayley graphs of a given degree and diameter and discuss the possibility of asymptotically approaching a natural upper bound on n(d,k) - known as the Moore bound - by Cayley graphs.

January 5, 7pm, Gabriel Cunningham, 3-orbit skeletal polyhedra

To view the recording of Gabe's talk, click on the title. To see the slides, click here.

Abstract: A \emph{skeletal polyhedron} is a graph embedded in space where certain simple cycles are designated as faces, subject to some ``geometric'' restrictions. The symmetry group of a skeletal polyhedron consists of the isometries that preserve the graph and the face structure. A skeletal polyhedron is k-orbit if the symmetry group has k orbits on the flags (consisting of a vertex, an edge at that vertex, and a face using that edge). The regular (1-orbit) skeletal polyhedra in $\mathbb E^3$ are the 48 Gr\"{u}nbaum-Dress polyhedra. One of the classes of 2-orbit skeletal polyhedra (the chiral ones) were classified by Egon Schulte in 2004-2005. In this talk, I will give a brief history of highly-symmetric polyhedra, and then I will discuss joint work with Daniel Pellicer where we are classifying the finite 3-orbit skeletal polyhedra. Unlike regular and 2-orbit polyhedra, there are finite skeletal 3-orbit polyhedra in $\mathbb E^2$. We will also see that although in principle, the symmetry group of a skeletal polyhedron might be a proper subgroup of the automorphism group of its graph, in a surprising number of cases that we encounter in our classification, the two groups coincide.

This talk will have no Cayley graphs, but circulant graphs do feature prominently.


December 22, 7pm, Primoz Sparl, On Cayley graphs of generalized dihedral groups

To view the recording of Primoz's talk, click on the title. To see the slides, click here.

Abstract: When considering various (difficult) problems about Cayley graphs one usually first takes a look at the Cayley graphs of abelian groups. For instance, the question of whether each connected Cayley graph of order at least 3 has a Hamilton cycle was answered in the affirmative for the special case of Cayley graphs of abelian groups long time ago. One then usually wants to move to groups that are not ``far away'' from being abelian. One of the most natural things to do is to consider (generalized) dihedral groups. However, as the situation regarding the previously mentioned question about the existence of Hamilton cycles shows, this seemingly small deviation can cause huge difficulties. Nevertheless, for some relatively simple problems the techniques for the case of abelian groups can sometimes carry over to the case for the generalized dihedral groups. In this talk I will present some (not necessarily related) results on Cayley graphs of generalized dihedral groups and try to compare the corresponding results for the Cayley graphs of abelian groups. I'll talk about extendability, distance regularity, symmetries and perhaps even efficient domination in these graphs. Some of these results are a few years old and some are very recent. Most of them are joint work with Stefko Miklavic.

December 8, 7pm, Joy Morris, Graphs that are Cayley on more than one group

To view the recording of Joy's talk, click on the title. To see the slides, click here.

Abstract: The Cayley digraph Cay(G,S) on the group G with connection set S is the graph whose vertices are the elements of G, with an arc from g to h if and only if hg^{-1} in S. If we want a graph, we add the additional requirement that S=S^{-1}.
Researchers often look at Cayley graphs from the perspective of a particular representation: a group G and a connection set S. However, it is very possible to have Cay(G,S) cong Cay(H,T), even if G not cong H. This presents interesting issues related to the isomorphism problem for Cayley graphs, and also has implications for determining the automorphism groups of such graphs. In addition, it is sometimes the case that if a particular Cayley graph seems exceptional, this may be due to the fact that it has a different representation under which it is not exceptional.
In this talk, I will present some results around graphs that have multiple representations as Cayley graphs. In particular, I will focus on Cayley graphs of prime power order and the very different implications that arise if one of the representations is on a cyclic group than if neither is. The results I will present include joint work with Ted Dobson, Luke Morgan, Josip Smolcic, and Gabriel Verret, in various combinations.

November 24, 7pm, Steve Wilson, Dart-transitive Edge-colorings of Graphs

To view the recording of Steve's talk, click on the title. To see the slides, click here.

Abstract: I will talk about highly symmetric colorings of highly symmetric graphs. With many examples, we will discuss how to find such colorings, how to show non-isomorphism, and we will see some of the varieties of such colorings. Most importantly, we will see how understanding the colorings of a graph helps to understand its structure.

Job Offering in Discrete Mathematics:

Postdoctoral Fellowship, Umea University

Friendly series and conferences:

Mirka Miller's Combinatorics Webinar Series

Lectorium on Algebraic Graph Theory

SIGMAP (Symmetries in Graphs, Maps and Polytopes), July 10 - 16, 2022, University of Alaska Fairbanks, U.S.A.

Innovations in Incidence Geometry, Algebraic, Topological, and Combinatorial


Isabel Hubard, Robert Jajcay and Primoz Potocnik