The Aleshin graph at level 
is the undirected multigraph
on the 
binary words of length 
obtained by joining each word 
to 
, 
, and 
and retaining all labels and edge
multiplicities. The permutations are defined
recursively, for 
,
by 
, 
, 
, 
, and 
, with all three fixing the empty word
(Kharlampovich and Vdovina 2026). The undirected convention uses the generating list
and has degree
six, counting a graph loop twice.
Kharlampovich and Vdovina (2026) report a two-sided normalized spectral gap of at least 
,
an undirected graph diameter at most 
, and a directed diameter at most 
. Thus these diameters have order 
, where 
is big-Theta notation.
They also report that the undirected graphs are not Ramanujan
for 
.
These claims use a recent Bellaterra graph result
and require further independent verification. Kharlampovich and Vdovina (2026) credit
ChatGPT with assistance in the non-Ramanujan proof.
