Algebraic and Spectral Graph Theory (16w5111)

The Banff International Research Station will host the "Algebraic and Spectral Graph Theory" workshop from July 31st to August 5th, 2016.

Graphs are among the most ubiquitous combinatorial objects: They can be used to model an array of diverse phenomena, and arise naturally in almost every area of mathematics and the sciences. Algebraic and Spectral Graph Theory are two closely related research traditions whose goal is roughly to understand and manipulate graphs by associating with them more classically “structured” objects like matrices, vector spaces, polynomials, and groups. While the former is more likely to be concerned with exact algebraic concepts, often producing identities and recurrences, the latter tends to focus on softer, analytic concepts. Part of the impetus for this workshop is the significant and rapidly growing interaction between the two.

An old and fruitful direction which both areas have in common is the study of eigenvalues and eigenvectors of the adjacency matrix of a graph. The modern agenda features many other themes, from generating polynomials for various graph parameters (e.g., counting matchings or spin assignments), to physical and other processes on graphs (such as electrical flow, heat flow, wave propagation, random walks, and chip firing games), to the powerful analogies between graph theory and differential geometry.

Altogether, these methods have played a guiding role in algorithms, complexity theory, and combinatorics for a long while. But in the past ten years, that role has increased substantially. A new theory has developed which treats the package of spectral information holistically, leading to breakthroughs on problems that have resisted progress for many decades. The highlights of this recent work include near-linear time solvers for Laplacian systems, faster algorithms for computing maximum flows, relationships between graph spectra and multi-way expansion, construction of Ramanujan graphs of every degree, and the resolution of the Kadison-Singer problem in the foundations of quantum mechanics. Perhaps even more remarkably, the connections between these seemingly disparate threads are strong, deep, and growing.

The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the U.S. National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT)..