The shortest common superpattern conjecture

Let n(l,m)n(l,m) be the length of the shortest word containing every pattern of length mm on at most ll letters. In the conjecture below, ll is a positive integer.

Shortest common superpattern conjecture. For any l1l\ge 1,

n(l,l)=l2l+1.n(l,l)=l^2-l+1.

This would show that the previously stated upper bound n(l,m)l(m1)+1n(l,m)\le l(m-1)+1 is sharp when m=lm=l. 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

No solutions have been posted yet.