CanaDAM 2021
En ligne, 25 - 28 mai 2021

Spectral Graph Theory - Part II
Org: Sebastian Cioaba (University of Delaware) et Michael Tait (Villanova University)

NATHAN LINDZEY, University of Colorado, Boulder
Some Recent Applications of Association Schemes  [PDF]

Association schemes are families of regular graphs that possess remarkable spectral properties. Born from design and coding theory, their impact on this area has been profound, but in recent years they have also found utility beyond their raison d'être. In this talk, we give a brief overview of such recent applications of association schemes to other areas of discrete mathematics. In particular, we survey a few recent results in extremal combinatorics and theoretical computer science that have been obtained through the theory of association schemes, with an emphasis on the latter.

THEO MCKENZIE, University of California, Berkeley
Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs  [PDF]

In this talk, we bound the multiplicity of the second eigenvalue of the normalized adjacency matrix, assuming the graph is connected. The main ingredient is a lower bound on the typical support of a random walk that is conditioned to be "closed" (namely, the walk ends where it starts). This, in turn, is shown by proving that the spectral radius of principal submatrices of the normalized adjacency matrix must satisfy certain bounds. Throughout the talk, we also give examples showing the tightness of our results.

This is joint work with Peter Rasmussen and Nikhil Srivastava

SIDHANTH MOHANTY, University of California, Berkeley
On the relationship between spectra, girth and vertex expansion in regular graphs  [PDF]

1. For every $d = p+1$, prime $p$ and infinitely many $n$, we exhibit an $n$-vertex $d$-regular graph with girth $\Omega(\log_{d-1} n)$ and vertex expansion of sublinear sized sets bounded by $(d+1)/2$ whose nontrivial eigenvalues are bounded in magnitude by $2\sqrt{d-1}+O(1/\log n)$.

2. In any near-Ramanujan graph with girth $C \log n$, sets of size bounded by $n^{0.99C/4}$ have near-lossless vertex expansion $(1-o_d(1))d$.

Our tools include the nonbacktracking operator of an infinite graph, the Ihara-Bass formula, a Bordenave inspired trace moment method, and a method of Kahale to study dispersion of eigenvalues of perturbed graphs.

Joint with Theo McKenzie (

SJANNE ZEIJLEMAKER, Eindhoven University of Technology
Optimization of eigenvalue bounds for the independence and chromatic number of graph powers  [PDF]

The $k$th power of a graph $G$ is the graph in which two vertices are adjacent if their distance is at most k. This talk presents eigenvalue bounds for the independence and chromatic number of $G^k$ which purely depend on the spectrum of $G$, together with a method to optimize them. Some new bounds for the $k$-independence number also work for its quantum counterpart, which is not known to be computable in general. Infinite graph families for which the bounds are sharp are presented as well. This is joint work with A. Abiad, G. Coutinho, M.A. Fiol and B.D. Nogueira.