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