Speaker
Description
One of the main goals in spectral graph theory is to deduce the principal properties and structure of a graph from its graph spectrum. In this talk we will show how spectral graph theory provides powerful methods for obtaining results concerning substructures of graphs, and also how these results can be useful in other mathematical fields such as coding theory. In particular, we will derive sharp eigenvalue bounds for the k-independence number of a graph (or equivalently, the independence number of the k-th graph power), which is known to be very hard to compute. We will see how to use polynomials and mixed integer linear programming in order to optimize and compute such spectral bounds. Finally, we will illustrate some recent applications of the obtained eigenvalue bounds to coding theory. The obtained results are encouraging and strongly suggest that spectral graph theory can uncover structural properties of ambient spaces that are relevant to coding theory, but that are often not captured by classical coding theory techniques. There is no question that eigenvalues play a central role in our fundamental understanding of graphs. The goal of this talk is to show that we can also use them for deepening our understanding of codes.