Doctoral Prize Lecture

MICHAEL NEWMAN, University of Waterloo / Queen Mary University of London
Using eigenspaces of graphs

What can an eigenspace of a graph tell us?

There is an old result due to Hoffman that links the eigenspace of the least eigenvalue of a graph to independent sets. On the surface, it doesn't seem to say very much, and is perhaps surprisingly easy to prove.

On the other hand, it turns out that the independent sets characterized by this bound play a central role in the structure of the graph. Characterizing these independent sets tells us a lot about the graph; and we use this to show a graph is a core, and to determine information on chromatic numbers, among other things. This gives us a unified approach to a variety of problems. Association schemes also play a role, both historically and technically.

We look at some examples of how this technique can be applied, and mention some further developments.