Spectral graph theory
Hoffman–Delsarte inequality

There is an eigenvalue bound for independent sets in regular graphs, originally due to Alan J. Hoffman and Philippe Delsarte.

Suppose that G {\displaystyle G} is a k {\displaystyle k} -regular graph on n {\displaystyle n} vertices with least eigenvalue λ m i n {\displaystyle \lambda _{\mathrm {min} }}. Then:

where α (G) {\displaystyle \alpha (G)} 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 fields.

For general graphs which are not necessarily regular, a similar upper bound for the independence number can be derived by using the maximum eigenvalue λ m a x ′ {\displaystyle \lambda '_{max}} of the normalized Laplacian of G {\displaystyle G}:

where m a x d e g {\displaystyle {\mathrm {maxdeg} }} and m i n d e g {\displaystyle {\mathrm {mindeg} }} denote the maximum and minimum degree in G {\displaystyle G}, respectively. This a consequence of a more general inequality (pp. 109 in):

where X {\displaystyle X} is an independent set of vertices and v o l (Y) {\displaystyle {\mathrm {vol} }(Y)} denotes the sum of degrees of vertices in Y {\displaystyle Y}.
detectable_format:title