REVIEW 2 cited by
Bipartite unique-neighbour expanders via Ramanujan graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
We construct an infinite family of bounded-degree bipartite unique-neighbour expander graphs with arbitrarily unbalanced sides. Although weaker than the lossless expanders constructed by Capalbo et al., our construction is simpler and may be closer to be implementable in practice due to the smaller constants. We construct these graphs by composing bipartite Ramanujan graphs with a fixed-size gadget in a way that generalizes the construction of unique neighbour expanders by Alon and Capalbo. For the analysis of our construction we prove a strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs. Our bound generalizes Kahale's average degree bound to bipartite Ramanujan graphs, and may be of independent interest. Surprisingly, our bound strongly relies on the exact Ramanujan-ness of the graph and is not known to hold for nearly-Ramanujan graphs.
Forward citations
Cited by 2 Pith papers
-
Explicit Lossless Vertex Expanders
For every epsilon and sufficiently large degree d, explicit d-regular graphs exist in which every small set S has at least (1-epsilon)d|S| distinct neighbors.
-
Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
An explicit infinite family of biregular graphs is shown to have (3/5 - epsilon)-two-sided unique-neighbor expansion, the first to beat the spectral 0.5d barrier.
Discussion (0). Continue with ORCID to comment.