← All problems

Zhang–Kitaev equinumerosity conjecture for 213- and 321-avoiding permutations

1 year old · traced to

Let Snt\mathfrak{S}_n^t be the set of permutations of length nn that become the identity after tt applications of the stack-sorting operation, and let Snt(p)\mathfrak{S}_n^t(p) denote those that avoid the pattern pp. Zhang–Kitaev's conjecture. For every t≥1t\geq 1,

∣Snt(321)∣=∣Snt(213)∣.|\mathfrak{S}_n^t(321)|=|\mathfrak{S}_n^t(213)|.

The paper constructs a bijection proving this equality, so the conjecture is solved.

References
  1. Yang Li, Sergey Kitaev, Zhicong Lin and Jing Liu, “A bijection between 321- and 213-avoiding permutations preserving t-stack-sortability”, arXiv:2507.09187 (2025).

Progress summary

Refreshed
Open · solution reported

A 2025 paper claims a bijection proving the equality for every number of stack-sorting steps, together with a stronger statistical correspondence.

Zhang and Kitaev conjectured that the two classes of pattern-avoiding permutations have equal size after every number tt of stack-sorting steps. Yang Li, Sergey Kitaev, Zhicong Lin, and Jing Liu claim to settle this by constructing a bijection preserving tt-stack-sortability.

Known results

  • Simion and Schmidt: the case t=1t=1 was previously known.
  • Zhang and Kitaev: the equality was previously verified for t∈{n−1,n−2,n−3,n−4}t\in\{n-1,n-2,n-3,n-4\}.
  • The new theorem gives a refinement matching (fix⁡,drop⁡)(\operatorname{fix},\operatorname{drop}) with (bad⁡,des⁡)(\operatorname{bad},\operatorname{des}).

July 12, 2025 claimed bijective proof

The arXiv paper A bijection between 321- and 213-avoiding permutations preserving tt-stack-sortability states that its bijection Υ:Sn(321)→Sn(213)\Upsilon:\mathfrak{S}_n(321)\to\mathfrak{S}_n(213) restricts to the tt-stack-sortable subsets, implying ∣Snt(321)∣=∣Snt(213)∣|\mathfrak{S}_n^t(321)|=|\mathfrak{S}_n^t(213)| for every t≥1t\geq1. The claim is unverified in the retrieved sources.

Current status (as of October 2026): The equality is claimed solved for every t≥1t\geq1, but the claimed bijection has not been independently verified in the retrieved sources.

Sources

Solutions 0

No solutions have been posted yet.