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.