Explicit bounded-degree unique-neighbor concentrators (Q2568494)

A bipartite graph \((I, O, E)\), where \(|O| \leq (1-c)|I|\) and \(c >0\) is an \((\alpha, \epsilon)\)-unique-neighbor concentrator, if for each subset \(S\) of \(I\) such that \(|S| \leq \alpha |I|\), there are at least \(\epsilon |S|\) vertices of \(O\) that are adjacent to exactly one vertex of \(S\). Unique-neighbor concentrators were used in the construction of self-routing networks, see \textit{S. Arora, F. T. Leighton and B. M. Maggs} [SIAM J. Comput. 25, No. 3, 600--625 (1996; Zbl 0852.68004)] (note it is referred incorrectly in the paper), and \textit{N. Pippenger} [J. Comput. Syst. Sci. 52, No. 1, 53--60 (1996; Zbl 0846.68006)]. The author shows that there is an infinite family of bounded-degree \((\alpha, \epsilon)\)-unique-neighbor concentrators for some \(\alpha > 0\) and \(\epsilon > 0\). The usual method of using the second largest eigenvalue breaks down, so the author comes up with a clever product of a fixed graph \(H\) on 44 vertices by a 44-regular Ramanujan graph \(\Lambda\). Indeed, \(\Lambda\) is any element of an infinite family constructed by \textit{A. Lubotzky, R. Phillips and P. Sarnak} [Combinatorica 8, No. 3, 261--277 (1988; Zbl 0661.05035)]. In order to show that the product is a unique-neighbor concentrator, some properties of the graph \(\Lambda\) are recalled, these were established by the second eigenvalue method, see \textit{N. Kahale} [J. Assoc. Comput. Mach. 42, No. 5, 1091--1106 (1995; Zbl 0885.68117)].