Return to Answer

There the problem is to find a string that contains all subsets of $\Sigma$ as substrings of $|\Sigma|$ consecutive letters. Note two differences: only the maximal case (all subsets), and the substrings are not allowed to be longer than $|\Sigma|$. In the current question such solutions are allowed, for example using substring $1234245$ for the subset $12345$.

There the problem is to find a string that contains all subsets $S \subseteq\Sigma$ as substrings of length $|S|$. Note two differences: only the maximal case (all subsets), and the substrings have to be of minimal length $|S|$. In the current question longer substrings are allowed, for example using substring $1234245$ for the subset $12345$.

Anyway, for this version and $m=1,\ldots,5$ they list solutions $$1, 12, 1231, 12342413, 1234512413524.$$ They also prove asymptotic lower and upper bounds of $(2/\pi m)^{1/2}2^m$ and $(2/\pi)2^m$, respectively.

Anyway, for this version and $m=1,\ldots,5$ Lipski lists solutions $$1, 12, 1231, 12342413, 1234512413524.$$ He also proves asymptotic lower and upper bounds of $(2/\pi m)^{1/2}2^m$ and $(2/\pi)2^m$, respectively.

Previous research on a similar problem

A closely related problem is found in Lipski (1978), "On strings containing all subsets as substrings", Discrete Mathematics, 21(3), 253-259.

There the problem is to find a string that contains all subsets of $\Sigma$ as substrings of $|\Sigma|$ consecutive letters. Note two differences: only the maximal case (all subsets), and the substrings are not allowed to be longer than $|\Sigma|$. In the current question such solutions are allowed, for example using substring $1234245$ for the subset $12345$.

Anyway, for this version and $m=1,\ldots,5$ they list solutions $$1, 12, 1231, 12342413, 1234512413524.$$ They also prove asymptotic lower and upper bounds of $(2/\pi m)^{1/2}2^m$ and $(2/\pi)2^m$, respectively.