Bijections between permutations with k descents and k ascents in weak Bruhat order

NEW

Problem: For $w=w_1\cdots w_n\in S_n$, let $\operatorname{des}(w)=|\{i:w_i>w_{i+1}\}|$. Let

Interpret weak Bruhat order as the usual right weak order: $u\le v$ iff $v$ is obtained from $u$ by adjacent swaps $ab\mapsto ba$ with $a<b$, equivalently by inclusion of value-inversion sets. The conjecture asks: if $n\ge 2k+1$, $k\ge1$, then there is a bijection $\sigma:D_k\to A_k$ with $\sigma(w)\ge w$ for all $w\in D_k$.

Result: The conjecture is true.

Use the modified Foata–Strehl valley-hopping action. Put $w_0=w_{n+1}=\infty$. Each letter of $w$ is a peak, valley, double ascent, or double descent according as its two neighbors form $<x>$, $>x<$, $<x<$, or $>x>$. The Foata–Strehl orbits have the following standard structure: each orbit has a unique representative $v$ with no double descents; if $r=\operatorname{des}(v)$, then the double ascents of $v$ form a set $F$ of size

and the orbit is naturally indexed by subsets $S\subseteq F$, say $v_S$, with

Moreover, if $S\subseteq T$, then $v_S\le v_T$ in right weak order, because toggling an untoggled double ascent moves that letter left across smaller adjacent letters, a sequence of upward weak-order covers.

Fix one orbit. Elements in $D_k$ in this orbit correspond to subsets $S\subseteq F$ of size

Since $n\ge2k+1$,

Consider the bipartite graph between $j$-subsets and $(m-j)$-subsets of $F$, with edge $S\subseteq T$. Both sides have size $\binom mj$, and every vertex has degree $\binom{m-j}{j}$. Hence, by Hall’s theorem, there is a perfect matching $\mu$ with $S\subseteq \mu(S)$.

Define on this orbit

Then

so $\sigma(v_S)\in A_k$, and since $S\subseteq\mu(S)$, we have $\sigma(v_S)\ge v_S$. Doing this independently on every Foata–Strehl orbit gives the required global bijection $D_k\to A_k$.

Audit: the only numerical hypothesis used is $n\ge2k+1$; $A_k$ is exactly the descent class $n-1-k$; and the order relation is precisely the right weak Bruhat order generated by increasing adjacent swaps.

Citation: The orbit structure used is the classical modified Foata–Strehl action; see D. Foata and M.-P. Schützenberger, Théorie géométrique des polynômes eulériens, Lecture Notes in Mathematics 138, Springer, 1970; also T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Ch. 4. The exact conjectured bijection follows from these ingredients as shown above.