Editing Spectral graph theory (section)

== Hoffman–Delsarte inequality ==
There is an eigenvalue bound for [[Independent set (graph theory)|independent sets]] in [[regular graph]]s, originally due to [[Alan J. Hoffman]] and Philippe Delsarte.<ref>{{Cite web|url=https://www.math.uwaterloo.ca/~cgodsil/pdfs/ekrs-clg.pdf|title=Erdős-Ko-Rado Theorems|last=Godsil|first=Chris|date=May 2009}}</ref>

Suppose that <math>G</math> is a <math>k</math>-regular graph on <math>n</math> vertices with least eigenvalue <math>\lambda_{\mathrm{min}}</math>. Then:<math display="block">\alpha(G) \leq \frac{n}{1 - \frac{k}{\lambda_{\mathrm{min}}}}</math>where <math>\alpha(G)</math> denotes its [[independence number]].

This bound has been applied to establish e.g. algebraic proofs of the [[Erdős–Ko–Rado theorem]] and its analogue for intersecting families of subspaces over [[finite field]]s.<ref>{{Cite book|title=Erdős-Ko-Rado theorems : algebraic approaches|last1=Godsil|first1=C. D.|last2=Meagher|first2=Karen|isbn=9781107128446|location=Cambridge, United Kingdom|oclc=935456305|year = 2016}}</ref>

For general graphs which are not necessarily regular, a similar upper bound for the independence number can be derived by using the maximum eigenvalue
<math> \lambda'_{max}</math> of the normalized Laplacian<ref name=chung/> of <math>G</math>:
<math display="block">\alpha(G) \leq n (1-\frac {1}{\lambda'_{\mathrm{max}}}) \frac {\mathrm{max deg}}{\mathrm{min deg}}
</math>
where <math>{\mathrm{max deg}}</math> and <math>{\mathrm{min deg}}</math> denote the maximum and minimum degree in <math>G</math>, respectively. This a consequence of a more general inequality (pp. 109 in
<ref name=chung/>):
<math display="block">{\mathrm{vol}}(X) \leq  (1-\frac {1}{\lambda'_{\mathrm{max}}}) {\mathrm{vol}}(V(G))
</math> 
where <math>X</math> is an independent set of vertices and <math>{\mathrm{vol}}(Y)</math> denotes the sum of degrees of vertices in <math>Y</math> .