← All problems

Malyshev–Pak conjecture on Aleshin graphs

Let AnA_n be the undirected Aleshin level graph with ∣V(An)∣=2n|V(A_n)|=2^n. The Malyshev–Pak conjecture asserts that (An)n≥1(A_n)_{n\ge 1} is an expander family: there exists a constant c>0c>0, independent of nn, such that for every nn and every subset S⊆V(An)S\subseteq V(A_n) with 0<∣S∣≤∣V(An)∣/20<|S|\le |V(A_n)|/2, the edge boundary satisfies ∣∂AnS∣≥c∣S∣|\partial_{A_n}S|\ge c|S|. Equivalently, the normalized spectral gap of the graphs AnA_n is bounded below by a positive constant independent of nn.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

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 diam⁡(An)=O(n2)\operatorname{diam}(A_n)=O(n^2).
  • Malyshev and Pak: the conjectured expansion would imply diameter growth linear in nn, since the graph size is 2n2^n.
  • 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.