2
$\begingroup$

Consider an alphabet $\Sigma=\{1,\dots,n\}$. An ordered word is a word $w=w_1w_2\dots w_k\in\Sigma^*$ such that $w_1<w_2<\dots<w_k$. In other words, an ordered word is a strictly increasing sequence over $\{1,\dots,n\}$.

Let us call $O_{n,k}$ the set of all ordered words over $\{1,\dots,n\}$ of length $k$. Clearly, there are $\binom{n}{k}$ many ordered words of length $k$.

Now, what I am looking for is the maximal size of a subset $M\subseteq O_{n,k}$ such that each pair of letters $ij$ ($1\le i<j\le n$) occurs at most once as a consecutive substring in any word of $M$. What is the maximal size of such a subset?

Formally, let $\#_{ij}(M)$ be the number of words in $M$ that contain $ij$ as a consecutive substring, then $$m_{n,k}=\max\{|M|:M\subseteq O_{n,k}\text{ and }\#_{ij}(M)\le 1\text{ for all }i,j\text{ with }1\le i<j\le n\}.$$ What is $m_{n,k}$?

Asymptotic behavior as well as some non-trivial lower and upper bounds would be helpful.

$ $

Example: $\Sigma=\{1,2,3,4\}$ and $k=3$.

All ordered words of length $3$ are $$O_{4,3}=\{123,124,134,234\}.$$ A maximal subset such that no pair occurs more than once would be $$M=\{123,134\},$$ because all pairs $(12,13,14,23,24,34)$ occur at most once as a consecutive substring in $M$ and there is no set of size $3$ with this property. It follows that $m_{4,3}=2$.

Thank for any help.

$\endgroup$
2
$\begingroup$

There is a simple upper bound of $$\frac{\binom{n}{2}}{k-1},$$ following from the fact that there are $\binom{n}{2}$ ordered pairs of elements, and each ordered word contains $k-1$ of them.

There is an almost matching lower bound of $$ \frac{\binom{n-k+1}{2}}{k-1}. $$ This shows that for fixed $k$, the answer is asymptotically $$ \frac{n^2}{2(k-1)} \pm O(n). $$

For every $c \geq 1$ and $1 \leq d \leq c$, we can consider the collection of ordered words of the form $$ d,d+c,\ldots,d+(k-1)c \\ d+(k-1)c,d+(k+1)c,\ldots,d+2(k-1)c \\ \ldots $$ These collections for all $c,d$ have disjoint pairs. For a given $m \leq n$ and $c$, there is a word of this type if $m-(k-1)c \geq 1$, that is, if $c \leq \frac{m-1}{k-1}$. Therefore, the total number of words is $$ \sum_{m=k}^n \left\lfloor \frac{m-1}{k-1} \right\rfloor. $$ We can estimate this sum roughly by $$ \sum_{m=k}^n \left(\frac{m-1}{k-1}-1\right) = \sum_{m=k}^n \frac{m-k}{k-1} = \frac{\binom{n-k+1}{2}}{k-1}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.