Some Questions — Question 8

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple vertex-transitive graph, with maximum degree at most $d$. Its edge-expansion constant is the minimum of $|E(A,V\setminus A)|/|A|$ over nonempty sets $A$ of size at most $|V|/2$. For a permutation $\sigma$ of $V$, define its adjacency error and distance to the automorphism group by \[ e_G(\sigma)=\frac{|\sigma(E)\mathbin{\triangle}E|}{|V|},\qquad a_G(\sigma)=\min_{\tau\in\operatorname{Aut}(G)} \frac{|\{v:\sigma(v)\ne\tau(v)\}|}{|V|}. \] Here $\sigma(E)$ is the set of unordered pairs obtained by applying $\sigma$ to both endpoints of each edge.

For fixed $d$ and $h>0$, is the following uniform stability statement true? For every $\varepsilon>0$ there exists $\delta>0$ such that, for every such graph with expansion at least $h$, \[ e_G(\sigma)<\delta\quad\Longrightarrow\quad a_G(\sigma)<\varepsilon. \] Equivalently, along any bounded-degree vertex-transitive expander family, permutations making a vanishing fraction of edge errors are a vanishing normalized Hamming distance from genuine automorphisms.

The approximating automorphism may vary with the permutation and graph, but the error threshold cannot depend on graph order. Counting a few incorrect edges alone does not require a permutation to be close pointwise to the identity; it may approximate any automorphism. Expansion and vertex transitivity are both hypotheses of the intended question.

Short English statement

Must an almost adjacency-preserving permutation of a vertex-transitive expander be close to a genuine automorphism?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200008 (AMR-011-0008), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Abert - Some questions (pdf) (2010), Question 8. Original source indexed by AMR-011-0008. https://www.renyi.hu/~abert/questions.pdf.