Wall Structures on Symmetric-Group Cayley Graphs

Definitions and mathematical statement

For each integer $n\geq 1$, let $S_n$ be the group of permutations of $\{1,\ldots,n\}$. A generating set $X_n\subseteq S_n$ determines the undirected Cayley graph with edges joining $g$ to $gx$ for $x\in X_n\cup X_n^{-1}$. Its graph metric is the word metric \[ d_n(g,h)=\min\left\{k\geq 0:g^{-1}h=x_1\cdots x_k,\quad x_i\in X_n\cup X_n^{-1}\right\}. \] Here the empty product is the identity.

Under the usual unweighted convention, a wall on $S_n$ is an unordered partition $\{A,S_n\setminus A\}$ into two nonempty subsets. A wall structure $\mathcal W_n$ is a collection of walls such that every pair of points is separated by finitely many walls and every pair of distinct points is separated by at least one wall. Its wall metric is \[ d_{\mathcal W_n}(g,h)=\#\left\{W\in\mathcal W_n: g\text{ and }h\text{ lie in different parts of }W\right\}. \] The walls are partitions of the vertex set; no compatibility of their parts with edges or group invariance is imposed in this interpretation.

Question (supplied as Problem 2(i)). Do there exist an integer $D\geq 1$, generating sets $X_n\subseteq S_n$, wall structures $\mathcal W_n$, and nondecreasing functions \[ \rho_-,\rho_+:[0,\infty)\longrightarrow[0,\infty), \qquad \lim_{t\to\infty}\rho_-(t)=\infty, \] such that $|X_n|\leq D$ for every $n\geq 1$ and \[ \rho_-\left(d_n(g,h)\right) \leq d_{\mathcal W_n}(g,h) \leq \rho_+\left(d_n(g,h)\right) \qquad \text{for all }n\geq 1\text{ and }g,h\in S_n? \] The same control functions must work for every $n$; the comparison is through the identity map on each vertex set. This spells out the supplied clean statement's requirement of uniform coarse equivalence.

Unresolved source conventions. The supplied excerpt does not define a wall structure or specify whether walls may carry weights, have multiplicities, or be required to respect the group action. It also does not specify whether a wall pseudometric is permitted. The formulation above uses separating, unweighted collections of vertex partitions and the undirected word metric. These conventions and the identity-map interpretation require confirmation against the full source before mathematical acceptance.

Short English statement

Can all symmetric groups be given generating sets of uniformly bounded size and wall structures so that counting separating walls measures distance comparably to word length, with coarse control functions independent of the group? This draft uses the explicit conventions above. The supplied record labels the question open; that label is dated curation, not an independently verified conclusion.

Sources

• Local UnsolvedMath registry, permanent ID $30006611$, title Wall Structures on Symmetric-Group Cayley Graphs, exact source code catalogue entry; collection: Oberwolfach Reports Open Problems. The supplied assessment identifies the target as Problem 2(i). No proposer is identified for this target in the supplied record.
• Supplied report citation: Median Geometry and Applications (2026), Oberwolfach Reports, pp. 487--540, DOI 10.4171/owr/2026/8. Supplied source link: https://doi.org/10.4171/owr/2026/8.
• Supplied literature source, labelled "OWR report": https://ems.press/content/serial-article-files/53603.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels Problem 2(i) open and reports that it was explicitly posed as an open question about bounded-degree generating sets of symmetric groups with wall metrics coarsely equivalent to word metrics, with no resolution found. This is supplied dated literature triage, not an independently verified assessment; time-sensitive status and cited claims require independent verification.
• The supplied registry labels the statement corrected_verified and says that only formula delimiters, notation, grammar, and typography were repaired, preserving mathematical content and scope. This records the supplied editorial qualification and does not constitute mathematical review of this draft.