Réunion d'hiver SMC 2024
Vancouver/Richmond, 29 novembre - 2 decembre 2024
Graphes de Cayley
Org: Soffia Arnadottir (UFMG (Federal University of Minas Gerais)) et Joy Morris (University of Lethbridge)
[PDF]
Org: Soffia Arnadottir (UFMG (Federal University of Minas Gerais)) et Joy Morris (University of Lethbridge)
[PDF]
- SOFFÍA ÁRNADÓTTIR, Federal University of Minas Gerais
Cayley incidence graphs [PDF]
-
Abstract: Cayley graphs are an important notion in algebraic graph theory as they connect the structures of groups and graphs. The concept of Cayley incidence graphs was first introduced by Evra et al in 2023 (referred to as Cayley bigraphs). They are bipartite, biregular graphs arising from Cayley graphs and in this talk we will explore their properties and connections with other algebraic structures. This is joint work with Alexey Gordeev, Sabrina Lato, Tovohery Randrianarisoa and Joannes Vermant.
- TED DOBSON, University of Primorska
${\mathbb Z}_{p}\times{\mathbb Z}_p$ is a BCI-group [PDF]
-
Haar graphs are natural bipartite analogues of Cayley digraphs. The BCI-problem asks whether two Haar graphs of a group $G$ are isomorphic if and only if they are isomorphic group by a list of specific maps, all of which are automorphisms of ${\mathbb Z}_2\ltimes G$. Let $p$ be an odd prime. We show that ${\mathbb Z}_p\times{\mathbb Z}_p$ is a BCI-group, meaning two Haar graphs of ${\mathbb Z}_p\times{\mathbb Z}_p$ are isomorphic if and only if they are isomorphic by maps on the specific list. This is the first example of a group $G$ that is a BCI-group where the group ${\mathbb Z}_2\ltimes G$ is not a CI-group with respect to digraphs.
- BOBBY MIRAFTAB, Carleton University
From finite to infinite: hamiltonian structures in Cayley graphs [PDF]
-
A weaker version of the celebrated Lovász conjecture states that every finite, connected Cayley graph contains a hamiltonian cycle. Although infinite graphs cannot have hamiltonian cycles in the traditional sense, there are natural analogues. In this talk, we focus on one such analogue—a topological approach—and show that some known results for finite Cayley graphs can be extended to infinite Cayley graphs.
- RAGHU PANTANGI
Perfect State Transfer in Cayley and double coset graphs related to linear groups in two dimensions. [PDF]
-
Quantum walk on a graph, a quantum analogue of the random walk on a graph, is a model originating from quantum physics and is of interest in quantum information theory. Of central importance to this theory is the perfect state transfer (PST). A result by Godsil shows that for a given maximum valency, there are only finitely many connected graphs that exhibit PST. For this reason, it is interesting to find infinite classes of examples of connected graphs that admit PST. In this talk, we will construct examples of PST admitting Cayley and double coset graphs associated with $\mathrm{SL}(2,q)$ $\mathrm{GL}(2,q)$, and $\mathrm{GU}(2,q^2)$. The Cayley graphs we construct, as far as we know, are the first such PST admitting examples in which the underlying groups are not solvable. This is joint work with Peter Sin.
- PRIMOZ POTOCNIK, University of Ljubljana
Extended Census of Cubic Cayley Graphs [PDF]
-
When studying combinatorial objects of a certain type, it is useful to have an extensive list of such objects, upon which
our conjectures can be built or tested; think of the famous Foster census of cubic arc-transitive graphs, for example.
The main purpose of my talk is to discusses a recently extended census of cubic Cayley graphs on at most 4094 vertices,
available at https://graphsym.net, which extends a previous census containing all such graph of order up to 1280 obtained
by Verret, Spiga and myself. I will present ways how to use the census as well as show some interesting emerging patterns.
- AMARPREET RATTAN, Simon Fraser University
Centrality of star factorizations [PDF]
-
Let $\mathfrak{S}_n$ be the symmetric group on $\{1, 2, \ldots, n\}$ and $S:=\{(i\, n) : 1 \leq i \leq n-1\}$. It is known that Cayley graph on $\mathfrak{S}_n$ with generating set $S$, denoted $\Gamma(\mathfrak{S}_n, S)$, has an interesting spectrum: all of its eigenvalues are integral. Walks on this Cayley graph beginning at the identity can be interpreted as factorizations of elements in $\mathfrak{S}_n$ where factors come from $S$. We call these star factorizations. Call a walk (or the corresponding factorization) transitive if the transpositions corresponding to the walk generate a transitive subgroup of $\mathfrak{S}_n$. The set of such walks in $\Gamma(\mathfrak{S}_n, S)$ have a remarkable property: the number of transitive walks to an element $\gamma$ only depends on the conjugacy class of $\gamma$, a surprising result because of the asymmetry in the set $S$. We refer to this property | that the number of factorizations of conjugate elements is the same | as the centrality property. Goulden and Jackson (2009) showed that transitive star factorizations are central, but this result was obtained as a corollary of their enumerative formulae. They posed the natural problem of finding a combinatorial explanation for centrality.
In this talk, I will discuss the centrality property of star factorizations and related factorizations that are central despite asymmetries in their underlying factorization problems. Our main result is that we give a combinatorial proof of the centrality of star factorizations, resolving the problem posed by Goulden and Jackson.
This is joint work with J. Campion Loth (Heilbronn Institute).
- GABRIEL VERRET, University of Auckland
Density of quotient orders in groups and applications to locally-transitive graphs [PDF]
-
We will discuss a recent result that the set of orders of finite quotients of a finitely generated group has natural density 0, 1/2 or 1. We also discuss applications of this result to the natural density of the set of orders of various families of symmetric graphs.
- XIAOHONG ZHANG, Université de Montréal
Signed or oriented Cayley graphs with nice spectrum [PDF]
-
Let $G$ be a finite abelian group. We consider signed or oriented Cayley graphs on $G$, whose adjacency matrices are symmetric or skew symmetric (0,1,-1) matrices, respectively. We give a characterization of when all the eigenvalues of such a graph are integer multiples of $\sqrt{\Delta}$ for some fixed square-free integer $\Delta$. This generalizes a result of Bridges and Mena on when a Cayley graph on $G$ has only integer eigenvalues. Our result also characterizes signed or oriented Cayley graphs on which continuous quantum walks are periodic. This is joint work with Chris Godsil.
- SHASHA ZHENG, Comenius University in Bratislava
Asymptotic proportion of graphical regular representations among Cayley graphs [PDF]
-
A Cayley graph whose group of symmetries is as small as its underlying group is called a graphical regular representation (GRR for short) of the group. In this talk we are concerned with the existence of GRRs and their asymptotic behaviour. Here are some natural questions: What kind of automorphism group of a Cayley graph is `typical'; what kind of Cayley graph is `common'? Viewing that `symmetry is rare', a rough guess for the first question would be the groups that are `as small as possible' in some sense, and one may guess for the second question that the Cayley graphs with the lowest level of symmetry would be the most common ones. We estimate the number of GRRs of a given group with large enough order and, based on some previously known results, show that almost all finite Cayley graphs have full automorphism groups `as small as possible'. This confirms a conjecture of Babai--Godsil--Imrich--Lov\'{a}sz.