Smallest Colored Graph Representations of Permutation Groups

Definitions and mathematical statement

Let $\Omega$ be a set and let $\operatorname{Sym}(\Omega)$ denote the group of all bijections from $\Omega$ to itself. Let $G\leq\operatorname{Sym}(\Omega)$ be the prescribed permutation group. For a vertex-colored and edge-colored graph $\Gamma$, write $V(\Gamma)$ and $E(\Gamma)$ for its vertex and edge sets. Colorings are maps from these sets to respective sets of color labels. A color-preserving graph automorphism preserves incidence, all vertex and edge color labels, and edge directions if the graph is directed. Set \[ s(\Gamma)=|V(\Gamma)|+|E(\Gamma)|. \] The supplied optimization problem is to determine, for the prescribed $G\leq\operatorname{Sym}(\Omega)$, a smallest vertex-colored and edge-colored graph representing $G$, with size measured by $s$.

More explicitly, once the admissible graph model and the meaning of representation have been specified, let $\mathcal R(G,\Omega)$ denote the corresponding class of representing graphs. The requested graph $\Gamma_{\min}$ must satisfy \[ \Gamma_{\min}\in\mathcal R(G,\Omega),\qquad s(\Gamma_{\min})\leq s(\Gamma) \quad\text{for every }\Gamma\in\mathcal R(G,\Omega). \] This is a schematic formulation of the supplied target: the source record does not define $\mathcal R(G,\Omega)$. In particular, it does not state whether representation means that the color-preserving automorphism group is abstractly isomorphic to $G$, or that a specified action on a distinguished copy of $\Omega$ recovers the given permutation action. In the latter interpretation, whether automorphisms fixing that copy pointwise are allowed must also be specified. The record does not specify directed versus undirected graphs, permitted loops or parallel edges, available colors, or whether $\Omega$ and the representing graph must be finite. Consequently, neither the admissible class nor whether the size is an integer or a cardinal is fully determined. These qualifications must be resolved before this schematic optimization becomes a precise, single mathematical problem.

Short English statement

For a prescribed permutation group $G\leq\operatorname{Sym}(\Omega)$, find a graph with vertex and edge colors that represents $G$ and minimizes the number of vertices plus the number of edges. The supplied record leaves the meaning of representation, the graph conventions, and finiteness assumptions unresolved; these choices affect the optimization problem.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30004771$, titled "Smallest Colored Graph Representations of Permutation Groups," source problem code catalogue entry, in the Oberwolfach Reports Open Problems collection. The record lists proposed year 2021 and supplies no individual proposer.
• Supplied source citation: Computational Group Theory (2022), Oberwolfach Reports, DOI 10.4171/owr/2021/38, pp. 2027--2087. https://doi.org/10.4171/owr/2021/38. The literature-source list labels this reference "Oberwolfach Report 38/2021." The background describes these reports as documenting mathematical workshops and their open-problem discussions.
• Supplied literature reference: "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, states that general graph representations of permutation groups exist, and states that the minimum of $|V|+|E|$ for a prescribed group is not characterized and is recorded as open in the source report. This is supplied dated curation, not an independently verified literature assessment. The background expressly requests independent verification of time-sensitive status and cited claims.
• The registry labels the statement corrected_verified and reports that the official report was checked directly and that the cleaned statement preserves the mathematical target while restoring definitions and removing extraction artifacts or source-dependent wording. These are supplied provenance claims; no independent source consultation or verification is asserted here.