
Generalized AlonBoppana Theorems and ErrorCorrecting 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 AlonBoppana 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 AlonBoppana argument
yields nontrivial code bound, and (2) our AlonBoppana argument that
equals a current best bound for codes has some hope of improvement.
We also improve the bound in sharpest known AlonBoppana theorem
(i.e., when $G$ is a regular tree).
