{"id":"arxiv/2610.30662","url":"https://arxiv.org/abs/2610.30662","tags":["math.CO"],"score":0,"title":"Aleshin graphs are expanders","domain":"math.CO","source":"arxiv","authors":["Olga Kharlampovich","Alina Vdovina"],"reviews":0,"subject":"math.CO","summary":"We prove that the Aleshin level graphs are two-sided expanders. We establish linear diameter bounds for Belaterra and Aleshin graph families. At level $n$, the diameters of the Bellaterra and undirected Aleshin graphs are a $|V_n|=2^n$. 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 $1-2\\sqrt2/3$ and an edge-expansion constant of at least $3-2\\sqrt2$, thereby establishing a Malyshev--Pak's Conjecture with explicit constants. An exact calculation at level ten also proves…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-22","reactions":{}}