Explicit Unique-Neighbor Expanders

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.

Authors

• Noga Alon
• Michael R. Capalbo

Keywords

• Graph theory
• Bipartite graph
• Mathematics
• Geometry
• Algorithm design and analysis
• Distributed algorithms
• Routing
• Parallel algorithms
• Positive Constant
• Explicit Construction
• Construction Of Family
• Family Of Graphs
• Eigenvalues
• Cardinality
• Set Of Integers
• Regular Graphs
• Small Graphs