Some Questions — Question 7

Definitions and mathematical statement

For a finite simple graph $G=(V,E)$ define its edge-expansion constant by \[ h(G)=\min_{0<|A|\leq |V|/2} \frac{|\{\{u,v\}\in E:u\in A,\ v\notin A\}|}{|A|}. \] A graph is vertex-transitive if its automorphism group acts transitively on $V$. For two graphs on equally many vertices, define their normalized edge-edit distance by \[ \operatorname{ed}(G,H)=\frac1{|V(G)|}\min_f |f(E(G))\mathbin{\triangle} E(H)|, \] where $f:V(G)\to V(H)$ ranges over bijections and sends each edge to the corresponding unordered pair.

Suppose $(G_j)$ and $(H_j)$ are vertex-transitive graphs with equal orders tending to infinity, uniformly bounded degrees, and a common positive lower bound on their expansion constants. If $\operatorname{ed}(G_j,H_j)\to0$, must $G_j$ and $H_j$ be isomorphic for all sufficiently large $j$? The source also asks the restricted question where both sequences consist of Cayley graphs of finite groups.

The bound on degrees and the positive expansion constant are uniform in $j$. Isomorphism means an exact adjacency-preserving bijection, although the bijections witnessing small edit distance may depend on $j$. The normalization is by vertices, appropriate for bounded-degree graphs; normalization by all vertex pairs would make this hypothesis vacuous for sparse graphs. Thus the problem asks for rigidity from a genuinely vanishing fraction of edge errors.

Short English statement

Are two bounded-degree vertex-transitive expander families eventually exactly isomorphic whenever their edge-edit distance tends to zero?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 1200007 (AMR-011-0007), 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 7. Original source indexed by AMR-011-0007. https://www.renyi.hu/~abert/questions.pdf.