Bipartite Subgraphs and the Smallest Eigenvalue

Noga Alon, Benny Sudakov

Research output: Contribution to journalArticle

42 Scopus citations

Abstract

Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue μ of any non-bipartite graph on n vertices with diameter D and maximum degree Δ satisfies μ ≥ -Δ + 1/(D+1)n. This improves previous estimates and is tight up to a constant factor. The second result is the determination of the precise approximation guarantee of the MAX CUT algorithm of Goemans and Williamson for graphs G = (V,E) in which the size of the max cut is at least A|E|, for all A between 0.845 and 1. This extends a result of Karloff.

Original languageEnglish (US)
Pages (from-to)1-12
Number of pages12
JournalCombinatorics Probability and Computing
Volume9
Issue number1
DOIs
StatePublished - Jan 1 2000
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Bipartite Subgraphs and the Smallest Eigenvalue'. Together they form a unique fingerprint.

  • Cite this