Hoffman’s bound (or: ratio bound) on the size of a coclique (or: independent set, stable set) in a graph is one of the most important bounds in spectral graph theory. At the same time it is often misattributed. Primary reason for is that Hoffman never published it, but people want to cite something for it. A few weeks ago, Willem Haemers published a nice article which presents the history of Hoffman’s ratio bound (here is the journal version).
As I have probably misattributed the bound myself in the past and even one of my favorite books, “Distance-Regular Graphs” by Brouwer, Cohen and Neumaier does so too (but they correct it online), I wanted to make this quick post.
The sad occasion of Willem’s article is that Alan J. Hoffman past away on the 18th January 2021 at the age of 96. May he rest in peace.
I started writing this blog post some months ago. Occasion was that my paper “A construction for clique-free pseudorandom graphs” (in joint work Anurag Bishnoi and Valentina Pepe) was accepted by Combinatorica with minor revisions. More precisely, one of the referees was unfavorable of publication because he got the impressions that we are simply restating a result by Bannai, Hao and Song. I think that the referee had a point, but for slightly wrong reasons. This triggered me to do two things. First of all, it made me include more history of the construction in our actual paper. Then I wanted to write a blog post about the history of the construction. Sadly, I wanted to include too much history in my first attempt to write this post, so it was very much out of scope. Here now a more concise version of my original plan.
The following is mostly based on texts by Cordula Tollmien. I thank John Bamberg for his assistance, and Cordula Tollmien and Cheryl Praeger for their helpful comments on earlier drafts of this text.
Emmy Noether is one the most influential mathematicians of all time and one of the shining examples of the mathematics department at the Universität Göttingen during its glory days in the first third of the 20th century. Her most important contributions are in invariant theory with the celebrated Noether’s theorem in her habilitation and the invention modern algebra in a series of publications in the early 1920s. This text focusses on the context of her habilitation.