[Submitted on 5 Aug 2021]
Abstract: We prove that there exist bipartite, biregular Ramanujan graphs of every
degree and every number of vertices provided that the cardinalities of the two
sets of the bipartition divide each other. This generalizes a result of Marcus,
Spielman, and Srivastava and, similar to theirs, the proof is based on the
analysis of expected polynomials. The primary difference is the use of some new
machinery involving rectangular convolutions, developed in a companion paper.
We also prove the constructibility of such graphs in polynomial time in the
number of vertices, extending a result of Cohen to this biregular case.
From: Adam W. Marcus [view email]
Thu, 5 Aug 2021 11:46:09 UTC (22 KB)