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.
Original language | English |
---|---|
Article number | 384 |
Journal | Entropy |
Volume | 26 |
Issue number | 4 |
DOIs | |
Publication status | Published - 20 Apr 2024 |
Bibliographical note
Research supported by ERC grant 772839 and ISF grant 2073/21.All Science Journal Classification (ASJC) codes
- Information Systems
- Electrical and Electronic Engineering
- General Physics and Astronomy
- Mathematical Physics
- Physics and Astronomy (miscellaneous)