Grant: Discovery Grants Program - Individual

Mathematical "graph theory" is the study of networks in the abstract. In this context, a "graph" is just a set of points (called vertices, representing the nodes of the network) and lines (called edges, representing connections between nodes). A graph can be used to represent any network (road; railway; computer; cell phone; interpersonal relations; chemical reactions, etc.) so as a model a graph allows us to understand some of the properties the corresponding network has, regardless of what sort of network it is. We may put arrows on (some of) our edges to represent one-way connections, or put labels on (some of) our edges to represent properties like distances or capacities, and studying this additional information yields further insight into the network. Studying graphs can help us understand the reasons why some real-life networks behave in the ways they do: for example, why a certain part of a network is most often the site of traffic jams (either real or virtual), or where a network is most vulnerable to becoming disconnected (either maliciously or accidentally). It can also help us design networks that have more desirable properties (are more robust, cheaper to build, etc.). Graph theory is also the source of many beautiful mathematical problems for which we do not yet necessarily have practical applications; mathematical understanding often predates technology that may make use of it, or simply advances our knowledge and understanding. When a graph has symmetries, these can make the graph easier to understand, since a symmetry really shows that the parts of the graph that can be exchanged by the symmetry are in some sense equivalent. Furthermore, research has shown that graphs with a lot of symmetry tend to have many desirable properties when constructed as real-world networks: for example, they provide an effective balance between the competing imperatives of cost and reliability. Group actions on graphs are a way of measuring and studying their symmetry, and is the focus of this research program. There are a number of beautiful methods for constructing graphs (networks) that impose a degree of symmetry (in particular, Cayley graphs are constructed from groups). When these construction methods are employed, it is almost always the case that the imposed symmetry accounts for all of the symmetry that the graph has. However, it can also happen that unexpected symmetries arise: symmetries that were not imposed by the construction method, but nevertheless appear. The focus of this research proposal is to better understand when and how such unexpected symmetries arise, as well as what they might look like when they do arise. We will also seek to improve our understanding of situations that preclude unexpected symmetries. Since having more symmetries seems to generally lead to desirable properties in a network, there is value in understanding symmetries that arise over and above what we imposed or expected.