Title: Unique-Neighbor Expanders
Speaker: Michael R. Capalbo, Rutgers University
Date: Monday, December 8, 2003, 1:10 pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
We define an expander to be a bounded-degree graph Gamma = (V,E) such that, for every subset S of V such that |S| is no larger than |V|/2, there are a `large' number of vertices in V\S that are adjacent to a vertex in S (so small subsets S "expand"). We say that Gamma is also a unique-neighbor expander if for every `reasonably small' subset S' of V, there are a large number of vertices in V\S' that are adjacent to exactly one vertex in S'. These graphs have several applications in Theoretical Computer Science, but no explicit construction of an infinite family of unique-neighbor expanders was know until recently. We present the first explicit construction of unique-neighbor expanders. (This is joint work with Noga Alon).