Title: Explicit Construction of Unique-Neighbor Expanders

Speaker: Michael Capalbo, DIMACS

Date: Tuesday, October 15, 2002

Location: Hill Center, room 705, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We define a unique-neighbor expander to be a bipartite graph $\Gamma$ with sides $X$ and $Y$, such that (1) $Y$ has significantly fewer vertices than $X$, andq (2) for every 'reasonably small' subset $S$ of $X$, there are are 'large' number of vertices in $Y$ that are adjacent to in $\Gamma$ to exactly one vertex in $S$. (We later define 'reasonably small' and 'large'). Unique-neighbor expanders have applications in communications networks, but the explicit construction of an infinite family of these graphs has been a long-standing open problem. Here we solve this open problem by presenting the first explicit constructions of an infinite family of bounded-degree 'unique-neighbor' expanders. \end{abstract}