Hoffman, Lovász and Haemers

At the weekend I attended remotely a memorial session for Alan Hoffman, organised by Bill Pulleyblank. I found it informative, as well as moving.

Hoffman is well-known in the algebraic graph theory community for a number of remarkable achievements, including the theorem on Moore graphs of diameter 2 and the construction of the Hoffman–Singleton graph, his bounds for chromatic number and for independence number in terms of the eigenvalues, and his very influential work on graphs with smallest eigenvalue −2.

He is perhaps even better known in the optimization communnity. According to Jack Edmonds, he was the first person to program the simplex algorithm (at the Rand corporation in the early 1960s), and he has many results on flows including the famous Circulation Theorem. But apparently he was much more interested in theorems than in algorithms. Several of the speakers claimed to have got their start by devising an algorithm for something which Alan had shown to exist.

So it is true to say that Alan Hoffman was a bridge between these two rather different communities. I am firmly on the algebraic graph theory side of the bridge, and was not really aware of the amount that Alan had contributed to optimization.

One of the speakers was Willem Haemers, who last month put on the arXiv a short paper entitled “Hoffman’s ratio bound”. This is the result which asserts that a regular graph of degree k on n vertices with smallest eigenvalue −s has independence number at most ns/(k+s). You should read the paper for the history. Haemers begins by pointing out that Hoffman never published this result, and consequently many people give the wrong reference to it (to Delsarte, or to Lovász, or to the wrong paper of Hoffman).

He was followed by Laci Lovász, who recalled a visit by Hoffman to a meeting in the former DDR when Laci was just beginning his studies. Hoffman spoke about his earlier result, bounding the chromatic number of an arbitrary graph. Lovász took the result back to Budapest and worked on it. He found a beautiful trick which Hoffman would no doubt have loved (though with his habitual modesty he would have admired it without jealousy). Lovász observed that the argument does not depend on the fact that the non-zero entries of the adjacency matrix is 1; any positive numbers will work. So finding the best bound is an optimization problem, which Lovász solved to come up with his famous θ parameter of graphs, related to the Shannon capacity.

About Peter Cameron

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

1 Response to Hoffman, Lovász and Haemers

  1. Josh Paik says:

    Speak of the devil… I just spent all last night looking up whether we could say anything about the connectivity of a graph in terms of the rank of the adjacency (whether it be in the spirit of expanders or otherwise) and I stumbled upon the Kotlov and Lovasz result bounding the chromatic number in terms of the rank as well as the Lovasz theta number.

    A question I have, is, does low chromatic number, at least probabilistically, mean less “connected?”

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

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