Is the following true? For every $n \geq 1, k\geq 2$, there is a set $S \subseteq [n]^k$ of size $|S| = n^2$ such that every two $k$-tuples in $S$ have at most one common entry.
Does anyone know if this is true? Is there a reference?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ please explicitly define "one common entry" since you talk about tuples not sets $\endgroup$– kodluJan 25, 2022 at 21:21
-
1$\begingroup$ If it means "tuples match in at most one coordinate", it would be false already for $n=2$, $k=4$. If one of the tuples is (w.l.o.g.) 1111, each of the other three tuples must have three 2's, so any two of them will have two matching 2's. So is there some other meaning of "one common entry"? $\endgroup$– Jukka KohonenJan 26, 2022 at 1:20
-
$\begingroup$ Thanks, Jukka. I missed this simple example.. $\endgroup$– Lior GishbolinerJan 26, 2022 at 12:23
-
$\begingroup$ So this "tuples match in at most one coordinate" is the intended meaning? In that case we have an answer to the question. $\endgroup$– Jukka KohonenJan 26, 2022 at 13:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Assuming that "at most common entry" means that any two tuples $(x_1,\ldots,x_k)$ and $(y_1,\ldots,y_k)$ match in at most one position, that is, there is at most one $i$ such that $x_i=y_i$.
The claim is false for $n=2$ and any $k \ge 4$. We would need $n^2=4$ tuples $x,y,z,w$. Then each of $y$ and $z$ must differ from $x$ in at least $k-1$ positions, which implies that $y$ and $z$ match in at least $k-2 \ge 2$ positions.
(If the meaning was that any two tuples contain at most one common value, regardless of position, the claim would fail already with $n=2$, $k=2$, because there are only four different tuples $(1,1),(1,2),(2,1),(2,2)$, and $(1,2),(2,1)$ have two common values $1$ and $2$.)
answered Jan 26, 2022 at 13:34