2016 CMS Summer Meeting

University of Alberta, June 24 - 27, 2016

Plenary, Prize and Public Lectures By session By speaker Posters

Algebraic graph theory: including Cayley graphs, group actions on graphs, graph eigenvalues, graphs and matrices
Org: Joy Morris (Lethbridge)
[PDF]

ROBERT BAILEY, Grenfell Campus, Memorial University On the metric dimension of incidence graphs [PDF]

A resolving set for a graph $\Gamma$ is a collection of vertices chosen so that any vertex of $\Gamma$ is uniquely identified by the list of distances to the chosen few. The metric dimension of $\Gamma$ is the smallest size of a resolving set for $\Gamma$. In this talk, we will consider the incidence graphs of symmetric designs, and show how he probabilistic method can be used to bound their metric dimension. In the case of incidence graphs of Hadamard designs, this result is (asymptotically) best possible.

JOEL FRIEDMAN, University of British Columbia Sheaves on Graphs and Applications [PDF]

We will give an introduction to sheaves on graphs and briefly discuss some of their applications.

A sheaf of vector spaces on a graph is a family of vector spaces, one for each vertex and one for each edge, with maps from each edge's space to those of its incident vertices. Each sheaf has its own incidence matrix, Laplacians, adjecency matrices, etc.

Sheaves allow us to (1) compare different sheaves over the same graph via exact sequences, and (2) create "new" morphisms between graphs, e.g., when there is no surjection of one graph to another, there can be surjections of the sheaves "representing" the graphs.

We explain how the above ideas helped to resolve the Hanna Neumann conjecture, using a symmetry argument for sheaves on Cayley graphs. This symmetry argument was recently "algebrized" by Jaikin-Zapirain, via work of Dicks, to resolve the "pro-p analog" of the Hanna Neumann conjecture.

This talk assumes only basic linear algebra and graph theory. Part of the material is joint work with Alice Izsak, Lior Silberman, and Warren Dicks.

SHONDA GOSSELIN, University of Winnipeg The metric dimension of circulant graphs [PDF]

A pair of vertices $x$ and $y$ in a graph $G$ are said to be resolved by a vertex $w$ if the distance from $x$ to $w$ is not equal to the distance from $y$ to $w$. We say that $G$ is resolved by a subset of its vertices $W$ if every pair of vertices in $G$ is resolved by some vertex in $W$. The minimum cardinality of a resolving set for $G$ is called the metric dimension of $G$. The problem of determining the metric dimension of a graph is known to be NP-hard (Khuller et al 1994). The metric dimension of a graph has applications in network discovery and verification, combinatorial optimization, chemistry, and many other areas, and consequently this graph parameter has received a great deal of attention from researchers recently, the main goal being to determine the metric dimension of certain classes of graphs. In this talk, we consider the metric dimension of circulant graphs, which are Cayley graphs on cyclic groups that were recently shown to be a class of graphs with bounded metric dimension (Grigorius et al 2014). We present some background on the problem and some new results. This is joint work with my student Kevin Chau.

CATHY KRILOFF, Idaho State University Spectra of Cayley graphs of complex reflection groups [PDF]

The distance matrix records the length of the shortest path between each pair of vertices in a graph and a graph with integral distance spectrum will be called distance integral. Renteln proved that Cayley graphs of finite real reflection groups with respect to all reflections are distance integral and provided combinatorial formulas for the distance spectrum of the infinite families of such graphs. We extend this result by proving that Cayley graphs of finite complex reflection groups with connection set consisting of all reflections are distance integral. We also provide a combinatorial formula for the distance spectrum for a family of monomial complex reflection groups. This is joint work with Briana Foster-Greenwood.

NATHAN LINDZEY, University of Waterloo Intersecting Families of Perfect Matchings [PDF]

A family of perfect matchings of $K_{2n}$ is $t$-intersecting if any two of its members have $t$ edges in common. It has been conjectured that such a family cannot have size larger than $(2(n-t)-1)!!$ for sufficiently large $n$, and that the extremal families are precisely those comprised of every perfect matching containing a fixed set of $t$ disjoint edges. We discuss a proof of this conjecture, emphasizing the algebraic aspects and techniques surrounding the proof.

SEAN MCGUINNESS, Thompson Rivers University Hamilton Paths in the Cayley Graph of a Dihedral Group [PDF]

A well-known conjecture states that every connected Cayley graph of order three or greater is Hamiltonian. We shall look at this conjecture in the special case of the Cayley graph of a dihedral group $D_n$. When $n$ is even, the conjecture is known to be true. We shall look at the case where $n$ is odd. As it turns out, the problem in this case reduces to showing that a certain class of cubic graphs is Hamilton-laceable. We shall present some results which show that Hamilton-laceability is possible so long as the graph is big enough.

