3
$\begingroup$

Given an alphabet $S={a_1,\cdots,a_m}$, we consider the words of length $n$, $S^n$.

We call two words $b_1b_2\cdots b_n$ and $c_1c_2\cdots c_n$ are connected if $b_i=c_i$ for some $i$.

We consider $P\subseteq S^n$ with the following property: for any $r\in S^n$, there exists $p\in P$ such that $r$ and $p$ are not connected.

What is the minimal size $u_m(n)$ of $P$ to have the wanted property? Is there an explicit construction?

For $m=2$, it shall be $u_2(n)=2^{n}$. What about general $m$?

For $m=3$ and $n=2$, we only need 3 elements, $a_1a_1$, $a_2a_2$ and $a_3a_3$. Because for any $b_1b_2$, there is $i$ such that $b_1\neq a_i$ and $b_2\neq a_i$. Then $a_ia_i$ is not connected with $b_1b_2$. So $u_3(2)=3$.

This seems like a standard error correcting code question.

$\endgroup$
11
  • $\begingroup$ Thank you very much! It shall be not connected. $\endgroup$
    – gondolf
    Jul 27, 2022 at 1:03
  • $\begingroup$ Yes. Can it be polynomial, even for $m=3$? $\endgroup$
    – gondolf
    Jul 27, 2022 at 1:10
  • 2
    $\begingroup$ domotorp's example generalises to give an upper bound of $n+1$ whenever $m > n$. But $n+1$ is also clearly a lower bound, because if you have $n$ words then you can find a word which is connected to all of them by taking the $i$th letter from the $i$th word. So the problem reduces to the case $m \le n$. $\endgroup$ Jul 27, 2022 at 8:18
  • 1
    $\begingroup$ We have bounds: $$\left(\frac{m}{m-1}\right)^n \leq u_m(n) \leq 2^n.$$ Also, for $n<m$, $u_m(n)\leq n+1$. $\endgroup$ Jul 27, 2022 at 21:11
  • 1
    $\begingroup$ In the jargon of graph theory, what you are asking for is the total domination number of the categorical product (a.k.a. tensor product, direct product, etc. etc. etc.) of $n$ copies of the complete graph $K_m$. It might be worthwhile to explore the extensive literature on domination in graphs to see what is known about your question. $\endgroup$
    – bof
    Jul 28, 2022 at 0:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.