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:
2023
☛☛☛ June 13, 7pm CEST = 5pm UTC, Grigory Ryabov,
Schurity problem for S-rings: overview and new results
To view the recording of Grigory's talk, click on the title. To see the slides, click here.
Abstract: Every permutation group induces in a natural way a coherent configuration. Moreover, many concepts from the permutation group theory can be transferred to the coherent configuration theory. However, not every coherent configuration is induced by a suitable permutation group. This is the reason why the coherent configuration theory is sometimes called ``group theory without groups''. A coherent configuration is called schurian if it is induced by a suitable permutation group. Finding a border between schurian and nonschurian coherent configurations (schurity problem) presents one of the most fundamental problems in this theory. The talk will be devoted to the schurity problem for S-rings (Schur rings) which can be considered as a special important case of coherent configurations.
May 30, 7pm
CEST = 5pm UTC, Chaim Goodman-Strauss,
An aperiodic monotile
To view the recording of Chaim's talk, click on the title.
Abstract: A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the "hat" polykite, can form clusters called "metatiles", for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical -- and hence aperiodic -- tilings.
This is joint work with David Smith, Joseph Samuel Myers, and Craig S. Kaplan.
May 16, 7pm
CEST = 5pm UTC, Kan Hu,
Complete Regular Dessins and Skew Morphisms of Cyclic Groups
To view the recording of Kan's talk, click on the title. To see the slides, click here.
Abstract: A dessin is a $2$-cell embedding of a bipartite graph into an oriented closed surface. A dessin is regular if its group of orientation- and color-preserving automorphisms acts transitively on the edges. If the underlying graph of a regular dessin is a complete bipartite graph, it is called a complete regular dessin. The automorphism group $G$ of a complete regular dessin with underlying graph $K_{m,n}$ is known to have an exact $(m,n)$-bicyclic factorization $G=\langle a\rangle \langle b\rangle$, where $\langle a\rangle\cong\mathbb{Z}_m,$ $\langle b\rangle\cong\mathbb{Z}_n$ and $\langle a\rangle\cap \langle b\rangle=1$. Moreover, all such dessins $D$ with $\mathrm{Aut}(D)$ isomorphic to $G$ correspond to the orbits of $\mathrm{Aut}(G)$ acting on the exact bicyclic generating pairs of $G$. This correspondence allows the use of group factorizations to classify and enumerate complete regular dessins, and to establish a new correspondence with certain pairs of skew morphisms of the cyclic groups. In this talk, we present an updated progress on the classification problem of complete regular dessins.
April 18, 7pm CEST = 5pm UTC, Stefko Miklavic,
(Closed) distance magic circulants
To view the recording of Stefko's talk, click on the title. To see the slides, click here.
Abstract: Let $\Gamma$ be a graph with vertex set $V$, and let $n=|V|$. A distance magic labelling of $\Gamma$ is a bijection $\ell : V \mapsto \{1,2, \ldots, n\}$ for which there exists a positive integer $r$ such that $\sum_{y \in \Gamma(x)} \ell(y) = r$ for all vertices $y \in V$, where $\Gamma(x)$ is the neighbourhood of $x$. Similarly, a closed distance magic labelling of $\Gamma$ is a bijection $\ell : V \mapsto \{1,2, \ldots, n\}$ for which there exists a positive integer $r$ such that $\sum_{y \in \Gamma[x]} \ell(y) = r$ for all vertices $y \in V$, where $\Gamma[x]$ is the closed neighbourhood of $x$. A graph is said to be (closed) distance magic if it admits a (closed) distance magic labelling. In this talk I will discuss (closed) distance magic circulants. The key ingredient of this research are eigenvalues and eigenvectors of circulant graphs, which could be computed using irreducible characters of cyclic groups.
April 4, 7pm CEST = 5pm UTC, Arindam Biswas,
On the cop number of algebraic graphs
To view the recording of Arindam's talk, click on the title. To see the slides, click here.
Abstract: We will study the game of cops and robbers in algebraic graphs. We show that the cop number of the Cayley sum graph of a finite group G with respect to a subset S is at most its degree when the graph is connected, undirected. We also show that a similar bound holds for the cop number of generalised Cayley graphs and the twisted Cayley sum graphs under certain conditions. Using the above bounds and a result of Bollobas-Janson-Riordan, we show that the weak Meyniel's conjecture holds for these algebraic graphs.
This is a joint work with J.P. Saha.
March 21, 7pm CET = 6pm UTC, Aida Abiad,
Eigenvalue bounds for the independence and chromatic number of graph powers
To view the recording of Aida's talk, click on the title. To see the slides, click here.
Abstract: In this talk I will present several eigenvalue bounds on the independence number and the distance chromatic number of graph powers. We will see how to use polynomials and mixed-integer linear programming in order to optimize such bounds. Some infinite families of graphs for which the new bounds are tight will also be shown.
March 7, 7pm CET = 6pm UTC, Veronika Bachrata,
Orientably-regular maps with no non-trivial exponents
To view the recording of Veronika's talk, click on the title. To see the slides, click here.
Abstract: Given an orientable map M, and an integer e relatively prime to the valency of M, the e-th rotational power M^e of M is the map formed by replacing the cyclic rotation of edges around each vertex with its e-th power. If maps M and M^e are isomorphic, and the corresponding isomorphism preserves the orientation of the carrier surface, then we say that e is an exponent of M.
In this talk, I will recall and explain some useful definitions, and then show how canonical regular covers of maps can be used to prove that for every given hyperbolic pair (k,m) there exists an orientably-regular map of type {m,k} with no non-trivial exponents. In particular, for each hyperbolic pair (k,m) we find a suitable orientable map of type {m,k} such that the canonical regular cover of this map is an orientably-regular map (of the same type) with no non-trivial exponents.
This is joint work with Martin Bachraty.
February 21, 7pm CET = 6pm UTC, Egon Schulte,
Skeletal Polyhedra, Complexes, and Symmetry
To view the recording of Egon's talk, click on the title. To see the slides, click here.
Abstract: The study of highly symmetric structures in Euclidean 3-space has a long and fascinating history tracing back to the early days of geometry. With the passage of time, various notions of polyhedral structures have attracted attention and have brought to light new exciting figures intimately related to finite or infinite groups of isometries. A radically different, skeletal approach to polyhedra was pioneered by Grunbaum in the 1970's building on Coxeter's work. A polyhedron is viewed not as a solid but rather as a finite or infinite periodic geometric edge graph in space equipped with additional polyhedral super-structure imposed by the faces. Since the mid 1970's there has been a lot of activity in this area. Much work has focused on classifying skeletal polyhedra and complexes by symmetry, with the degree of symmetry defined via distinguished transitivity properties of the geometric symmetry groups. These skeletal figures exhibit fascinating geometric, combinatorial, and algebraic properties and include many new finite and infinite structures.
February 7, 7pm CET = 6pm UTC, Antonina Khramova,
Constructing cospectral hypergraphs
To view the recording of Antoninas' talk, click on the title. To see the slides, click here.
Abstract: Spectral hypergraph theory mainly concerns using hypergraph spectra to obtain structural information about the given hypergraphs. The study of cospectral hypergraphs is important since it reveals which hypergraph properties cannot be deduced from their spectra. In this talk, we show a new method for constructing cospectral uniform hypergraphs using two well-known hypergraph representations: adjacency tensors and neighbor matrices. The method is inspired by WQH-switching (Wang, Qiu, Hu, 2019), also known in the literature as modified GM-switching.
The talk is based on joint work with Aida Abiad.
January 24, 7pm CET = 6pm UTC, Milagros Izquierdo,
Regular Maps and Curves with Large Number of Automorphisms
To view the recording of Milagros' talk, click on the title. To see the slides, click here.
Abstract: In 1878-79 Felix Klein gave Klein's Quartic as a 7-fold covering of the Riemann Sphere with monodromy group PSL(2,7) producing a tessellation of the Riemann surface imbedding what he called `linienz{\"u}ge'.
In 1896, Anders Wiman gave two (smooth, irreducible) complex algebraic curves for each genus $g\ge 2$: one admitting an automorphism of order 4g + 2, and the other admitting an automorphism of order 4g. These curves are known as Wiman's curves of type I and II respectively. These curves are determined by regular maps with large automorphism group. Wiman's curves of type II have exactly 8g orientation-preserving automorphisms, except in the case g = 2, when the curve has 48 automorphisms (and it provides the regular map of genus 2 having the maximum number of automorphisms, Bolza's curve).
In 1978, Gareth Jones and David Singerman showed the close relation between maps (and hypermaps) and (complex structure of some) Riemann surfaces (and triangular Fuchsian. groups): Belyi curves (after the work of Gennadii V. Belyi 1979). In 1984, Alexander Grothendieck gave the dessins d'enfants (the maps and hypermaps) as a combinatorial method to study the action of the Absolute Galois Group.
In this talk we will focus on Wiman's curve of type II that provide, for all integer values of $g \ge 2$ other than 3, 6, 12 and 30, the only two regular dessins d'enfant of genus g with orientation-preserving automorphism group of order 4g. Moreover, the regular map $\mathcal{W}_g$ with orientation-preserving automorphism group of order 8g corresponding to Wiman's curve of type II can be obtained as a medial subdivision of each of the two non-sporadic dessins with 4g orientation-preserving automorphisms.
Joint work with E. Bujalance, M. Conder and A. F. Costa
January 10, 7pm CET = 6pm UTC, Dimitri Leemans
The number of string C-groups of high rank
To view the recording of Dimitri's talk, click on the title. To see the slides, click here.
Abstract: Abstract polytopes are a combinatorial generalisation of classical objects that were already studied by the Greeks. They consist in posets satisfying some extra axioms. Their rank is roughly speaking the number of layers the poset has. When they have the highest level of symmetry (namely the automorphism group has one orbit on the set of maximal chains), they are called regular. One can then use string C-groups to study them. Indeed, string C-groups are in one-to-one correspondence with abstract regular polytopes. They are also smooth quotients of Coxeter groups. They consist in a pair $(G,S)$ where $G$ is a group and $S$ is a set of generating involutions satisfying a string property and an intersection property. The cardinality of the set $S$ is the rank of the string C-group. It corresponds to the rank of the associated polytope.
In this talk, we will give the latest developments on the study of string C-groups of high rank. In particular, if $G$ is a transitive group of degree $n$ having a string C-group of rank $r\geq (n+3)/2$, work over the last twelve years permitted us to show that $G$ is necessarily the symmetric group $S_n$. We have just proven in the last months that if $n$ is large enough, up to isomorphism and duality, the number of string C-groups of rank $r$ for $S_n$ (with $r\geq (n+3)/2$) is the same as the number of string C-groups of rank $r+1$ for $S_{n+1}$. This result and the tools used in its proof, in particular the rank and degree extension, imply that if one knows the string C-groups of rank $(n+3)/2$ for $S_n$ with $n$ odd, one can construct from them all string C-groups of rank $(n+3)/2+k$ for $S_{n+k}$ for any positive integer $k$. The classification of the string C-groups of rank $r\geq (n+3)/2$ for $S_n$ is thus reduced to classifying string C-groups of rank $r$ for $S_{2r-3}$. A consequence of this result is the complete classification of all string C-groups of $S_n$ with rank $n-\kappa$ for $\kappa\in\{1,\ldots,6\}$, when $n\geq 2\kappa+3$, which extends previous known results. The number of string C-groups of rank $n-\kappa$, with $n\geq 2\kappa +3$, of this classification gives the following sequence of integers indexed by $\kappa$ and starting at $\kappa = 1$. $$\Sigma{\kappa}=(1,1,7,9,35,48).$$ This sequence of integers is new according to the On-Line Encyclopedia of Integer Sequences.
Joint work with Peter J. Cameron (University of St Andrews) and Maria Elisa Fernandes (University of Aveiro).
Schurity problem for S-rings: overview and new results
To view the recording of Grigory's talk, click on the title. To see the slides, click here.
Abstract: Every permutation group induces in a natural way a coherent configuration. Moreover, many concepts from the permutation group theory can be transferred to the coherent configuration theory. However, not every coherent configuration is induced by a suitable permutation group. This is the reason why the coherent configuration theory is sometimes called ``group theory without groups''. A coherent configuration is called schurian if it is induced by a suitable permutation group. Finding a border between schurian and nonschurian coherent configurations (schurity problem) presents one of the most fundamental problems in this theory. The talk will be devoted to the schurity problem for S-rings (Schur rings) which can be considered as a special important case of coherent configurations.
An aperiodic monotile
To view the recording of Chaim's talk, click on the title.
Abstract: A longstanding open problem asks for an aperiodic monotile, also known as an "einstein": a shape that admits tilings of the plane, but never periodic tilings. We answer this problem for topological disk tiles by exhibiting a continuum of combinatorially equivalent aperiodic polygons. We first show that a representative example, the "hat" polykite, can form clusters called "metatiles", for which substitution rules can be defined. Because the metatiles admit tilings of the plane, so too does the hat. We then prove that generic members of our continuum of polygons are aperiodic, through a new kind of geometric incommensurability argument. Separately, we give a combinatorial, computer-assisted proof that the hat must form hierarchical -- and hence aperiodic -- tilings.
This is joint work with David Smith, Joseph Samuel Myers, and Craig S. Kaplan.
Complete Regular Dessins and Skew Morphisms of Cyclic Groups
To view the recording of Kan's talk, click on the title. To see the slides, click here.
Abstract: A dessin is a $2$-cell embedding of a bipartite graph into an oriented closed surface. A dessin is regular if its group of orientation- and color-preserving automorphisms acts transitively on the edges. If the underlying graph of a regular dessin is a complete bipartite graph, it is called a complete regular dessin. The automorphism group $G$ of a complete regular dessin with underlying graph $K_{m,n}$ is known to have an exact $(m,n)$-bicyclic factorization $G=\langle a\rangle \langle b\rangle$, where $\langle a\rangle\cong\mathbb{Z}_m,$ $\langle b\rangle\cong\mathbb{Z}_n$ and $\langle a\rangle\cap \langle b\rangle=1$. Moreover, all such dessins $D$ with $\mathrm{Aut}(D)$ isomorphic to $G$ correspond to the orbits of $\mathrm{Aut}(G)$ acting on the exact bicyclic generating pairs of $G$. This correspondence allows the use of group factorizations to classify and enumerate complete regular dessins, and to establish a new correspondence with certain pairs of skew morphisms of the cyclic groups. In this talk, we present an updated progress on the classification problem of complete regular dessins.
(Closed) distance magic circulants
To view the recording of Stefko's talk, click on the title. To see the slides, click here.
Abstract: Let $\Gamma$ be a graph with vertex set $V$, and let $n=|V|$. A distance magic labelling of $\Gamma$ is a bijection $\ell : V \mapsto \{1,2, \ldots, n\}$ for which there exists a positive integer $r$ such that $\sum_{y \in \Gamma(x)} \ell(y) = r$ for all vertices $y \in V$, where $\Gamma(x)$ is the neighbourhood of $x$. Similarly, a closed distance magic labelling of $\Gamma$ is a bijection $\ell : V \mapsto \{1,2, \ldots, n\}$ for which there exists a positive integer $r$ such that $\sum_{y \in \Gamma[x]} \ell(y) = r$ for all vertices $y \in V$, where $\Gamma[x]$ is the closed neighbourhood of $x$. A graph is said to be (closed) distance magic if it admits a (closed) distance magic labelling. In this talk I will discuss (closed) distance magic circulants. The key ingredient of this research are eigenvalues and eigenvectors of circulant graphs, which could be computed using irreducible characters of cyclic groups.
On the cop number of algebraic graphs
To view the recording of Arindam's talk, click on the title. To see the slides, click here.
Abstract: We will study the game of cops and robbers in algebraic graphs. We show that the cop number of the Cayley sum graph of a finite group G with respect to a subset S is at most its degree when the graph is connected, undirected. We also show that a similar bound holds for the cop number of generalised Cayley graphs and the twisted Cayley sum graphs under certain conditions. Using the above bounds and a result of Bollobas-Janson-Riordan, we show that the weak Meyniel's conjecture holds for these algebraic graphs.
This is a joint work with J.P. Saha.
Eigenvalue bounds for the independence and chromatic number of graph powers
To view the recording of Aida's talk, click on the title. To see the slides, click here.
Abstract: In this talk I will present several eigenvalue bounds on the independence number and the distance chromatic number of graph powers. We will see how to use polynomials and mixed-integer linear programming in order to optimize such bounds. Some infinite families of graphs for which the new bounds are tight will also be shown.
Orientably-regular maps with no non-trivial exponents
To view the recording of Veronika's talk, click on the title. To see the slides, click here.
Abstract: Given an orientable map M, and an integer e relatively prime to the valency of M, the e-th rotational power M^e of M is the map formed by replacing the cyclic rotation of edges around each vertex with its e-th power. If maps M and M^e are isomorphic, and the corresponding isomorphism preserves the orientation of the carrier surface, then we say that e is an exponent of M.
In this talk, I will recall and explain some useful definitions, and then show how canonical regular covers of maps can be used to prove that for every given hyperbolic pair (k,m) there exists an orientably-regular map of type {m,k} with no non-trivial exponents. In particular, for each hyperbolic pair (k,m) we find a suitable orientable map of type {m,k} such that the canonical regular cover of this map is an orientably-regular map (of the same type) with no non-trivial exponents.
This is joint work with Martin Bachraty.
Skeletal Polyhedra, Complexes, and Symmetry
To view the recording of Egon's talk, click on the title. To see the slides, click here.
Abstract: The study of highly symmetric structures in Euclidean 3-space has a long and fascinating history tracing back to the early days of geometry. With the passage of time, various notions of polyhedral structures have attracted attention and have brought to light new exciting figures intimately related to finite or infinite groups of isometries. A radically different, skeletal approach to polyhedra was pioneered by Grunbaum in the 1970's building on Coxeter's work. A polyhedron is viewed not as a solid but rather as a finite or infinite periodic geometric edge graph in space equipped with additional polyhedral super-structure imposed by the faces. Since the mid 1970's there has been a lot of activity in this area. Much work has focused on classifying skeletal polyhedra and complexes by symmetry, with the degree of symmetry defined via distinguished transitivity properties of the geometric symmetry groups. These skeletal figures exhibit fascinating geometric, combinatorial, and algebraic properties and include many new finite and infinite structures.
Constructing cospectral hypergraphs
To view the recording of Antoninas' talk, click on the title. To see the slides, click here.
Abstract: Spectral hypergraph theory mainly concerns using hypergraph spectra to obtain structural information about the given hypergraphs. The study of cospectral hypergraphs is important since it reveals which hypergraph properties cannot be deduced from their spectra. In this talk, we show a new method for constructing cospectral uniform hypergraphs using two well-known hypergraph representations: adjacency tensors and neighbor matrices. The method is inspired by WQH-switching (Wang, Qiu, Hu, 2019), also known in the literature as modified GM-switching.
The talk is based on joint work with Aida Abiad.
Regular Maps and Curves with Large Number of Automorphisms
To view the recording of Milagros' talk, click on the title. To see the slides, click here.
Abstract: In 1878-79 Felix Klein gave Klein's Quartic as a 7-fold covering of the Riemann Sphere with monodromy group PSL(2,7) producing a tessellation of the Riemann surface imbedding what he called `linienz{\"u}ge'.
In 1896, Anders Wiman gave two (smooth, irreducible) complex algebraic curves for each genus $g\ge 2$: one admitting an automorphism of order 4g + 2, and the other admitting an automorphism of order 4g. These curves are known as Wiman's curves of type I and II respectively. These curves are determined by regular maps with large automorphism group. Wiman's curves of type II have exactly 8g orientation-preserving automorphisms, except in the case g = 2, when the curve has 48 automorphisms (and it provides the regular map of genus 2 having the maximum number of automorphisms, Bolza's curve).
In 1978, Gareth Jones and David Singerman showed the close relation between maps (and hypermaps) and (complex structure of some) Riemann surfaces (and triangular Fuchsian. groups): Belyi curves (after the work of Gennadii V. Belyi 1979). In 1984, Alexander Grothendieck gave the dessins d'enfants (the maps and hypermaps) as a combinatorial method to study the action of the Absolute Galois Group.
In this talk we will focus on Wiman's curve of type II that provide, for all integer values of $g \ge 2$ other than 3, 6, 12 and 30, the only two regular dessins d'enfant of genus g with orientation-preserving automorphism group of order 4g. Moreover, the regular map $\mathcal{W}_g$ with orientation-preserving automorphism group of order 8g corresponding to Wiman's curve of type II can be obtained as a medial subdivision of each of the two non-sporadic dessins with 4g orientation-preserving automorphisms.
Joint work with E. Bujalance, M. Conder and A. F. Costa
The number of string C-groups of high rank
To view the recording of Dimitri's talk, click on the title. To see the slides, click here.
Abstract: Abstract polytopes are a combinatorial generalisation of classical objects that were already studied by the Greeks. They consist in posets satisfying some extra axioms. Their rank is roughly speaking the number of layers the poset has. When they have the highest level of symmetry (namely the automorphism group has one orbit on the set of maximal chains), they are called regular. One can then use string C-groups to study them. Indeed, string C-groups are in one-to-one correspondence with abstract regular polytopes. They are also smooth quotients of Coxeter groups. They consist in a pair $(G,S)$ where $G$ is a group and $S$ is a set of generating involutions satisfying a string property and an intersection property. The cardinality of the set $S$ is the rank of the string C-group. It corresponds to the rank of the associated polytope.
In this talk, we will give the latest developments on the study of string C-groups of high rank. In particular, if $G$ is a transitive group of degree $n$ having a string C-group of rank $r\geq (n+3)/2$, work over the last twelve years permitted us to show that $G$ is necessarily the symmetric group $S_n$. We have just proven in the last months that if $n$ is large enough, up to isomorphism and duality, the number of string C-groups of rank $r$ for $S_n$ (with $r\geq (n+3)/2$) is the same as the number of string C-groups of rank $r+1$ for $S_{n+1}$. This result and the tools used in its proof, in particular the rank and degree extension, imply that if one knows the string C-groups of rank $(n+3)/2$ for $S_n$ with $n$ odd, one can construct from them all string C-groups of rank $(n+3)/2+k$ for $S_{n+k}$ for any positive integer $k$. The classification of the string C-groups of rank $r\geq (n+3)/2$ for $S_n$ is thus reduced to classifying string C-groups of rank $r$ for $S_{2r-3}$. A consequence of this result is the complete classification of all string C-groups of $S_n$ with rank $n-\kappa$ for $\kappa\in\{1,\ldots,6\}$, when $n\geq 2\kappa+3$, which extends previous known results. The number of string C-groups of rank $n-\kappa$, with $n\geq 2\kappa +3$, of this classification gives the following sequence of integers indexed by $\kappa$ and starting at $\kappa = 1$. $$\Sigma{\kappa}=(1,1,7,9,35,48).$$ This sequence of integers is new according to the On-Line Encyclopedia of Integer Sequences.
Joint work with Peter J. Cameron (University of St Andrews) and Maria Elisa Fernandes (University of Aveiro).
2022
December 27, 7pm CET = 6pm UTC, Cristina Dalfo
The algebraic connectivity of token graphs
To view the recording of Cristina's talk, click on the title. To see the slides, click here.
Abstract: We study the algebraic connectivity (or second Laplacian eigenvalue) of token graphs, also called symmetric powers of graphs. The k-token graph F_k(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. Recently, it was conjectured that the algebraic connectivity of F_k(G) equals the algebraic connectivity of G. In this talk, we prove the conjecture for new infinite families of graphs, such as trees, some graphs with hanging trees, graphs with minimum degree large enough. In these families are included the following graphs: the cocktail party graph, the complement graph of a cycle, the complete multipartite graph, etc. We also show the conjecture for cycles C_n when k=2 for most cases of n.
December 13, 7pm CET = 6pm UTC, Mark Mixer
Internal and External Duality in Abstract Polytopes
To view the recording of Mark's talk, click on the title. To see the slides, click here.
Abstract: Whenever a polytope is invariant under a transformation, such as duality, we often describe this as an ``external" symmetry of the polytope. However, in the context of abstract regular polytopes, self-duality can be seen as an automorphism of the symmetry group of the polytope. Often this symmetry will be an outer automorphism, but there are many interesting cases where the symmetry will be inner, and thus corresponds with a rank-preserving symmetry of the polytope; such polytopes are said to be internally self-dual.
What does this mean combinatorially? What types of polytopes have this property that self-duality yields an inner automorphism? In this talk, we will examine various examples of families of polytopes that are internally-self dual, and explore the implications of a polytope having an internal duality.
This is joint work with Gabe Cunningham.
November 29, 7pm CET = 6pm UTC, Marston Conder,
Constructing small volume hyperbolic manifolds from Coxeter groups
To view the recording of Marston's talk, click on the title. To see the slides, click here.
Abstract: It is well known that various compact hyperbolic manifolds of small volume can be constructed using torsion-free subgroups of minimum possible index in certain string Coxeter groups. Examples include the 600-cell and the Weber-Seifert and Gieseking manifolds, obtainable from the [3,3,5], [5,3,5] and [3,3,6] Coxeter groups. Constructions for certain 3-manifolds were developed in some notes by Milnor in the late 1970s on computing volumes, and in papers by Lorimer (1992) and Everitt (2004) using the identification of faces of a Platonic solid, and Colin Maclachlan and the speaker took a different approach (in 2005) to find the compact 4-manifold of currently smallest known volume, via subgroups of the [3,3,3,5] Coxeter group. Milnor's notes on 3-manifolds omitted the case of the [4,3,4] Coxeter group, and did not resolve some other cases, and a subsequent paper by Lorimer (2002) unsuccessfully attempted to deal with the case of the [4,3,5] Coxeter group.
We complete and extend these pieces of work by determining all of the small volume 3-manifolds constructible from torsion-free subgroups of minimum possible index in the [p,q,r] Coxeter groups for which p,q,r \ge 3 and each of the pairs (p,q) and (q,r) is spherical or Euclidean (that is, with 1/p+1/q \ge 1 and 1/q+1/r \ge 1).
This is quite recent joint work with PhD student Georgina Liversidge.
November 15, 7pm CET = 6pm UTC, Himanshu Gupta,
The least Euclidean distortion constant of a distance-regular graph
To view the recording of Himanshu's talk, click on the title. To see the slides, click here.
Abstract: Embedding graphs into Euclidean spaces with least distortion is a topic well-studied in mathematics and computer science. Despite this research, there are just a few graphs for which the precise least distortion and a least distortion embedding is known. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for Hamming and Johnson graphs as well as strongly regular graphs and conjectured that his bound is always tight for distance-regular graphs. In this talk, we provide several counterexamples to this conjecture with diameter 4 and larger, but we also prove the conjecture for several families of distance-regular graphs.
This is joint work with Sebastian M. Cioaba (University of Delaware), Ferdinand Ihringer (Ghent University) and Hirotake Kurihara (Kitakyushu National College of Technology).
November 1, 7pm CET = 6pm UTC,
Istvan Kovacs,
On certain edge-transitive bicirculants
To view the recording of Istvan's talk, click on the title. To see the slides, click here.
Abstract: A graph admitting an automorphism with two orbits of the same length is called a bicirculant. We consider the edge-transitive bircirculants of valency at least 3 for which the subgraph induced by at least one of the latter orbits is a cycle. All these graphs of valency up to 5 are known as well as those of valency 6 and of girth 3. In this talk, I present two results. The classification of the graphs of valency 6 and the classification of the graphs of any valency at least 3 and of twice odd order.
October 18, 7pm CEST = 5pm UTC, Olivia Jeans,
Orbits of fully regular maps on SL(2,q) under the group of operators < D, P, H_j >
To view the recording of Olivia's talk, click on the title. To see the slides, click here.
Abstract: A given group may be the automorphism group for many different isomorphism classes of a fully regular map. The associated group of operators is generated by the (usual, geometric) dual operator, the Petrie operator, and certain hole operators. This talk will look at the orbit structure of the operator group acting on the set of (isomorphism classes of) maps whose automorphism group is SL(2,q) for even q.
October 4, 7pm CEST = 5pm UTC, Vladislav Taranchuk,
On the eigenvalues of the graphs D(5,q)
To view the recording of Vlad's talk, click on the title. To see the slides, click here.
Abstract: Let q = p^e, where p is a prime and e is a positive integer. The family of graphs D(k, q), defined for any positive integer k and prime power q, were introduced by Lazebnik and Ustimenko in 1995. To this day, the connected components of the graphs D(k, q), provide the best known general lower bound for the size of a graph of given order and given girth. Furthermore, Ustimenko conjectured that the second largest eigenvalue of D(k, q) is always less than or equal to 2sqrt{q}. In this talk, we will discuss some of the recent progress on this conjecture, including new results that show that the second largest eigenvalue of D(5, q) is less than or equal to 2sqrt{q} when q is an odd prime power. This result is obtained through the use of representation theory and so a portion of the talk will be dedicated to giving a background on the tools used to prove the result.
This is joint work with Himanshu Gupta.
September 20, 7pm CEST = 5pm UTC, Gareth Jones,
Regular maps with primitive automorphism groups
To view the recording of Gareth's talk, click on the title. To see the slides, click here.
Abstract: This is work in progress with Martin Macaj. We classify the automorphism groups G of regular maps M which act faithfully and primitively on the vertices. As a permutation group G must be of almost simple or affine type, with dihedral point stabilisers. We show that all such almost simple groups, namely all but a few groups PSL(2,q), PGL(2,q) and Sz(q), arise from regular maps, which are always non-orientable. In the affine case, the maps M occur in orientable and non-orientable Petrie dual pairs. We give details of the genus and the extended type of each map. Some of this builds on recent work of Jajcay, Li, Siran and Wang on quasiprimitive automorphism groups.
June 21, 7pm CEST = 5pm UTC, Martin Macaj,
On the defect of vertex-transitive graphs of given degree and diameter
To view the recording of Martin's talk, click on the title. To see the slides, click here.
Abstract: The Degree/Diameter Problem is the problem of finding the largest order n(Delta,D) of a graph of maximum degree Delta and diameter D. The well-known Moore bound, M(Delta,D)=1+Delta((Delta-1)^D-1)/(Delta-2), provides a natural upper bound on n(Delta,D), and graphs that attain this bound are called Moore graphs. To avoid trivialities we will assume Delta > 2 and D > 1, in which case Moore graphs are very rare. Any graph G of maximum degree Delta and diameter D (a (Delta,D)-graph) is said to have the defect delta(G) = M(Delta,D) - |V(G)|.
We present bounds on the number of cycles of length 2D+1 in graph with prescribed degree Delta, diameter D and defect delta which besides the term Delta(Delta-1)^D/2 depend only on degree Delta and defect delta.
Using two classical number theory results due to Niven and Erdos, we prove that for any fixed degree Delta > 2 and any positive integer delta, the order of a largest vertex-transitive Delta-regular graph of diameter D differs from the Moore bound by more than delta for (asymptotically) almost all diameters D > 1. We also obtain an estimate for the growth of this difference, or defect, as a function of D.
This talk is based on a joint work with G. Exoo, R. Jajcay and J. Siran.
June 7, 7pm CEST = 5pm UTC, Elias Mochan,
Constructing k-orbit polytopes from their automorphism groups
To view the recording of Elias' talk, click on the title. To see the slides, click here.
Abstract: An abstract polytope is a combinatorial generalization of the face lattice of a convex polytope. The most studied abstract polytopes are the regular ones: those in which the automorphism group acts transitively on the set of flags. The automorphism groups of regular polytopes are characterized by having a set of generators satisfying what's called "the intersection property". This result has been generalized for some families of polytopes with lots of symmetries, for example chiral polytopes. However, until recently, not much was known about a general result about the automorphism groups of polytopes with an arbitrary number of flag-orbits.
In this talk we will use voltage graphs to be able to find the intersection properties that a group must satisfy to act by automorphisms on a polytope with an arbitrary number of flag-orbits given a desired symmetry type graph. We will also show how we can use this to build any polytope (with a given symmetry type), as a coset geometry from its automorphism group and a list of distinguished generators.
May 24, 7pm CEST = 5pm UTC, Tomo Pisanski,
Grunbaum incidence calculus revisited
To view the recording of Tomo's talk, click on the title. To see the slides, click here.
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).
The algebraic connectivity of token graphs
To view the recording of Cristina's talk, click on the title. To see the slides, click here.
Abstract: We study the algebraic connectivity (or second Laplacian eigenvalue) of token graphs, also called symmetric powers of graphs. The k-token graph F_k(G) of a graph G is the graph whose vertices are the k-subsets of vertices from G, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. Recently, it was conjectured that the algebraic connectivity of F_k(G) equals the algebraic connectivity of G. In this talk, we prove the conjecture for new infinite families of graphs, such as trees, some graphs with hanging trees, graphs with minimum degree large enough. In these families are included the following graphs: the cocktail party graph, the complement graph of a cycle, the complete multipartite graph, etc. We also show the conjecture for cycles C_n when k=2 for most cases of n.
Internal and External Duality in Abstract Polytopes
To view the recording of Mark's talk, click on the title. To see the slides, click here.
Abstract: Whenever a polytope is invariant under a transformation, such as duality, we often describe this as an ``external" symmetry of the polytope. However, in the context of abstract regular polytopes, self-duality can be seen as an automorphism of the symmetry group of the polytope. Often this symmetry will be an outer automorphism, but there are many interesting cases where the symmetry will be inner, and thus corresponds with a rank-preserving symmetry of the polytope; such polytopes are said to be internally self-dual.
What does this mean combinatorially? What types of polytopes have this property that self-duality yields an inner automorphism? In this talk, we will examine various examples of families of polytopes that are internally-self dual, and explore the implications of a polytope having an internal duality.
This is joint work with Gabe Cunningham.
Constructing small volume hyperbolic manifolds from Coxeter groups
To view the recording of Marston's talk, click on the title. To see the slides, click here.
Abstract: It is well known that various compact hyperbolic manifolds of small volume can be constructed using torsion-free subgroups of minimum possible index in certain string Coxeter groups. Examples include the 600-cell and the Weber-Seifert and Gieseking manifolds, obtainable from the [3,3,5], [5,3,5] and [3,3,6] Coxeter groups. Constructions for certain 3-manifolds were developed in some notes by Milnor in the late 1970s on computing volumes, and in papers by Lorimer (1992) and Everitt (2004) using the identification of faces of a Platonic solid, and Colin Maclachlan and the speaker took a different approach (in 2005) to find the compact 4-manifold of currently smallest known volume, via subgroups of the [3,3,3,5] Coxeter group. Milnor's notes on 3-manifolds omitted the case of the [4,3,4] Coxeter group, and did not resolve some other cases, and a subsequent paper by Lorimer (2002) unsuccessfully attempted to deal with the case of the [4,3,5] Coxeter group.
We complete and extend these pieces of work by determining all of the small volume 3-manifolds constructible from torsion-free subgroups of minimum possible index in the [p,q,r] Coxeter groups for which p,q,r \ge 3 and each of the pairs (p,q) and (q,r) is spherical or Euclidean (that is, with 1/p+1/q \ge 1 and 1/q+1/r \ge 1).
This is quite recent joint work with PhD student Georgina Liversidge.
The least Euclidean distortion constant of a distance-regular graph
To view the recording of Himanshu's talk, click on the title. To see the slides, click here.
Abstract: Embedding graphs into Euclidean spaces with least distortion is a topic well-studied in mathematics and computer science. Despite this research, there are just a few graphs for which the precise least distortion and a least distortion embedding is known. In 2008, Vallentin studied this problem for distance-regular graphs and obtained a lower bound for the least distortion of a distance-regular graph. In addition, he showed that this bound is tight for Hamming and Johnson graphs as well as strongly regular graphs and conjectured that his bound is always tight for distance-regular graphs. In this talk, we provide several counterexamples to this conjecture with diameter 4 and larger, but we also prove the conjecture for several families of distance-regular graphs.
This is joint work with Sebastian M. Cioaba (University of Delaware), Ferdinand Ihringer (Ghent University) and Hirotake Kurihara (Kitakyushu National College of Technology).
On certain edge-transitive bicirculants
To view the recording of Istvan's talk, click on the title. To see the slides, click here.
Abstract: A graph admitting an automorphism with two orbits of the same length is called a bicirculant. We consider the edge-transitive bircirculants of valency at least 3 for which the subgraph induced by at least one of the latter orbits is a cycle. All these graphs of valency up to 5 are known as well as those of valency 6 and of girth 3. In this talk, I present two results. The classification of the graphs of valency 6 and the classification of the graphs of any valency at least 3 and of twice odd order.
Orbits of fully regular maps on SL(2,q) under the group of operators < D, P, H_j >
To view the recording of Olivia's talk, click on the title. To see the slides, click here.
Abstract: A given group may be the automorphism group for many different isomorphism classes of a fully regular map. The associated group of operators is generated by the (usual, geometric) dual operator, the Petrie operator, and certain hole operators. This talk will look at the orbit structure of the operator group acting on the set of (isomorphism classes of) maps whose automorphism group is SL(2,q) for even q.
On the eigenvalues of the graphs D(5,q)
To view the recording of Vlad's talk, click on the title. To see the slides, click here.
Abstract: Let q = p^e, where p is a prime and e is a positive integer. The family of graphs D(k, q), defined for any positive integer k and prime power q, were introduced by Lazebnik and Ustimenko in 1995. To this day, the connected components of the graphs D(k, q), provide the best known general lower bound for the size of a graph of given order and given girth. Furthermore, Ustimenko conjectured that the second largest eigenvalue of D(k, q) is always less than or equal to 2sqrt{q}. In this talk, we will discuss some of the recent progress on this conjecture, including new results that show that the second largest eigenvalue of D(5, q) is less than or equal to 2sqrt{q} when q is an odd prime power. This result is obtained through the use of representation theory and so a portion of the talk will be dedicated to giving a background on the tools used to prove the result.
This is joint work with Himanshu Gupta.
Regular maps with primitive automorphism groups
To view the recording of Gareth's talk, click on the title. To see the slides, click here.
Abstract: This is work in progress with Martin Macaj. We classify the automorphism groups G of regular maps M which act faithfully and primitively on the vertices. As a permutation group G must be of almost simple or affine type, with dihedral point stabilisers. We show that all such almost simple groups, namely all but a few groups PSL(2,q), PGL(2,q) and Sz(q), arise from regular maps, which are always non-orientable. In the affine case, the maps M occur in orientable and non-orientable Petrie dual pairs. We give details of the genus and the extended type of each map. Some of this builds on recent work of Jajcay, Li, Siran and Wang on quasiprimitive automorphism groups.
On the defect of vertex-transitive graphs of given degree and diameter
To view the recording of Martin's talk, click on the title. To see the slides, click here.
Abstract: The Degree/Diameter Problem is the problem of finding the largest order n(Delta,D) of a graph of maximum degree Delta and diameter D. The well-known Moore bound, M(Delta,D)=1+Delta((Delta-1)^D-1)/(Delta-2), provides a natural upper bound on n(Delta,D), and graphs that attain this bound are called Moore graphs. To avoid trivialities we will assume Delta > 2 and D > 1, in which case Moore graphs are very rare. Any graph G of maximum degree Delta and diameter D (a (Delta,D)-graph) is said to have the defect delta(G) = M(Delta,D) - |V(G)|.
We present bounds on the number of cycles of length 2D+1 in graph with prescribed degree Delta, diameter D and defect delta which besides the term Delta(Delta-1)^D/2 depend only on degree Delta and defect delta.
Using two classical number theory results due to Niven and Erdos, we prove that for any fixed degree Delta > 2 and any positive integer delta, the order of a largest vertex-transitive Delta-regular graph of diameter D differs from the Moore bound by more than delta for (asymptotically) almost all diameters D > 1. We also obtain an estimate for the growth of this difference, or defect, as a function of D.
This talk is based on a joint work with G. Exoo, R. Jajcay and J. Siran.
Constructing k-orbit polytopes from their automorphism groups
To view the recording of Elias' talk, click on the title. To see the slides, click here.
Abstract: An abstract polytope is a combinatorial generalization of the face lattice of a convex polytope. The most studied abstract polytopes are the regular ones: those in which the automorphism group acts transitively on the set of flags. The automorphism groups of regular polytopes are characterized by having a set of generators satisfying what's called "the intersection property". This result has been generalized for some families of polytopes with lots of symmetries, for example chiral polytopes. However, until recently, not much was known about a general result about the automorphism groups of polytopes with an arbitrary number of flag-orbits.
In this talk we will use voltage graphs to be able to find the intersection properties that a group must satisfy to act by automorphisms on a polytope with an arbitrary number of flag-orbits given a desired symmetry type graph. We will also show how we can use this to build any polytope (with a given symmetry type), as a coset geometry from its automorphism group and a list of distinguished generators.
Grunbaum incidence calculus revisited
To view the recording of Tomo's talk, click on the title. To see the slides, click here.
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.
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.
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).
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.
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.
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.
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.
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.
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,
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.
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).
2021
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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$.
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.
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.
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.
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.
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.
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.
2020
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:
4 year PhD-position within the Vidi NWO project "Finding graph structure beyond the spectrum: new frontiers and new methods" supervised by Aida Abiad.
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
Organizers:
Isabel Hubard, Robert Jajcay and Primoz Potocnik
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.
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.
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:
4 year PhD-position within the Vidi NWO project "Finding graph structure beyond the spectrum: new frontiers and new methods" supervised by Aida Abiad.
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
Organizers:
Isabel Hubard, Robert Jajcay and Primoz Potocnik
 |
 |
 |
 |