Explicit two-sided unique-neighbor expanders

MaRDI QIDQ6508670arXivFDO

Authors Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes

Published in arXiv

Mathematics Subject Classification ID

Expander graphs (05C48)

Abstract: We study the problem of constructing explicit sparse imbalanced bipartite unique-neighbor expanders. For large enough $d_1$ and $d_2$, we give a strongly explicit construction of an infinite family of $(d_1,d_2)$-biregular graph (assuming $d_{1}leq{d}_2$) where all sets $S$ with fewer than $1/d_1^3$ fraction of vertices have $Omega(d_{1}cdot|S|)$ unique-neighbors. Further, for each $$, we give a construction with the additional property that the left side of each graph has roughly $$ fraction of the total number of vertices. Our work provides the first two-sided construction of imbalanced unique-neighbor expanders, meaning small sets contained in both the left and right side of the bipartite graph exhibit unique-neighbor expansion. Our construction is obtained from the ``line product of a large small-set edge expander and a sufficiently good constant-sized unique-neighbor expander, a product defined in the work of Alon and Capalbo.

This page was built for publication: Explicit two-sided unique-neighbor expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6508670)