Eigenvalue bounds for independent sets

Simple item page
dc.creatorGodsil, C. D.
dc.creatorNewman, M. W.
dc.date2005-08-03
dc.date.accessioned2026-07-07T05:22:13Z
dc.date.available2026-07-07T05:22:13Z
dc.descriptionWe derive bounds on the size of an independent set based on eigenvalues. This generalizes a result due to Delsarte and Hoffman. We use this to obtain new bounds on the independence number of the Erdős-Rényi graphs. We investigate further properties of our bounds, and show how our results on the Erdős-Rényi graphs can be extended to other polarity graphs.
dc.description18 pages
dc.identifierhttps://arxiv.org/abs/math/0508081
dc.identifierhttp://arxiv.org/abs/math/0508081
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/75975
dc.subjectCombinatorics
dc.subject05C69; 51E15, 51E12
dc.titleEigenvalue bounds for independent sets
dc.typetext

Files

Collections

arXiv