pipette
ESEspañol

Aleshin graphs are expanders

Olga Kharlampovich, Alina Vdovina

Preprint

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.