Tight products and Expansion

Details Tight products and Expansion Tight products and Expansion

2010-01-20

arxiv.org/abs/1001.3661v1

Computer Science

Discrete Mathematics

Scientific paper

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 $NP$-hard to decide). We investigate the conditions under which this is possible. This perspective yields a new characterization of class-1 $(2k+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.

Affiliated with

Also associated with

No associations

Rating

Tight products and Expansion does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Tight products and Expansion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Tight products and Expansion will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-248396