Super-Expanding Cayley Graphs of Symmetric Groups

Definitions and mathematical statement

For each integer $n\geq 2$, let $G_n=\operatorname{Sym}(n)$ be the group of all permutations of $\{1,\ldots,n\}$. A symmetric generating set is a set $X_n\subseteq G_n\setminus\{e\}$ satisfying $X_n^{-1}=X_n$ and $\langle X_n\rangle=G_n$. Its undirected Cayley graph has vertex set $G_n$, with $g$ adjacent to $gs$ for $s\in X_n$. Symmetry and exclusion of the identity are explicit graph conventions for this draft; a uniformly bounded generating set can be symmetrized without losing uniform boundedness. Omitting the trivial group at $n=1$ does not affect the family question.

A Banach space $E$ is uniformly convex if, for every $0<\varepsilon\leq 2$, there exists $\delta>0$ such that $\|u\|_E,\|v\|_E\leq 1$ and $\|u-v\|_E\geq\varepsilon$ imply $\|(u+v)/2\|_E\leq 1-\delta$.

The supplied record does not define super-expander. Under the uniform Banach-space Poincaré interpretation, the question is whether there exist an integer $D\geq 1$ and symmetric generating sets $(X_n)_{n\geq 2}$, with $|X_n|\leq D$ for every $n$, such that, for every uniformly convex Banach space $E$, there exists a constant $C_E\in(0,\infty)$ for which every $n\geq 2$ and every map $f:G_n\to E$ satisfy \[ \frac{1}{|G_n|^2}\sum_{g,h\in G_n}\|f(g)-f(h)\|_E^2 \leq \frac{C_E}{|G_n|\,|X_n|} \sum_{g\in G_n}\sum_{s\in X_n}\|f(g)-f(gs)\|_E^2. \] The generating sets must be chosen independently of $E$, whereas $C_E$ may depend on $E$ but not on $n$ or $f$. This gives uniformly bounded degrees and vertex counts $|G_n|=n!$ tending to infinity; taking $E={\mathbb{R}}$ includes the ordinary expander requirement.

This is an explicit interpretation requiring source confirmation. The supplied text does not determine whether its intended definition instead requires ordinary expansion together with failure of uniform coarse embedding into every uniformly convex Banach space. No equivalence between these formulations is asserted here. The source's sentence about whether "the converse holds" has no identifiable antecedent in the supplied excerpt and is not imposed as a further mathematical assertion.

Short English statement

Can one choose uniformly bounded generating sets for every symmetric group so that the resulting Cayley graphs form a family of super-expanders? The displayed formulation requires uniform Poincaré inequalities for maps into each uniformly convex Banach space. The source does not specify its definition of super-expansion, so this interpretation requires human review.

Sources

• Local problem registry, permanent UnsolvedMath ID $30005884$, title Super-Expanding Cayley Graphs of Symmetric Groups, exact source code catalogue entry. The record belongs to the Oberwolfach Reports Open Problems collection and gives proposed year 2024; no individual proposer is supplied.
• Supplied report citation: Mini-Workshop: Growth and Expansion in Groups (2024), Oberwolfach Reports, pp. 1005--1040, DOI 10.4171/owr/2024/17. https://doi.org/10.4171/owr/2024/17. The record attributes the extracted question to this report but supplies no exact page or named speaker for the passage.
• Supplied literature source, labelled "OWR report": https://oa.tib.eu/renate/server/api/core/bitstreams/5c03f705-7680-4cb6-b7cd-653d4b29494d/content.
• Supplied literature source, labelled "Kassabov expanders": https://arxiv.org/abs/math/0505624. The source passage attributes bounded-size generating sets giving ordinary expanders for the symmetric groups to Kassabov and cites this background result as reference [13]; the complete report entry for [13] is not supplied.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that Kassabov constructed ordinary expanders using bounded-size generating sets, while the super-expander question remains open. This is supplied dated curation, not an independently verified literature assessment. The background explicitly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified, explaining that only formula delimiters, notation, grammar, and typography were repaired while mathematical content and scope were preserved. This supplied editorial label does not verify the interpretation of super-expansion used in this draft.