The staircase Young tableaux–sorting networks generating-function identity

From papers

For n2n\ge 2, let δn\delta_n be the staircase Young diagram, let SYT(δn)\operatorname{SYT}(\delta_n) be its standard Young tableaux, and let SNn\operatorname{SN}_n be the set of sorting networks on nn elements. For each tSYT(δn)t\in\operatorname{SYT}(\delta_n) and sSNns\in\operatorname{SN}_n, let ft(x1,,xn1)f_t(x_1,\ldots,x_{n-1}) and gs(x1,,xn1)g_s(x_1,\ldots,x_{n-1}) be the associated generating polynomials, and let σt\sigma_t and πs\pi_s denote the corresponding basis vectors. The staircase tableaux–sorting networks conjecture. For n2n\ge 2, one has the identity of vector-valued generating functions

tSYT(δn)ft(x1,,xn1)σt=sSNngs(x1,,xn1)πs.\sum_{t\in\operatorname{SYT}(\delta_n)} f_t(x_1,\ldots,x_{n-1})\,\sigma_t = \sum_{s\in\operatorname{SN}_n} g_s(x_1,\ldots,x_{n-1})\,\pi_s.

This is presented as an algebraic-combinatorial reformulation of the preceding distributional conjecture and is intended to clarify the relation between staircase Young tableaux and sorting networks. The supplied passage does not state a resolution, so the identity remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Elia Bisi, Fabio Deelan Cunden, Shane Gibbons and Dan Romik, “Sorting networks, staircase Young tableaux and last passage percolation”, arXiv:2003.03331 (2020).

Solutions 0

No solutions have been posted yet.