KAREN MEAGHER, University of Regina Derangement graphs for 2-transitive groups [PDF]

The \textsl{derangement graph} of a permutation group $G$ is a Cayley graph on $G$ and the connection set is the set of all derangements in $G$ (these are the elements with no fixed points). The eigenvalues of the derangement graph can be calculated using the irreducible characters of the group. The well-known \textsl{ratio bound} (also known as the Delsarte-Hoffman ratio bound) uses the eigenvalues of the graph to bound the size of the maximum coclique (or independent set) in the derangement graph. In this talk, I will show how a variant of this bound can be used to prove that the size of the largest coclique in the derangement graph for any $2$-transitive group is the size of the stabilizer of a point. This is related to the Erd\H{o}s-Ko-Rado Theorem for groups.

DAVE WITTE MORRIS, University of Lethbridge Infinitely many nonsolvable groups whose Cayley graphs are hamiltonian [PDF]

It has been conjectured that if $G$ is any finite group, then every connected Cayley graph on $G$ has a hamiltonian cycle. This conjecture has been verified for numerous groups that either are small or are close to being abelian, but we provide the first verification that includes infinitely many non-solvable groups. More precisely, we exhibit infinitely many primes $p$, such that every connected Cayley graph on the direct product $A_5 \times \mathbb{Z}_p$ has a hamiltonian cycle (where $A_5$ is the alternating group on 5 letters).

JOY MORRIS, University of Lethbridge Cyclic $m$-cycle systems of near-complete graphs [PDF]

There are certain straightforward necessary conditions for a graph to be decomposable into cycles of a fixed length $m$: the valency of every vertex must be even; the number of edges must be divisible by the cycle length. The graphs that are most natural to try to decompose into cycles, are complete graphs $K_n$. If $n$ is even, then a 1-factor must be removed from the graph so that it meets the first necessary condition, and the resulting graph is denoted by $K_n-I$.

Alspach, Gavlas, and \v{S}ajna proved that the necessary conditions are sufficient to ensure an $m$-cycle decomposition of $K_n$, or of $K_n-I$. Since $K_n$ has a great deal of symmetry, it is natural to ask whether or not some of that symmetry can carry over into an $m$-cycle decomposition. We let $\rho$ denote the $n$-step rotation of the complete graph $K_n$, or of $K_n-I$ (where the 1-factor that has been removed is chosen so that the graph still has $n$-step rotational symmetry). An $m$-cycle system is called cyclic, if for any cycle $C$ in the system, $\rho(C)$ is also in the system.

I will discuss results on cyclic $m$-cycle systems of $K_n$ and more particularly $K_n-I$, including recent results dealing with the case where $m$ is an even divisor of $n$.

ADRIÁN PASTINE, Michigan Technological University Abelian Groups are R-Sequenceable [PDF]

In his 1974 solution to the map colouring problem for all compact 2-dimensional manifolds except the sphere, Gerhard Ringel was led to the following group-theoretic problem: When can the non-identity elements of a group of order $n$ be cyclically arranged in a sequence $g_0$, $g_1, g_2, ..., g_{n-1}$ such that the quotients $g^{-1}_ig_{i+1}$, $i = 0, 1, 2, . . . , n$ (with subscripts modulo $n$) are all distinct?

The complete Cayley graph $X$ on a group $G$ is the complete directed graph where the edge $(x, y)$ is labeled by $x^{-1}y$. The edges with a given label $z$ in $G$ form a 1-factor $F_z$ and $\{F_z\, :\, z \in G\}$ is a 1-factorization of $X$. A subgraph $H$ of $X$ is an orthogonal subgraph if it contains exactly one edge of each of the one-factors. In this language Ringel’s problem asks: For which groups $G$ does the complete Cayley graph $X$ admit an orthogonal directed cycle? In this joint work with Brian Alspach and Donald L. Kreher, we will discuss R-Sequenceability of even ordered abelian groups.

HARMONY ZHAN, University of Waterloo Spectra of Discrete Quantum Walks [PDF]

Due to the extra coin register, the relation between the spectrum of a discrete quantum walk and the spectrum of the underlying graph $X$ is in general unclear. However, in the model where the transition matrix $U$ is a product of two reflections, the eigenvalues and eigenvectors of $U$ are completely determined by those of $X$. In fact, $U$ is closely related to the directed line graph of $X$. We will derive the spectral decomposition of $U$ and use it to construct a family of circulant graphs that admit perfect state transfer.

Sponsors