9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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]”. $\endgroup$ – Tsuyoshi Ito Jun 2 '12 at 16:49
9
$\begingroup$

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 AiAj. (For the “only if” direction, take Ai = R(M, i) for a c-to-k coloring matrix M. For the “if” direction, set mijAiAj.) 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}$.

$\endgroup$
  • 1
    $\begingroup$ 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! $\endgroup$ – Jukka Suomela Jun 2 '12 at 17:15
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I am not sure what you are claiming your analysis is tighter than, but please see my answer for the exact bound. $\endgroup$ – Tsuyoshi Ito Jun 9 '12 at 17:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.