Existence of "colouring matrices"

Question

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} -&2&2&1&1&1\\ 3&-&3&1&1&1\\ 4&4&-&1&1&1\\ 3&2&2&-&3&2\\ 4&2&2&4&-&2\\ 3&4&3&4&3&- \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 & 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$.

Answer 1

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 A₁, …, A_c of the set {1, …, k} such that no distinct i and j satisfy A_i ⊆ A_j. (For the “only if” direction, take A_i = R(M, i) for a c-to-k coloring matrix M. For the “if” direction, set m_ij ∈ A_i ∖ A_j.) 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}$.

Answer 2

For a slightly tighter asymptotic, it could be proven that:

if $c \leadsto k$, then $c \leq 2^k$

Suppose there is a coloring of a $ c \times c$ matrix using $k$ colors. Now, color each row in the matrix by the set of colors present it contains. That gives a coloring of the rows using subsets of $[k]$. Different rows must have different colors. Otherwise, suppose that for $i \lt j$, row $i$ has the same color as row $j$. That means the color of $(i,j)$ is present at both row $j$ and at column $j$ which contradict the fact that we started with a coloring. It follows that $c \leq 2^k$