Unique-neighbor Expanders with Better Expansion for Polynomial-sized Sets

A (d 1 , d 2 )-biregular bipartite graph G = (L ∪ R, E) is called left-(m, δ) unique-neighbor expander iff each subset S of the left vertices with |S| ≤ m has at least δd 1 |S| unique-neighbors, where unique-neighbors mean vertices with exactly one neighbor in S. We can also define right/two-sided expanders similarly. In this paper, we give the following three strongly explicit constructions of unique-neighbor expanders with better unique-neighbor expansion for polynomial-sized sets, while sufficient expansion for linear-sized sets is also preserved:

• Two-sided (n 1/3-ε , 1 -ε) lossless expanders for arbitrary ε > 0 and aspect ratio.

• Left-(Ω(n), 1 -ε) lossless expanders with right-(n 1/3-ε , δ) expansion for some δ > 0.

• Two-sided-(Ω(n), δ) unique-neighbor expanders with two-sided-(n Ω(1) , 1/2 -ε) expansion.

The second construction exhibits the first explicit family of one-sided lossless expanders with unique-neighbor expansion for polynomial-sized sets from the other side and constant aspect ratio. The third construction gives two-sided unique-neighbor expanders with additional (1/2ε) unique-neighbor expansion for two-sided polynomial-sized sets, which approaches the 1/2 requirement in Lin and Hsieh (arXiv:2203.03581).

Our techniques involve tripartite product recently introduced by Hsieh et al (STOC 2024), combined with a generalized existence argument of biregular graph with optimal two-sided unique-neighbor expansion for almost all degrees. We also use a new reduction from large girth/bicycle-freeness to vertex expansion, which might be of independent interest.