Orthogonal Knuth equivalence characterization by Sagan–Worley insertion

From papers

Let aa and bb be primed words, and let shK\overset{\textsf{shK}}\sim be the transitive closure of the relation aokni(a)a\sim\mathsf{okn}_i(a) for all iZi\in\mathbb{Z}. Let PSWO(a)P^\mathsf{O}_{\textsf{SW}}(a) denote the insertion tableau under orthogonal Sagan–Worley insertion.

Orthogonal Knuth equivalence conjecture. Two primed words satisfy

ashKba\overset{\textsf{shK}}\sim b

if and only if

PSWO(a)=PSWO(b).P^\mathsf{O}_{\textsf{SW}}(a)=P^\mathsf{O}_{\textsf{SW}}(b).

This is presented as a consequence of the orthogonal Sagan–Worley insertion conjecture. The paper establishes that every primed word is orthogonally Knuth equivalent to the row word of its insertion tableau, but the converse characterization remains conjectural.

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

Eric Marberg, “Shifted insertion algorithms for primed words”, arXiv:2104.11437 (2023).

Solutions 0

No solutions have been posted yet.