Abstract: Spectral graph theory is the study of the relationship between the graphical properties of a graph and the spectral properties (i.e., eigenvalues and eigenvectors) of various matrices associated with that graph, most commonly the adjacency matrix. The spectrum of the adjacency matrix of a cubic graph (i.e., one where each vertex has three neighbours) on n vertices is a set of n real numbers lying in the interval [-3,3] which determines a surprising amount of information about the graph. A spectral gap set X is an open subset of (-3,3) with the property that there are an infinite number of cubic graphs whose spectrum is disjoint from X. For example, the interval (-3,-2) is a spectral gap set because the infinite family of cubic line graphs has no eigenvalues in (-3,-2), and in fact the list of all cubic graphs whose spectrum avoids (-3,-2) is known. The fact that (-1,1) is a spectral gap set for cubic graphs has been shown at least twice previously, with two different (but closely related) infinite families of cubic graphs. In this talk, I describe some recent work, joint with Krystal Guo, where we give an exact characterisation of the cubic graphs whose spectrum avoids (-1,1). This allows us to deduce that (-1,1) is a maximal gap set, thereby answering a question of Kollar and Sarnak.

Joint work with Krystal Guo.

Abstract: The computer generation of complete catalogues of pairwise non-isomorphic graphs and other combinatorial objects (designs, geometries, matroids etc.) is a fundamental part of research in combinatorics. However the naive method of removing isomorphs---namely testing each newly constructed graph against each previously-constructed graph in the growing catalogue is possible only for tiny catalogues. In a seminal paper in the 1970s entitled "Every one a winner; or how to avoid isomorphism search when cataloguing combinatorial configurations'', Ron Read outlined an algorithm---that he called an orderly algorithm---for constructing isomorph-free catalogues without explicitly testing any pairs of graphs. In this talk, I will explain in some detail the principles behind Read's orderly algorithm, how its main weaknesses were addressed by its spiritual successor, Brendan McKay's canonical construction path algorithm, before finishing with some examples of the use of this latter algorithm.