Search

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 $\beta\in(0,1)$, we give a construction with the additional property that the left side of each graph has roughly $\beta$ 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., Comment: 22 pages, 1 figure

Analyzing nodal domains is a way to discern the structure of eigenvectors of operators on a graph. We give a new definition extending the concept of nodal domains to arbitrary signed graphs, and therefore to arbitrary symmetric matrices. We show that for an arbitrary symmetric matrix, a positive fraction of eigenbases satisfy a generalized version of known nodal bounds for un-signed (that is classical) graphs. We do this through an explicit decomposition. Moreover, we show that with high probability, the number of nodal domains of a bulk eigenvector of the adjacency matrix of signed a Erd\H{o}s-R\'enyi graph is $\Omega(n/\log n)$ and $o(n)$., Comment: 38 pages 1 figure