Orthogonal Knuth equivalence characterization by Sagan–Worley insertion

At least 4 years old · documented by

Let aa and bb be primed words, and let ∼shK\overset{\textsf{shK}}\sim be the transitive closure of the relation a∼okni(a)a\sim\mathsf{okn}_i(a) for all i∈Zi\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

a∼shKba\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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.