Generalized Alon-Boppana Theorems and Error-Correcting Codes
  • Postscript version.
  • Dvi version.
  • PDF version.

  • Abstract:

    In this paper we describe several theorems that give lower bounds on the second eigenvalue of any quotient of a given size of a fixed graph, $G$. These theorems generalize Alon-Boppana type theorems, where $G$ is a regular (infinite) tree. When $G$ is a hypercube, our theorems give minimum distance upper bounds on linear binary codes of a given size and information rate. Our bounds at best equal the current best bounds for codes, and only apply to linear codes. However, it is of interest to note that (1) one very simple Alon-Boppana argument yields non-trivial code bound, and (2) our Alon-Boppana argument that equals a current best bound for codes has some hope of improvement. We also improve the bound in sharpest known Alon-Boppana theorem (i.e., when $G$ is a regular tree).