Existence of "colouring matrices"
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}$.