Construct large set of words with a property

52 Views Asked by At

Let $[m]$ denote $\{1,\ldots,m\}$ and $(v)_i$ denote the $i$-ith coordinate of a vector $v$.

Let $m$ and $k$ be positive integers. Then $[m]^k$ denotes the set of all words with letters from $[m]$ of length $k$. I am trying to find a large set $\mathcal{W}\subset [m]^k$ such that the following property holds. For every distinct $W_1,\ldots,W_m\in\mathcal{W}$ there exists a coordinate $i\in [k]$ such that $(W_1)_i,(W_2)_i,\ldots,(W_m)_i$ are all distinct (in other words, $\{(W_1)_i,\ldots,(W_m)_i\}=[m]$).

Clearly, the size of $[m]^k$ is $m^k$. So I am looking for a set $\mathcal{W}$ such that its size is also exponential in $k$ (consider $m$ as a constant). In particular, I would like to find $\lambda=\lambda_m>1$ such that for every $k$ we can find a set of size at least $\lambda^k$ with the property. Also, I would prefer a deterministic construction (but nondeterministic constructions are of interest as well).