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.
