Sets of symbols contained in contiguous substrings

Question

Let $\Sigma$ be an alphabet with $m$ different symbols.

Let $s$ be a string in $\Sigma$ of length $n$. Assume that every symbol in $\Sigma$ occurs in $s$ at least once (so $n\geq m$).

Let $\mathrm{Sub}(s)$ be the set of contiguous substrings of $s$. Let $P(\Sigma)$ be the power set of $\Sigma$. There is a map $f:\mathrm{Sub}(s)\to P(\Sigma)$ sending a substring to the set of symbols it contains.

For fixed $m$ and $n$ what is the maximum cardinality of the image of $\mathrm{Sub}(s)\to P(\Sigma)$?

For instance if $m=n$ then $f$ is injective so we get$$1+\frac{n(n+1)}{2}$$different subsets.

Answer 1

If I understand the question correctly, brute-force search with some Julia code gives following small values $C(m,n)$ for the maximum number of subsets covered by the contiguous substrings:

\begin{array}{rr|rrrrrrrrrrrrrrrrr} && n\\ && 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14\\ \hline m & 2 & 4 & = \\ & 3 & & 7 & 8 & = \\ & 4 & & & 11 & 13 & 14 & 15 & 16 & = \\ & 5 & & & & 16 & 19 & 21 & 23 & 25 & 27 & 30 & 31 & 32 & = \\ & 6 & & & & & 22 & 26 & 29 & 32 & 35 & 38 & 41 & 45 & 48 \\ & 7 & & & & & & 29 & 34 & 38 & 42 & 46 & 50 & 54 & 58 \\ & 8 & & & & & & & 37 & 43 & 48 & 53 & 58 & 63 & 68 \\ & 9 & & & & & & & & 46 & 53 & 59 & 65 & 71 & 77 \\ & 10& & & & & & & & & 56 & 64 & 71 & 78 & 85 \\ & 11& & & & & & & & & & 67 & 76 & 84 & 92 \\ & 12& & & & & & & & & & & 79 & 89 & 98 \\ & 13& & & & & & & & & & & & 92 & 103 \\ & 14& & & & & & & & & & & & & 106 \\ \end{array}

"=" means that the rest of the row repeats the last value, that is, there is a string that exhibits all $2^m$ subsets (adding more length will not change this).

Looking at diagonals:

• The main diagonal is as described in the question.
• The first superdiagonal 4,8,13,19,26,34,43,53,64,76 has one OEIS match, A034856 "a(n) = binomial(n+1, 2) + n - 1 = n*(n + 3)/2 - 1".
• The second superdiagonal has no OEIS entry but OEIS guesses it to be a quadratic. Same with third superdiagonal.
• The fourth superdiagonal, starting from 16,25,35,46,58,71,85,100,116,133,151 has two matches (but different values before the 16).

If we write $T(m)$ for the smallest $n$ where $2^m$ appears, $T$ forms a sequence that starts 1,2,4,8,13, which matches many things in OEIS. Examples of shortest strings where all $2^m$ subsets of alphabet $\{1,2,\ldots,m\}$ appear are:

\begin{array}{l|l} m & T(m) \\ \hline 1 & 1 & 1 \\ 2 & 2 & 12 \\ 3 & 4 & 1231 \\ 4 & 8 & 12314234 \\ 5 & 13 & 1234512413524 \\ \end{array}

Proof sketch for first superdiagonal

From the small values one can conjecture that $C(m,m+1) = \frac{1}{2}m^2 + \frac{3}{2}m - 1$. I think this is true for all $m \ge 2$, here's a (sort of) proof.

Let us construct the string letter by letter. At each position we have two kinds of choices: a letter already seen, or an unseen letter. In the second case we can, without loss of generality, pick the smallest unseen letter; this is just a matter of permutation of the alphabet. In the first case, it does no good to pick the previous letter again, so we rule that out.

