Non-Messing-Up++: Diagonal Sorting and Young Tableaux

Summary

# Non-Messing-Up++: Diagonal Sorting and Young Tableaux _Date: 2026-03-13_ _Updated: 2026-03-18_ ___ I've been sitting on this for too long. Happened upon this idea while trying to figure out parallel sorting techniques, using SIMD "in-register" sorting as a primitive. Proof fleshed out by Opus 4.6 (and LaTeX-ified, which is important for making it look correct). I found Claude was pretty decent at poking holes in my reasoning, though it wasn't great at coming up with counterexamples. And hey, better to be open and wrong at this stage than to be closed. The decreasing form (Lemma 2) is not particularly interesting to me, because only the increasing form is needed for a parallel SIMD mergesort strategy :) # Anti-Diagonal Sort Preserves the Young Tableau Property ### Notes Why anti-diagonal instead of diagonal? I'm pretty sure that diagonal vs antidiagonal sorting would be symmetric in the following, just that I like things to start from the left if possible. I think there may be an issue with diagonal sorting in that regard, though Young Tableau obviously implies diagonals are already sorted with rows/cols. Of course, antidiagonal also just sounds cooler. The theorem below seems rather simple, so I'm a bit suspicious I didn't find it stated this way already. The closest neighbors I found are the classical non-messing-up theorem for row/column sorting and the products-of-two-chains literature, though I don't understand the latter well enough to know whether this is already hiding in it somewhere. Maybe I should call this thing "non-messing-up++"? Regardless, this was a fun little exercise in capturing some ideas more rigorously -- ideas which an algorithm will be predicated on. ## Conventions Throughout, $G$ is an $n \times n$ grid of distinct real numbers, indexed by $(r, c)$ for $r, c \in \{0, \ldots, n-1\}$, with $r$ increasing downward and $c$ increasing rightward. - **Rows** are sorted left to right: $G[r][c] < G[r][c+1]$ - **Columns** are sorted top to bottom: $...