Cutting-distance conjecture for even k-ary words

About 1 year old · traced to

For a kk-ary word WW, let c(W)c(W) be the minimum number of cuts needed to partition WW into consecutive blocks that can be permuted to form a shuffle square. A word is even if every letter occurs an even number of times.

Cutting-distance conjecture. For each k⩾2k\geqslant2, every even kk-ary word WW satisfies

c(W)⩽k.c(W)\leqslant k.

The binary case is posed separately with the stronger bound c(W)⩽2c(W)\leqslant2, while the proposed generalization is compatible with the known ternary example having cutting distance 33.

References

Primary source

Jarosław Grytczuk, Bartłomiej Pawlik and Andrzej Ruciński, “Shuffle squares and ordered nest-free graphs”, arXiv:2503.22043 (2025).

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.