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 Kn 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 E8.

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.

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

3 Responses to Alan Hoffman

1. ENOCH SULEIMAN says:

Can I get Prof Peter Cameron contact please. His phone number if possible. Thanks.

2. Sebi Cioaba says:

That is sad news! Hoffman had so many beautiful theorems. The result you mentioned may be that for any given x between -1-\sqrt{2} and -2, any connected graph with \lambda_{min}\geq x and minimum degree large enough must be a generalized line graph with \lambda_{min}\geq -2. He has also has a similar theorem when x is between -2 and -1, where the generalized line graph is replaced by a complete graph. Hoffman mentions in the chapter “Graph Spectra” of the book “Selected Papers of Alan Hoffman with commentary” that “If I had known more about root systems in Lie algebras, I would have seen more direct routes to the answer (as Cameron, Goethals, Seidel and Shult did later), and perhaps not become involved in research on graph spectra at all.”

He comments on a related paper “On spectrally bounded graphs” that “I knew that, if G contained a large claw or a large graph of a certain other type as an induced subgraph the least eigenvalue of G had to be a negative number large in absolute value. So I speculated that those were (in a qualitative sense) the only possibilities for G to have a least eigenvalue of large absolute value; namely, a large representatitve of at least one of those two families of graphs must be an induced subgraph. I am very proud of this paper. …. (in the sytle of Erdos) God knows almost all theorems and chooses the particular theorems to be revealed to each mathematician. But I do not think God knew this theorem; I had to tell Him, but I still don’t know if He is interested.”

3. frankbel says:

I have just read this news, it is a very sad one. His research has inspired mine and that of many mathematicians working on graph spectra. Besides his contributions on the characterization of graphs with least eigenvalue not less than -2, I love the theory on limit points of eigenvalues developed by him. Possibly, he wrote the first paper on the spectra of signed graphs, another one of my favourite topics.

In one of the few messages we exchanged each other, he wrote:
“My favorite of all my papers on spectral graph theory is On Spectrally Bounded Graphs. Apart from one of my students, nobody did anything more on such topics, and I am disappointed. The paper specifies two monotonic sequences of graphs (K(1,n) and what we can call H(n)– a clique on 2n nodes, and another node joined to half the nodes of the clique) such that, a bound on the largest n such that either of these graphs is an induced subgraph of a graph G implies that there is a lower bound on the least eigenvalue of the adjacency matrix of G.”

Rest in peace, Alan.

This site uses Akismet to reduce spam. Learn how your comment data is processed.