Explicit unique-neighbor expanders

Noga Alon, Michael Capalbo

Research output: Contribution to journalConference articlepeer-review

20 Scopus citations

Abstract

We present a simple, explicit construction of an infinite family F of bounded-degree 'unique-neighbor' expanders Γ; i.e., there are strictly positive constants α and ε, such that all Γ = (X, E(Γ)) ∈ F satisfy the following property. For each subset S of X with no more than α|X| vertices, there are at least ε|S| vertices in X\S that are adjacent in Γ to exactly one vertex in S. The construction of F is simple to specify, and each Γ ∈ 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.

Original languageEnglish (US)
Pages (from-to)73-79
Number of pages7
JournalAnnual Symposium on Foundations of Computer Science - Proceedings
StatePublished - 2002
Externally publishedYes
EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
Duration: Nov 16 2002Nov 19 2002

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Explicit unique-neighbor expanders'. Together they form a unique fingerprint.

Cite this