Aleshin graphs are expanders
In the authors' words
We prove that the Aleshin level graphs are two-sided expanders. We establish linear diameter bounds for Belaterra and Aleshin graph families. At level , the diameters of the Bellaterra and undirected Aleshin graphs are a . This improves the quadratic diameter bounds of Malyshev and Pak to the correct order of growth. For the Aleshin graphs we obtain a normalized spectral gap of at least and an edge-expansion constant of at least , thereby establishing a Malyshev--Pak's Conjecture with explicit constants. An exact calculation at level ten also proves that the undirected Aleshin graphs are not Ramanujan for any .
Main resultLimitation the authors admit
Appeared: Friday, October 23. arXiv. Preprint, not yet peer-reviewed.