Bipartite Unique Neighbour Expanders via Ramanujan Graphs

Area of Science:

• Graph Theory
• Theoretical Computer Science
• Combinatorics

Background:

• Expander graphs are crucial in computer science and mathematics.
• Previous constructions of lossless expanders have limitations in simplicity and practical implementation.
• Unique neighbor expander graphs offer specific properties for network design.

Purpose of the Study:

• To construct an infinite family of bipartite unique neighbor expander graphs.
• To achieve graphs with arbitrarily unbalanced sides and bounded degrees.
• To offer a simpler and potentially more implementable alternative to existing expander constructions.

Main Methods:

• Composing bipartite Ramanujan graphs with a fixed-size gadget.
• Generalizing constructions by Alon and Capalbo for unique neighbor expanders.
• Proving a strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs.

Main Results:

• An infinite family of bounded-degree bipartite unique neighbor expander graphs with arbitrarily unbalanced sides was successfully constructed.
• A novel, strong upper bound on average degrees in small induced subgraphs of bipartite Ramanujan graphs was proven.
• The new construction is simpler and has smaller constants, suggesting improved practical implementability.

Conclusions:

• The new construction provides a valuable tool for theoretical computer science and network design.
• The proven average degree bound is a significant theoretical contribution, relying crucially on the exact Ramanujan property.
• This work advances the understanding and construction of expander graphs with specific desirable properties.