Consider a string over alphabet $\{1,2,\ldots,m\}$ of length $n=m+1$. Because each letter has to appear at least once, we have only one letter $q$ appearing twice, with the repeat occurring at some position $p$. So we have only a small number of strings to consider. The strings are of the form:

$$ 1,2,\ldots,p-1,q,p,\ldots,m $$

where at position $p$ we have picked an already seen letter $q \in \{1,2,\ldots,p-2\}$. The rest of the string is forced because we must pick all the remaining $m-p+1$ letters, and w.l.o.g. we can just take them in order.

For example, with $m=5$ and $n=6$, our candidate strings and the numbers of subsets covered are as follows. The repeated letter $q$ is underlined.

\begin{array}{ll} 12\underline{1}345 & 16 \\ 123\underline{1}45 & 17 \\ 123\underline{2}45 & 16 \\ 1234\underline{1}5 & 18 \\ 1234\underline{2}5 & 17 \\ 1234\underline{3}5 & 16 \\ 12345\underline{1} & 19 \\ 12345\underline{2} & 18 \\ 12345\underline{3} & 17 \\ 12345\underline{4} & 16 \end{array}

Taking $p=n$ and $q=1$ we get the string that has first all letters $1,\ldots,m$ in order, then repeats the 1. This gives the conjectured value. I believe that for other choices of $p$ and $q$ one can show that the result is smaller (for all $m$) but I didn't check the details.

The $m=6$ case

Update (25.5.2021). We have $C(6,24)=64$. There are several 24-digit strings attaining this maximum, for example $$123456 \; 532614 \; 251364 \; 265143$$ (spaces just for easier reading). This string begins with 1...m, supporting Per Alexandersson's conjecture in the comments.

It also seems (by about 56 cpu-hours of computation) that $C(6,23)=63$, so the $T$ sequence would begin $1,2,4,8,13,24$. This has 7 matches in OEIS, but I could not easily see a connection to the present problem in any of them.

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 $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$ 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.

Answer 2

Using some Mathematica, we we let $h(m,n)$ be defined as $$ h(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$ For small combinations of $(m,n)$, we get the table \begin{array}{cccccccc} 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 2 & 4 & 4 & 4 & 4 & 4 & 4 & 4 \\ 2 & 4 & 7 & 8 & 8 & 8 & 8 & 8 \\ 2 & 4 & 7 & 11 & 13 & 14 & 15 & 16 \\ 2 & 4 & 7 & 11 & 16 & 19 & 21 & 23 \\ 2 & 4 & 7 & 11 & 16 & 22 & 26 & 29 \\ \end{array} $$ The code used here is:

cardSort[wrd_List] := Prepend[
   Union[Join @@ Table[
      Union[wrd[[i ;; j]]],
      {i, Length@wrd}, {j, i, Length@wrd}]]
   , {}];
h2[m_, n_] := 
  h2[m, n] = Max@Table[Length@cardSort[w], {w, Tuples[Range[m], n]}];

OLD Answer: If we instead set $$ h'(m,n) = \max_{f : [n] \to [m] } | \mathrm{image}(f) |. $$ where the we now map to $f$ to the set of all contiguous substrings, we get the table $$ \begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 1 & 3 & 5 & 8 & 12 & 16 & 21 & 27 \\ 1 & 3 & 6 & 9 & 13 & 18 & 24 & 31 \\ 1 & 3 & 6 & 10 & 14 & 19 & 25 & 32 \\ 1 & 3 & 6 & 10 & 15 & 20 & 26 & 33 \\ \end{array} $$ Some search in the OEIS suggests that we (almost always have) $$ h'(m,n) = \text{Number of edges in $(m+1)$-partite Turán graph of order $n+1$.} $$

The Mathematica code I used here is

card[wrd_List] := 
  Length@Union[
    Join @@ Table[wrd[[i ;; j]], {i, Length@wrd}, {j, i, Length@wrd}]];
h[m_, n_] := h[m, n] = Max@Table[card[w], {w, Tuples[Range[m], n]}];