Grant: Discovery Grants Program - Individual

My research program involves using permutation groups to study symmetries of Cayley graphs. A ""graph"" is a model of a network, with ""vertices"" (points) representing nodes or terminals, and edges representing connections. Cayley graphs are graphs with strong symmetry: a simple example is the pentagram (star), which has rotational and reflectional symmetries.******Cayley graphs are interesting combinatorial objects to study for their own sakes. They also provide a class of graphs for which powerful techniques of group theory (abstract algebra) can be brought to bear in exploring difficult problems.******I will continue to work with students, post-doctoral fellows, and collaborators, to explore open problems on symmetries of Cayley graphs, including:******1. There is a canonical way of colouring the edges of a Cayley graph so that the most natural symmetries of the graph preserve this canonical colouring. I will be exploring when it is the case that only the most natural symmetries preserve this colouring, and when extra symmetries might preserve this colouring. Edge-colourings are much studied since they can be used to represent properties that vary for different edges of the graph, such as capacity. However, most edge-colourings destroy most symmetry. ******2. If a Cayley graph has the ""Cayley Isomorphism property,"" algebraic techniques enable us to determine whether or not another Cayley graph is essentially the same network, just drawn differently. This has been much studied for finite graphs. I will be studying the extension of this problem to infinite graphs, which has attracted much less attention. I will also work to extend some previous results of mine on which finite graphs have this property.******3. Sometimes Cayley graphs are allowed to have directed edges, representing one-way connections in the network; if they do, we call them digraphs. It is known that (with some exceptions) any ""nice"" collection of symmetries (a symmetry group) has a ""regular"" representation by a Cayley graph, meaning that there is a Cayley graph with precisely these ""regular"" symmetries. There is a similar result for Cayley digraphs. However, whether or not a symmetry group can be regularly represented by an oriented Cayley graph (with at most one directed edge between any pair of vertices) is a long-standing open problem. A co-author and I recently solved this problem for ""non-solvable"" symmetry groups. We will try to extend our work to ""solvable"" symmetry groups.******4. Describing a graph as a Cayley graph provides information about a large number of its symmetries, but often not all of them. I will work to characterise graphs that can be represented as a Cayley graph in more than one way. The second representation significantly enhances our ability to understand all of the symmetries such graphs exhibit.******These are steps toward solving recognition and isomorphism problems for Cayley graphs: extremely important open questions in algebraic graph theory.*****