Realizable Standard Young Tableaux

Abstract

Given two vectors $u$ and $v$, their outer sum is given by the matrix $A$ with entries $A_{ij}=u_i+v_j$. If the entries of $u$ and $v$ are increasing and sufficiently generic, the total ordering of the entries of the matrix is a standard Young tableau of rectangular shape. We call rectangular standard Young tableaux arising in this way realizable. The set of realizable tableaux was defined by Mallows and Vanderbei for studying a deconvolution algorithm, but we show they have appeared in many other contexts including sorting algorithms, quantum computing, random sorting networks, reflection arrangements, fiber polytopes, and Goodman and Pollack's theory of allowable sequences. In our work, we prove tight bounds on the asymptotic number of realizable rectangular tableaux. We also derive tight asymptotics for the number of realizable allowable sequences, which are in bijection with realizable staircase-shaped standard Young tableaux with the notion of realizability coming from the theory of sorting networks.

17 pages