CanaDAM 2021
En ligne, 25 - 28 mai 2021

Movement and symmetry in graphs - Part I
Org: Karen Gunderson (University of Manitoba), Karen Meagher (University of Regina) et Joy Morris (University of Lethbridge)

KAREN GUNDERSON, University of Manitoba
Bootstrap percolation on infinite graphs  [PDF]

In $r$-neighbour bootstrap percolation, vertices of a graph are either `healthy' or `infected' and infection spreads to a healthy vertex with at least $r$ infected neighbours. Percolation is said to occur if all vertices are eventually infected. When vertices are infected initially at random, the main question is the value of the critical probability -- where percolation becomes more likely than not. I will present results on how the variance of vertex degrees affects the value of the critical probability in Galton--Watson trees and discuss some open problems on the critical probabilities for infinite regular graphs including Cayley graphs.

JEANNETTE JANSSEN, Dalhousie University
An approximation algorithm for finding the zero-forcing number of a graph  [PDF]

Consider the following graph process: Given a graph with vertices coloured black or white. At each step, if a black vertex has exactly one white neighbour, then this neighbour turns black. If the process turns all vertices black, then the initial set of black vertices is a zero-forcing set. The minimum size of a zero-forcing set in a graph $G$ is called the zero-forcing number $z(G)$. We give an approximation algorithm that finds a zero-forcing set of size at most $(pw+1)z(G)$, where $pw$ is the path-width of $G$. This is joint work with Ben Cameron, Rogers Mathew, and Zhiyuan Zhang.

KAREN MEAGHER, University of Regina
Open problems related to Erd\H{o}s-Ko-Rado type results  [PDF]

I have been working on Erd\H{o}s-Ko-Rado type results using methods from Algebraic Graph Theory for many years. In this talk I will describe several problems and conjectures related to this work where my standard methods fail and I need new tools! These are all problems I am hoping to make progress on with the collaborative research group Movement and Symmetry in Graphs.

JOY MORRIS, University of Lethbridge
Regular Representations  [PDF]

A regular representation is a combinatorial object whose automorphism group is acting regularly (generally on the points). A regular action is one that is sharply transitive: i.e., there is precisely one automorphism taking any point to any other. I will give an overview of some of the results on regular representations (graphical, digraphical, tournament, etc.), including asymptotic results and results about when they can be easily detected.