Alan Hoffman

I have just heard the news that Alan Hoffman has died, at the age of 96.

There is much to say about Alan; I will restrict myself to my own person perspective, and not even all of that; I didn’t know him well, but met him several times and regarded him as a friend.

Alan was interested (among many other things) in eigenvalues of graphs, in particular the smallest eigenvalue, and more particularly still the class of graphs with smallest eigenvalue −2 (or greater). To describe such graphs, it is enough to describe the connected ones.

Alan knew that line graphs have least eigenvalue −2 (or greater, in a few simple cases). One of his results from the 1950s characterized the line graph of the complete graph K_n by its spectrum if n is not equal to 8. (For n = 8, there are three exceptional graphs, characterized by Chang.)

Alan further invented the class of generalized line graphs, which also have least eigenvalue −2. He knew that this class did not capture all such graphs (the Petersen graph, unsurprisingly, being an exception), but he conjectured that “most” connected graphs with least eigenvalue −2 are generalized line graphs, and around 1970 wrote a long manuscript attempting to prove a result along these lines. I never saw this legendary manuscript, so I am not quite sure what it did; I think perhaps “most” meant a lower bound on the minimum valency of a vertex.

Anyway, it was this manuscript which led Jean-Marie Goethals and Jaap Seidel to a geometric analysis, where they embedded the graph as a set of vectors of fixed length in a Euclidean space, any two making an angle of 90 degrees or 60 degrees. They also showed that the lines spanned by such a set could be enlarged to a maximal set, which was “star-closed” (that is, if two lines in a plane make an angle of 60 degrees, then the third line at 60 degrees to both is also in the set). I realised that these star-closed sets were exactly the lines spanned by the vectors in a root system of type ADE. This gave rise to a very simple proof of Hoffman’s theorem, in stronger form: a connected graph with least eigenvalue −2 is either a generalized line graph or one of a finite set (up to isomorphism), all of which were embeddable as above in the root system E₈.

I think Alan was very pleased with this theorem (not least because he had no need to struggle to complete his long manuscript). The paper is among my most cited.

So rest in peace, Alan.