The shortest common superpattern conjecture
Let be the length of the shortest word containing every pattern of length on at most letters. In the conjecture below, is a positive integer.
Shortest common superpattern conjecture. For any ,
This would show that the previously stated upper bound is sharp when . The source says that the matching lower bound is apparent in this case but that it has not been proved.
References
- A. Burstein, Peter Hästö and T. Mansour, “Packing patterns into words”, arXiv:math/0212343 (2003).
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.