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:


September 28, 7pm CET, Martin Skoviera, Geometric approach to Berge's conjecture.

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

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:
Associate Professor in Mathematics, Umea University, Faculty of Science and Technology
We seek an Associate Professor in mathematics for a permanent post. Applicants are expected to strengthen our research in computational mathematics, discrete mathematics, or mathematical modelling and analysis. The deadline for applications is May 31, 2021.
For more information:

Friendly conferences:

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


Isabel Hubard, Robert Jajcay and Primoz Potocnik