 |
Relative Expansion and an Extremal Degree Two Cover of the Boolean Cube
- Postscript version.
- Dvi version.
- PDF version.
-
Abstract:
In this paper we show that there is a unique degree two cover of the
Boolean $n$-cube whose new eigenvalues are all $\pm \sqrt{n}$, and we
describe some of its properties. To explain it further, we develop
relative notions of expansion and relate them to the new eigenvalues.
We will give examples of the importance of covering maps.
We also explain how these properties generalize to pregraphs.
Then we perform some numerical calculations which suggest that
no such covers exists for general covers of higher degree. The
new eigenvalues of degree two covers gives a geometric interpretation
of the eigenvalues of ``signed graphs.''
- Note: this was submitted to Journal of Algebraic Combinatorics
in 1993 and rejected. I have not persued this article's publication
any further, but ideas and/or parts of this article may appear in my
later papers involving ``relative expansion,'' especially the one in
the Duke Journal. The article may have been modified up to 1995;
contrary to the title page, I was no longer at Princeton in 1995...
|