Compact Graph Representations of Permutation Groups

Definitions and mathematical statement

The supplied record concerns compact graph representations of permutation groups. For the natural finite interpretation of its size questions, let $\Omega$ be a finite set, put $n=|\Omega|$, and let $G\leq\operatorname{Sym}(\Omega)$, where $\operatorname{Sym}(\Omega)$ is the group of all permutations of $\Omega$. Finiteness is implicit in the requested size and algorithmic bounds, rather than explicitly stated in the source text.

For a finite graph representation $\Gamma$ with vertex set $V(\Gamma)$ and edge set $E(\Gamma)$, the specified size measure is \[ s(\Gamma)=|V(\Gamma)|+|E(\Gamma)|. \] The supplied record does not define what constitutes a graph representation of the given permutation action. In particular, it does not specify whether graphs are directed, colored, or labeled, whether auxiliary vertices are allowed, or whether the group must be the full automorphism group, an induced permutation group on a distinguished subset, or some other associated group. These choices must be fixed before the following questions have a unique mathematical meaning.

Requested classification and constructions. Determine which classes of permutation groups admit graph representations of size of order $n$, $n\log n$, or a low-order polynomial in $n$. If "of order" means an asymptotic upper bound, the corresponding uniform formulation for a class $\mathcal C$ of finite permutation actions and a specified representation convention is \[ \begin{gathered} \exists C>0\;\exists n_0\geq 2\;\forall (G,\Omega)\in\mathcal C,\\ |\Omega|\geq n_0\ \Longrightarrow\ \exists\Gamma\text{ representing }(G,\Omega) \text{ with }s(\Gamma)\leq C f(|\Omega|), \end{gathered} \] where the requested scales are \[ f(n)=n,\qquad f(n)=n\log n,\qquad f(n)=n^d. \] For the polynomial scale, $d$ would have to be a fixed exponent independent of the individual action; neither its permitted range nor the meaning of "low-order" is supplied. The upper-bound interpretation of "of order" is also unresolved. The displayed formulation concerns sufficiently large degrees and imposes no additional small-degree boundary condition.

Develop methods to construct the requested representations and fast algorithms in this setting. The record specifies neither the input encoding of $G$, nor the precise algorithmic tasks, nor a running-time bound or computational model.

Supergroup question. Determine whether low-index supergroups can admit compact graph representations when the original group cannot. Under the same-domain interpretation, this concerns groups \[ G\leq H\leq\operatorname{Sym}(\Omega),\qquad [H:G]=|H|/|G|. \] The record does not specify whether this same-domain interpretation is required, what bound makes the index "low", which compactness scale is intended, or whether the requested existence is universal over a class, conditional on further hypotheses, or illustrated by particular families. Consequently, this part remains a research question requiring these qualifications before it can be expressed as a definite quantified assertion.

Short English statement

Classify permutation groups that have small graph representations, construct such representations, and develop fast algorithms for them. Also investigate whether a supergroup of small index can have a compact representation when the original group does not. The supplied record leaves the representation model, several size thresholds, and the algorithmic and supergroup quantifiers unspecified.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004772$, title Compact Graph Representations of Permutation Groups, source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The proposed year is recorded as 2021; no proposer is named.
• Supplied report citation: Computational Group Theory (2022), Oberwolfach Reports, pp. 2027--2087, DOI 10.4171/owr/2021/38. https://doi.org/10.4171/owr/2021/38. The literature-source list labels this reference "Oberwolfach Report 38/2021". The supplied year labels are retained without resolving their relationship.
• Supplied literature source: Permutation group algorithms based on directed graphs. https://doi.org/10.1016/j.jalgebra.2021.06.015.
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem open and states that only general constructions and selected lower bounds are available, while the requested classification, construction methods, algorithms, and low-index supergroup questions remain open in general. This is supplied dated curation, not an independently verified literature assessment. The background explicitly calls it dated literature triage derived from the supplied OWR curation and requests independent verification of time-sensitive status and cited claims.
• The registry gives the statement status as corrected_verified and reports that the official Oberwolfach report was checked directly and that the cleaned statement preserves the complete mathematical target while restoring definitions and removing extraction artifacts or source-dependent wording. These are supplied provenance claims; this draft does not independently verify them or claim to have visited either reference.