loading...
Explicit Unique-Neighbor Expanders
Vancouver, BC, Canada November 16-November 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2002.1181884The 43rd Annual IEEE Symposium on Fou ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Noga Alon, Institute for Advanced Study and Tel Aviv University
Michael Capalbo, Institute for Advanced Study
We present a simple, explicit construction of an infinite family F of bounded-degree ?unique-neighbor? expanders \Gamma; i.e., there are strictly positive constants \alpha and, such that all \Gamma = (X,E(\Gamma)) \varepsilon F satisfy the following property. For each subset S of X with no more than \alpha|X| vertices, there are at least \varepsilon|S| vertices in X \S that are adjacent in \Gamma to exactly one verte in S. The construction of F is simple to specify, and each \Gamma \varepsilon 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 non equal color classes and similar properties.This has several applications and settles an open problem considered by various researchers.
Citation:
Noga Alon, Michael Capalbo, "Explicit Unique-Neighbor Expanders," focs, pp.73, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002
Usage of this product signifies your acceptance of the Terms of Use.