Independence ratio and random eigenvectors in transitive graphs

Viktor Harangi, Bálint Virág

A theorem of Hoffman gives an upper bound on the independence ratio of regular graphs in terms of the minimum ${\lambda }_{\min }$ of the spectrum of the adjacency matrix. To complement this…