 |
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).
|