Monotone k-Shuffles in Long Permutations

Definitions and mathematical statement

For an integer $n\geq 1$, let $S_n$ be the set of permutations of $\{1,\ldots,n\}$, written as sequences. The standardization of a sequence of distinct numbers is the unique permutation with the same relative order. A consecutive factor of a permutation $\pi\in S_n$ is a contiguous sequence $\pi_i\pi_{i+1}\cdots\pi_j$, interpreted as a permutation by standardization.

Fix a positive integer $k$. A permutation $\tau\in S_{2k}$ is a $k$-shuffle of $12$ if its positions can be partitioned into $k$ pairs $\{a_r,b_r\}$, with $a_r<b_r$ and $\tau_{a_r}<\tau_{b_r}$ for every $r\in\{1,\ldots,k\}$. It is a $k$-shuffle of $21$ if such a partition exists with $\tau_{a_r}>\tau_{b_r}$ for every $r$. The pairs need not occupy adjacent positions. The supplied excerpt does not separately define a $k$-shuffle; this pairing interpretation is reconstructed from its stated perfect-matching characterization and requires confirmation against the report. We use positive $k$, since the excerpt does not specify whether $0\in{\mathbb{N}}$.

Conjecture (as supplied). For every integer $k\geq 1$, there exists an integer $N_k\geq 2k$ such that, for every integer $n\geq N_k$ and every $\pi\in S_n$, there is an index $i\in\{1,\ldots,n-2k+1\}$ for which \[ \operatorname{std}(\pi_i\pi_{i+1}\cdots\pi_{i+2k-1}) \] is a $k$-shuffle of $12$ or a $k$-shuffle of $21$.

For context, the supplied report defines a directed factor graph $\Gamma_k$ whose vertices are $S_{2k-1}$. Each $\sigma\in S_{2k}$ that is neither kind of $k$-shuffle contributes an edge \[ \operatorname{std}(\sigma_1\cdots\sigma_{2k-1}) \longrightarrow \operatorname{std}(\sigma_2\cdots\sigma_{2k}). \] The excerpt reports that the conjecture for a fixed $k$ is equivalent to acyclicity of $\Gamma_k$, and that acyclicity was confirmed through $k=5$. These are supplied contextual claims, not independently verified conclusions of this draft. The general conjecture is labelled open in the supplied record.

Short English statement

For each positive integer $k$, the conjecture asks whether every sufficiently long permutation has a consecutive block of $2k$ entries that can be partitioned into $k$ increasing pairs or into $k$ decreasing pairs. Entries within each pair may be separated in the block. The pairing definition is reconstructed from the supplied matching characterization and needs source confirmation.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005773$, title: Monotone k-Shuffles in Long Permutations; exact source problem code: catalogue entry. The supplied record labels the problem open and its statement corrected_verified; these are registry annotations, not independent verification by this draft.
• Mini-Workshop: Permutation Patterns (2024), Oberwolfach Reports, pp. 273--308, DOI 10.4171/owr/2024/6. Supplied source URL and literature-source link labelled "original OWR report": https://doi.org/10.4171/owr/2024/6.
• The supplied excerpt attributes Progress on k-shuffle conjecture to Andrew Elvey Price, joint work with David Bevan and Stefan Felsner. The registry gives proposed year 2024 but does not separately identify a proposer of the conjecture.
• Literature assessment dated exactly 2026-08-22: the supplied curation states that the conjecture remained unproved, with finite verification and structural progress, and that no later proof of the stated general conjecture was located. 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 excerpt invokes Tutte's perfect-matching theorem as reference [1], but the supplied record does not include the bibliographic entry for [1].