paper

Tight products and Expansion

arXiv:1001.3661

Abstract

In this paper we study a new product of graphs called {\em tight product}. A graph $H$ is said to be a tight product of two (undirected multi) graphs $G_{1}$ and $G_{2}$ , if $V (H) = V (G_{1}) \times V (G_{2})$ and both projection maps $V (H) \to V (G_{1})$ and $V (H) \to V (G_{2})$ are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is $N P$ -hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class-1 $(2 k + 1)$ -regular graphs. We also obtain a new model of random $d$ -regular graphs whose second eigenvalue is almost surely at most $O (d^{3/4})$ . This construction resembles random graph lifts, but requires fewer random bits.