Structural Decomposition of Separable Permutation Subclasses

Definitions and mathematical statement

For a positive integer $n$, a permutation of length $n$ is a sequence containing each element of $\{1,\ldots,n\}$ exactly once. A permutation $\pi$ contains a pattern $\sigma$ if some subsequence of $\pi$ has the same relative order as $\sigma$; otherwise it avoids $\sigma$. A permutation class is a collection closed under taking patterns. Write $\operatorname{Av}(B)$ for the class avoiding every pattern in $B$. The separable permutations form the class \[ \mathcal S=\operatorname{Av}(2413,3142). \] Here a subclass means a permutation class contained in the specified class, with no finite-basis assumption.

For permutations $\alpha$ and $\beta$ of lengths $a$ and $b$, respectively, define \[ \alpha\oplus\beta=(\alpha_1,\ldots,\alpha_a,a+\beta_1,\ldots,a+\beta_b), \qquad \alpha\ominus\beta=(b+\alpha_1,\ldots,b+\alpha_a,\beta_1,\ldots,\beta_b). \] For classes $A,B$, let $A\oplus B=\{\alpha\oplus\beta:\alpha\in A,\ \beta\in B\}$, and define $A\ominus B$ analogously. A class $D$ is sum closed if $D\oplus D\subseteq D$, and skew closed if $D\ominus D\subseteq D$.

For a permutation $\sigma$ of length $k$ and nonempty permutations $\tau_1,\ldots,\tau_k$, the inflation $\sigma[\tau_1,\ldots,\tau_k]$ replaces each entry $\sigma_i$ by a consecutive block order-isomorphic to $\tau_i$, with the blocks ordered in value according to $\sigma$. For classes $X,U$, write \[ X[U]=\{\sigma[\tau_1,\ldots,\tau_k]:k\geq1,\ \sigma\in X\cap S_k,\ \tau_i\in U\text{ for all }i\}. \] Set \[ X=\operatorname{Av}(2413,3142,2143,3412). \]

Structural conjecture (Conjecture 3 in the supplied excerpt). For every permutation class $C\subseteq\mathcal S$, at least one of the following holds:

1. $C$ is sum closed or skew closed, or there are finitely many permutation classes $D_1,\ldots,D_m$, with $m\geq1$, such that \[ C=\bigcup_{i=1}^{m}D_i, \qquad \text{each }D_i\text{ is sum closed or skew closed}; \]
2. there exists a permutation class $U\subsetneq C$ such that $C\subseteq X[U]$.

The alternatives are not required to be mutually exclusive. The finite-union clause above reads "such classes" as allowing the closure type to vary among the constituents; the excerpt does not explicitly settle whether a common closure type was intended. The displayed definitions use nonempty permutations and nonempty inflation blocks. The supplied record does not specify its convention for the empty permutation, empty classes, or empty inflation blocks; these boundary conventions require confirmation before accepting the formulation.

Supplied context and qualifications. For a permutation class $D$, its ordinary generating function is $F_D(z)=\sum_{n\geq0}d_nz^n$, where $d_n$ counts its length-$n$ members and the constant term depends on the empty-permutation convention. Rationality means membership in ${\mathbb{Q}}(z)$. A symmetry of a permutation class is its image under a symmetry of permutation plots, generated by reversing positions, complementing values, and taking inverses. Let $\mathfrak A$ be the set of distinct symmetry images of $\operatorname{Av}(231)$.

The excerpt attributes to Albert, Atkinson and Vatter, as its Theorem 2, the assertion \[ C\subseteq\mathcal S,\qquad (\forall A\in\mathfrak A)\ A\nsubseteq C \quad\Longrightarrow\quad F_C(z)\in{\mathbb{Q}}(z). \] Thus the supplied condition excludes containment of every individual symmetry image. The excerpt presents the converse rationality question as unresolved and proposes the structural conjecture as a possible route toward characterising nonrationality.

The excerpt also states, as Theorem 4 and as a slight reinterpretation of Theorem 5.1 of Bóna [3], that a permutation class satisfying \[ C\oplus C\subseteq C, \qquad \{1\}\ominus C\subseteq C \] has a nonrational generating function, where $1$ is the unique permutation of length one. It calls $\operatorname{Av}(231)$ the smallest class satisfying these hypotheses. These are supplied contextual assertions, not independently verified here; their boundary hypotheses, including nonemptiness of $C$, are not explicit in the record. The excerpt says that the proof of Conjecture 3 remains incomplete and that many required steps can use methods similar to those of reference [2].

A subsequent, separate discussion asks whether every proper subclass of $\mathcal S$ has generating function in a field apparently intended to be ${\mathbb{Q}}(z,\sqrt{1-4z})$, motivated by observations concerning subclasses containing a symmetry of $\operatorname{Av}(231)$. The radical notation is corrupted in the supplied extraction. The excerpt reports that this universal assertion is false, but ends before supplying the enumeration or counterexample. This incomplete contextual discussion is not an additional conjecture asserted by this draft.

Short English statement

The conjecture asks whether every class of separable permutations is a finite union of classes closed under direct sums or skew sums, or can be built by inflating members of a fixed avoidance class using permutations from a strictly smaller subclass. The source reports an incomplete proof and supplies related rationality results. Empty-object conventions, the finite-union interpretation, and incomplete contextual references require review.

Sources

• Local registry: data/unsolvedmath/problems.json, permanent UnsolvedMath ID $30005766$, source problem code catalogue entry, title Structural Decomposition of Separable Permutation Subclasses. The supplied record gives proposed year 2024 and no named proposer.
• Supplied report citation: Mini-Workshop: Permutation Patterns (2024), Oberwolfach Reports, pp. 273--308, DOI 10.4171/owr/2024/6. Supplied literature-source label: "original OWR report." https://doi.org/10.4171/owr/2024/6. The excerpt identifies the target as Conjecture 3; no conjecture-specific page is supplied.
• Supplied literature-source label: "separable-subclass theorem." https://arxiv.org/abs/1007.1014. The excerpt attributes its Theorem 2 to Albert, Atkinson and Vatter [2]. Full bibliographic details and the identification of the linked paper with the excerpt's numbered reference require confirmation.
• The excerpt attributes its Theorem 4 to a slight reinterpretation of Theorem 5.1 of Bóna [3]. The supplied record contains no full citation or URL for [3].
• Literature assessment dated exactly 2026-08-22: the supplied curation labels the problem "partially solved," reports rationality when every symmetry image of $\operatorname{Av}(231)$ is excluded, and describes the converse question as unresolved and the structural conjecture as incomplete. This is supplied dated curation, not an independently verified literature assessment.
• The registry labels the statement corrected_verified and records a claim that the official report was checked directly. That claim is supplied provenance; no source visit or independent verification is claimed in this draft.