<p>For a slightly tighter asymptotic, it could be proven that:</p>

<p>if $c \leadsto k$,  then $c \leq 2^k$</p>

<p>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$</p>

CC BY-SA 3.0
2012-06-09T17:05:24.063Z
I am not sure what you are claiming your analysis is tighter than, but please see my answer for the exact bound.
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-03T02:31:13.497Z
2012-06-03T02:31:13.497Z
hbm
<p>The construction is optimal in the sense that $\binom{2n}{n}+1 \leadsto n$ cannot hold.  Indeed, it is easy to see that <i>c</i>-to-<i>k</i> coloring matrix exists if and only if there are <i>c</i> subsets <i>A</i><sub>1</sub>, …, <i>A</i><sub><i>c</i></sub> of the set {1, …, <i>k</i>} such that no distinct <i>i</i> and <i>j</i> satisfy <i>A</i><sub><i>i</i></sub> ⊆ <i>A</i><sub><i>j</i></sub>.  (For the “only if” direction, take <i>A</i><sub><i>i</i></sub> = <i>R</i>(<i>M</i>, <i>i</i>) for a <i>c</i>-to-<i>k</i> coloring matrix <i>M</i>.  For the “if” direction, set <i>m</i><sub><i>ij</i></sub> ∈ <i>A</i><sub><i>i</i></sub> ∖ <i>A</i><sub><i>j</i></sub>.)  A family of sets none of which contains another is called a <a href="http://en.wikipedia.org/wiki/Sperner_family">Sperner family</a>, and it is Sperner’s theorem that the maximum number of sets in a Sperner family on the universe of size <i>k</i> is $\binom{k}{\lfloor k/2\rfloor}$.  This implies that $c \leadsto k \iff c \le \binom{k}{\lfloor k/2\rfloor}$.</p>

CC BY-SA 3.0
2012-06-02T17:15:17.397Z
Oh, right, I thought it looked like the rows would have to form a Sperner family, but did not see how to prove it. But you are absolutely right: if we have $R(M,i) \subseteq R(M,j)$, then $m_{i,j} \in R(M,i) \subseteq R(M,j)$, and therefore $C(M,j) \cap R(M,j) \ne \emptyset$. That was easy, many thanks!
Jukka Suomela
CC BY-SA 3.0
2012-06-02T16:46:20.583Z
2012-06-02T16:51:27.767Z
2012-06-02T16:51:27.767Z
Tsuyoshi Ito
<p><strong>Edit:</strong> there is now a <a href="https://cstheory.stackexchange.com/questions/11620/existence-of-colouring-matrices-a-generalisation">follow-up question</a> related to this post.</p>

<hr>

<h2>Definitions</h2>

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

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

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

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

<hr>

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

<p>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).</p>

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

<h2>Examples</h2>

<p>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}.$$</p>

<p>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).</p>

<p>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).$$</p>

<p>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)$.</p>

<h2>Question</h2>

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

<p>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.</p>

<h2>Motivation</h2>

<p>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$.</p>

CC BY-SA 3.0
2012-06-02T16:49:02.497Z
In the display math in the “alternate perspective,” [c] should read [k].  On the line following it, “for all l \in [k]” should read “for all l \in [c]”.
Tsuyoshi Ito
<co.combinatorics><lower-bounds><dc.distributed-comp>
Existence of "colouring matrices"
Jukka Suomela
# Existence of "colouring matrices"

(Asked by: username_0 on 2012-06-02)

**Edit:** there is now a [follow-up question](https://cstheory.stackexchange.com/questions/11620/existence-of-colouring-matrices-a-generalisation) 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$.

**Tags:** co.combinatorics, lower-bounds, dc.distributed-comp

> **Comments:**
> **username_1**: In the display math in the “alternate perspective,” [c] should read [k].  On the line following it, “for all l \in [k]” should read “for all l \in [c]”.  

---

## 2 answers

### Answer by username_1 on 2012-06-02. Score: 9 | Accepted answer

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*1, …, *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](http://en.wikipedia.org/wiki/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}$.

> **Comments:**
> **username_0**: Oh, right, I thought it looked like the rows would have to form a Sperner family, but did not see how to prove it. But you are absolutely right: if we have $R(M,i) \subseteq R(M,j)$, then $m_{i,j} \in R(M,i) \subseteq R(M,j)$, and therefore $C(M,j) \cap R(M,j) \ne \emptyset$. That was easy, many thanks!  

---

### Answer by username_2 on 2012-06-03. Score: 0

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$

> **Comments:**
> **username_1**: I am not sure what you are claiming your analysis is tighter than, but please see my answer for the exact bound.  

---

