The edge-isoperimetric conjecture for the permutahedron at size 6(n+1)/36^{(n+1)/3}

Let Perm(n)\operatorname{Perm}(n) be the permutahedron graph, and let ik(G)i_k(G) denote the minimum edge-expansion among subsets of GG of size kk. Set

k=6n+13.k=6^{\frac{n+1}{3}}.

Edge-isoperimetric conjecture for the permutahedron.

ik(Perm(n))=n+131.i_k\bigl(\operatorname{Perm}(n)\bigr)=\frac{n+1}{3}-1.

This conjecture asserts that the heuristic construction using a Cartesian product of copies of the 66-cycle gives the optimal edge expansion at this scale. The surrounding discussion does not provide a proof or a resolution.

Sources & referencesView supporting material

Primary source

Maurício Collares, Joseph Doolittle and Joshua Erde, “The evolution of the permutahedron”, arXiv:2404.17260 (2026).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.