2003/06/26 by Noga Alon, Michael Capalbo · 2 citations
Computer Science · Engineering · Neuroscience · #Advanced Graph Theory Research #graph theory and CDMA systems #Nuclear Receptors and Signaling
paper · doi:10.1109/sfcs.2002.1181884
openalex publication_date 2003/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.