Tight products and graph expansion

✍ Scribed by Amit Daniely; Nathan Linial

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 286 KB
• Volume: 69
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20593

✦ Synopsis

Abstract

In this article, we study a new product of graphs called 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~) × V(G~2~) and both projection maps V(H)→V(G~1~) and V(H)→V(G~2~) are covering maps. It is not a priori clear when two given graphs have a tight product (in fact, it is NP‐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. © 2011 Wiley Periodicals, Inc. J Graph Theory