Vertex-transitive graphs with large automorphism groups

Gabriel Verret (University of Auckland, New Zealand)

Many results in algebraic graph theory can be viewed as upper bounds on the size of the automorphism group of graphs satisfying various hypotheses. These kinds of results have many applications. For example, Tutte's classical theorem on 3-valent arc-transitive graphs led to many other important results about these graphs, including enumeration, both of small order and in the asymptotical sense. This naturally leads to trying to understand barriers to this type of results, namely graphs with large automorphism groups. We will discuss this, especially in the context of vertex-transitive graphs of fixed valency. We will highlight the apparent dichotomy between graphs with automorphism group of polynomial (with respect to the order of the graph) size, versus ones with exponential size.