The shortest common superpattern conjecture
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.
Sources & referencesView supporting material
Primary source
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
Sign in to submit a solution.
No solutions have been posted yet.