Expander-family conjecture for undirected prefix-reversal graphs

From papers

Let Pm(n)\mathbb{P}_m(n) be the undirected prefix-reversal graph, which is 2n2n-regular for m>1m>1. A sequence of regular graphs is an expander family if there exists ε>0\varepsilon>0 such that every graph in the sequence has expansion ratio at least ε\varepsilon. Expander-family conjecture. Given n1n\geq1, the sequence of 2n2n-regular graphs

{Pm(n)}m>1\{\mathbb{P}_m(n)\}_{m>1}

indexed by mm is an expander family of graphs. The conjecture concerns expansion as mm varies with nn fixed; the source provides no resolution.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Saúl A. Blanco and Charles Buehrle, “On the spectra of prefix-reversal graphs”, arXiv:2506.08345 (2025).

Solutions 0

No solutions have been posted yet.