Explicit unique-neighbor expanders
Noga Alon, Michael Capalbo · 2003
We present a simple, explicit construction of an infinite family F of bounded-degree 'unique-neighbor' expanders /spl Gamma/; i.e., there are strictly positive constants /spl alpha/ and /spl epsi/, such that all /spl Gamma/ = (X, E(/spl Gamma/)) /spl isin/ F satisfy the following property. For each subset S of X with no more than /spl alpha/|X| vertices, there are at least /spl epsi/|S| vertices in X/spl bsol/S that are adjacent in /spl Gamma/ to exactly one vertex in S. The construction of F is simple to specify, and each /spl Gamma/ /spl isin/ F is 6-regular. We then extend the technique and present easy to describe explicit infinite families of 4-regular and 3-regular unique-neighbor expanders, as well as explicit families of bipartite graphs with nonequal color classes and similar properties. This has several applications and settles an open problem considered by various researchers.