The Hoffman ratio bound, also called the Hoffman bound, is an upper bound on the independence number of a
regular graph in terms of its least graph
eigenvalue. If 
is a regular graph of vertex
degree 
on 
vertices and has least graph
eigenvalue 
,
then
 |
If an independent vertex set meets the bound, then every vertex outside the set has exactly 
neighbors in it.
Applying the bound to the graph complement gives
the corresponding upper bound on the clique
number. For a strongly regular graph,
the latter bound agrees with the Delsarte bound.
The result is due to A. J. Hoffman, but was not published by him. Lovász (1979, Thm. 9) published a bound using the Lovász
number that implies the Hoffman ratio bound, and Haemers (2021) gives a historical
account. The Hoffman ratio bound is the 
case of the Haemers
regular upper bound.
