Existence of "colouring matrices" Edit: there is now a follow-up question related to this post.



Definitions

Let $c$ and $k$ be integers. We use the notation $[i] = \{1,2,...,i\}$.

A $c \times c$ matrix $M = (m_{i,j})$ is said to be a $c$-to-$k$ colouring matrix if the following holds:


we have $m_{i,j} \in [k]$ for all $i, j \in [c]$,
for all $i,j,\ell \in [c]$ with $i \ne j$ and $j \ne \ell$ we have $m_{i,j} \ne m_{j,\ell}$.


We write $c \leadsto k$ if there exists a $c$-to-$k$ colouring matrix.



Note that the diagonal elements are irrelevant; we are only interested in the non-diagonal elements of $M$.

The following alternative perspective may be helpful. Let $R(M,\ell) = \{ m_{\ell,i} : i \ne \ell \}$ be the set of non-diagonal elements in row $\ell$, and similarly let $C(M,\ell) = \{ m_{i,\ell} : i \ne \ell \}$ be the set of non-diagonal elements in column $\ell$. Now $M$ is a $c$-to-$k$ colouring matrix iff $$R(M,\ell) \subseteq [k], \quad C(M,\ell) \subseteq [k], \quad R(M,\ell) \cap C(M,\ell) = \emptyset$$ for all $\ell \in [c]$. That is, row $\ell$ and column $\ell$ must consist of distinct elements (except, of course, at the diagonal).

It may or may not be helpful to try to interpret $M$ as a special kind of hash function from $[c]^2$ to $[k]$.

Examples

Here is a $6$-to-$4$ colouring matrix: $$\begin{bmatrix}
-&amp;2&amp;2&amp;1&amp;1&amp;1\\
3&amp;-&amp;3&amp;1&amp;1&amp;1\\
4&amp;4&amp;-&amp;1&amp;1&amp;1\\
3&amp;2&amp;2&amp;-&amp;3&amp;2\\
4&amp;2&amp;2&amp;4&amp;-&amp;2\\
3&amp;4&amp;3&amp;4&amp;3&amp;-
\end{bmatrix}.$$

In general, it is known that for any $n \ge 2$ we have $${2n \choose n} \leadsto 2n.$$ For example, $20 \leadsto 6$ and $6 \leadsto 4$. To see this, we can use the following construction (e.g., Naor &amp; Stockmeyer 1995).

Let $c = {2n \choose n}$ and let $k = 2n$. Let $f$ be a bijection from $[c]$ to the set of all $n$-subsets of $[2n]$, that is, $f(i) \subseteq [2n]$ and $|f(i)| = n$ for all $i$. For each $i,j \in [c]$ with $i \ne j$, choose arbitrarily $$m_{i,j} \in f(i) \setminus f(j).$$

Note that $f(j) \setminus f(i) \ne \emptyset$. It is straightforward to verify that the construction is indeed a colouring matrix; in particular, we have $R(M,\ell) = f(\ell)$ and $C(M,\ell) = [k] \setminus f(\ell)$.

Question

Is the above construction optimal? Put otherwise, do we have $${2n \choose n} + 1 \leadsto 2n$$ for any $n \ge 2$?

It is well-known that the above construction is asymptotically tight; necessarily $k = \Omega(\log c)$. This follows, e.g., from Linial's (1992) result or from a straightforward application of Ramsey theory. But to me it is not clear whether the construction is also tight up to constants. Some numerical experiments suggest that the above construction might be optimal.

Motivation

The question is related to the existence of fast distributed algorithms for graph colouring. For example, assume that we are given a directed tree (all edges oriented towards a root node), and assume that we are given a proper $c$-colouring of the tree. Now there is a distributed algorithm that computes a proper $k$ colouring of the tree in $1$ synchronous communication round if and only if $c \leadsto k$.
The construction is optimal in the sense that $\binom{2n}{n}+1 \leadsto n$ cannot hold.  Indeed, it is easy to see that c-to-k coloring matrix exists if and only if there are c subsets A1, …, Ac of the set {1, …, k} such that no distinct i and j satisfy Ai ⊆ Aj.  (For the “only if” direction, take Ai = R(M, i) for a c-to-k coloring matrix M.  For the “if” direction, set mij ∈ Ai ∖ Aj.)  A family of sets none of which contains another is called a Sperner family, and it is Sperner’s theorem that the maximum number of sets in a Sperner family on the universe of size k is $\binom{k}{\lfloor k/2\rfloor}$.  This implies that $c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$.