Malyshev–Pak conjecture on Aleshin graphs
Let be the undirected Aleshin level graph with . The Malyshev–Pak conjecture asserts that is an expander family: there exists a constant , independent of , such that for every and every subset with , the edge boundary satisfies . Equivalently, the normalized spectral gap of the graphs is bounded below by a positive constant independent of .
References
- Aleshin graphs are expanders — arXiv — Olga Kharlampovich, Alina Vdovina
Source: arXiv
Progress summary
A new preprint claims to prove that these graphs expand efficiently, settling the conjecture, but the claim has not been independently checked.
The Malyshev–Pak conjecture asserts that the Aleshin graphs are expanders, which would imply linear diameter growth. Malyshev and Pak’s earlier work presented this as an open conjecture.
Known results
- Malyshev and Pak: the Aleshin graphs have the upper bound .
- Malyshev and Pak: the conjectured expansion would imply diameter growth linear in , since the graph size is .
- Malyshev and Pak: related automata were shown not to produce expanders.
October 2026 claimed proof
Olga Kharlampovich and Alina Vdovina’s preprint claims explicit expansion bounds for the Aleshin graphs, thereby proving the Malyshev–Pak conjecture and giving linear diameter bounds. It also claims the graphs are not Ramanujan from level ten onward. The resolution remains unverified because the retrieved evidence is only the preprint.
Current status (as of October 2026): The conjecture has a claimed proof with explicit expansion and linear diameter bounds, but it remains an unverified claimed resolution.
Sources
Solutions 0
No solutions have been posted yet.