<p>This is a generalisation of the following post: <a href="https://cstheory.stackexchange.com/questions/11617/existence-of-colouring-matrices">Existence of "colouring matrices"</a>.</p>

<p>As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner families), I am feeling a bit more optimistic about the general case as well. Let's see how far we can get.</p>

<h2>Definition</h2>

<p>Let's switch from the matrix notation to a function notation. Again, $[i] = \{1,2,...,i\}$.</p>

<p>A function $f\colon [c]^d \to [k]$ is a <strong>$d$-dimensional $c$-to-$k$ colouring function</strong>, in notation $f\colon c \leadsto_d k$, if the following holds for all $x_1, x_2, ..., x_{d+1} \in [c]$ with $x_1 \ne x_2 \ne ... \ne x_{d+1}$: $$f(x_1,x_2,...,x_d) \ne f(x_2,x_3,...,x_{d+1}).$$</p>

<p>We write $c \leadsto_d k$ if $f\colon c \leadsto_d k$ for some $f$.</p>

<p>Now $c \leadsto k$ in the <a href="https://cstheory.stackexchange.com/questions/11617/existence-of-colouring-matrices">previous question</a> is exactly equal to $c \leadsto_2 k$ in this question, as it is trivial to interpret a colouring matrix as a $2$-dimensional colouring function.</p>

<h2>An example</h2>

<p>The $1$-dimensional case is trivial. We already saw examples of $2$-dimensional colouring functions in the previous question. Here is a simple example of a $3$-dimensional colouring function $f\colon k+1 \leadsto_3 k$, for any $k \ge 3$:</p>

<ul>
<li>$f(x,y,z) = y$ if $y \ne k+1$,</li>
<li>$f(x,y,z) = \min ( \{1,2,3\} \setminus \{x,z\} )$ if $y = k+1$.</li>
</ul>

<p>(This can be interpreted as a greedy graph colouring algorithm, in the case of $2$-regular graphs; $y$ is the old colour of a node $v$, $x$ and $z$ are the old colours of its two neighbours, and $f(x,y,z)$ is the new colour of node $v$. In essence, nodes of colour $k+1$ pick the smallest free colour that is available in their neighbourhood.)</p>

<h2>Composition</h2>

<p>Lower-dimensional colouring functions can be easily composed into higher-dimensional colouring functions. For example, assume that $$f_1\colon c_0 \leadsto_2 c_1, \quad f_2\colon c_1 \leadsto_2 c_2.$$ Now we can construct a colouring function $$g\colon c_0 \leadsto_3 c_2$$ as follows: $$g(x,y,z) = f_2(f_1(x,y), f_1(y,z)).$$</p>

<p>To see that this construction is correct, it is sufficient to note that $w \ne x \ne y \ne z$ implies $f_2(w, x) \ne f_2(x,y) \ne f_2(y,z)$, which implies $f_1(f_2(w, x), f_2(x,y)) \ne f_1(f_2(x, y), f_2(y,z))$.</p>

<p>As we observed in the <a href="https://cstheory.stackexchange.com/questions/11617/existence-of-colouring-matrices">previous post</a>, we have, for example, $$20 \leadsto_2 6 \leadsto_2 4.$$ Therefore we also have $$20 \leadsto_3 4.$$</p>

<p>However, <strong>this is not optimal</strong>! There is a computer-generated construction that shows that $$24 \leadsto_3 4.$$ Note that this is not possible to achieve by merely composing any $2$-dimensional colouring functions.</p>

<p>(If we construct $d$-dimensional colouring functions by composing $2$-dimensional colouring functions, we do get an <em>asymptotically</em> optimal solution; for example, $c \leadsto_2 \Theta(\log c)$, $c \leadsto_3 \Theta(\log \log c)$, etc. However, this question is really about exact constants, especially for small values of $c, k, d$.)</p>

<h2>Questions</h2>

<p>Of course ideally we would like to understand precisely when we have $c \leadsto_d k$. But here are some more down-to-earth questions; resolving any of those would be helpful:</p>

<ul>
<li>Is there a <em>simple</em> (human-generated) function $f\colon 24 \leadsto_3 4$? Or anything substantially better than $20 \leadsto_3 4$?</li>
<li>Is there a <em>simple</em> (human-generated) proof that $25 \leadsto_3 4$ does not hold?</li>
<li>More generally, can we construct optimal $3$-dimensional colouring functions?</li>
</ul>

<p><strong>Edit:</strong> Here is yet another example of a relevant question:</p>

<ul>
<li>By composition, we have $24 \leadsto_5 3$. Can we do better, for example, does $25 \leadsto_5 3$ hold?</li>
</ul>

<h2>Notes</h2>

<p>The existence of colouring functions is closely related to the chromatic number of a certain graph. For example, you can construct a graph $G(c,d)$ in which each $d$-tuple $(x_1,x_2,...,x_d) \in [c]^d$ is a node, and there are edges between nodes $(x_1,x_2,...,x_d)$ and $(x_2,x_3,...,x_{d+1})$ for all $x_1 \ne x_2 \ne ... \ne x_{d+1}$. Now the chromatic number of $G(c,d)$ is at most $k$ if and only if $c \leadsto_d k$. However, while this interpretation is helpful from the perspective of understanding the asymptotics, I do not know if it helps with the above questions.</p>

CC BY-SA 3.0
2012-06-02T21:29:41.757Z
An easy observation: It is again easy to see that existence of a 3-dimensional c-to-k coloring function is equivalent to a family of c(c−1) subsets A_ij (i≠j) of [k] such that A_ij ⊈ A_jk whenever i≠j≠k.  (This generalizes to arbitrary dimension, but that is not the point for now.)  To construct a 3-dimensional c-to-k coloring function for even k, it is tempting to assume that all A_ij’s have the same size k/2, but if we assume this, A_ij’s form a c-to-K coloring matrix, where $K=\binom{k}{k/2}$, by identifying k/2-subsets of [k] with integers in [K]. (cont)
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-02T21:29:53.223Z
(cont’d) In particular, we cannot construct a 3-dimensional 21-to-4 coloring function if we want all A_ij to have size 2. So we have to make these sets somewhat “unbalanced.”
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-03T12:03:17.857Z
The graph $G(c,d)$ = $L^{(d-1)}(\overrightarrow K_c)$, where $\overrightarrow K_c$ is the directed complete graph on $c$ vertices(between any two vertices both directed edges are included) and $L$ is the operation that return the the line graph (directed version).
hbm
<co.combinatorics><lower-bounds><dc.distributed-comp>
Existence of "colouring matrices" — a generalisation
Jukka Suomela
# Existence of "colouring matrices" — a generalisation

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

This is a generalisation of the following post: [Existence of "colouring matrices"](https://cstheory.stackexchange.com/questions/11617/existence-of-colouring-matrices).

As the base case turned out to be fairly straightforward (in essence, precisely equal to the existence of Sperner families), I am feeling a bit more optimistic about the general case as well. Let's see how far we can get.

## Definition

Let's switch from the matrix notation to a function notation. Again, $[i] = \{1,2,...,i\}$.

A function $f\colon [c]^d \to [k]$ is a **$d$-dimensional $c$-to-$k$ colouring function**, in notation $f\colon c \leadsto\_d k$, if the following holds for all $x\_1, x\_2, ..., x\_{d+1} \in [c]$ with $x\_1 \ne x\_2 \ne ... \ne x\_{d+1}$: $$f(x\_1,x\_2,...,x\_d) \ne f(x\_2,x\_3,...,x\_{d+1}).$$

We write $c \leadsto\_d k$ if $f\colon c \leadsto\_d k$ for some $f$.

Now $c \leadsto k$ in the [previous question](https://cstheory.stackexchange.com/questions/11617/existence-of-colouring-matrices) is exactly equal to $c \leadsto\_2 k$ in this question, as it is trivial to interpret a colouring matrix as a $2$-dimensional colouring function.

## An example

The $1$-dimensional case is trivial. We already saw examples of $2$-dimensional colouring functions in the previous question. Here is a simple example of a $3$-dimensional colouring function $f\colon k+1 \leadsto\_3 k$, for any $k \ge 3$:

* $f(x,y,z) = y$ if $y \ne k+1$,
* $f(x,y,z) = \min ( \{1,2,3\} \setminus \{x,z\} )$ if $y = k+1$.

(This can be interpreted as a greedy graph colouring algorithm, in the case of $2$-regular graphs; $y$ is the old colour of a node $v$, $x$ and $z$ are the old colours of its two neighbours, and $f(x,y,z)$ is the new colour of node $v$. In essence, nodes of colour $k+1$ pick the smallest free colour that is available in their neighbourhood.)

## Composition

Lower-dimensional colouring functions can be easily composed into higher-dimensional colouring functions. For example, assume that $$f\_1\colon c\_0 \leadsto\_2 c\_1, \quad f\_2\colon c\_1 \leadsto\_2 c\_2.$$ Now we can construct a colouring function $$g\colon c\_0 \leadsto\_3 c\_2$$ as follows: $$g(x,y,z) = f\_2(f\_1(x,y), f\_1(y,z)).$$

To see that this construction is correct, it is sufficient to note that $w \ne x \ne y \ne z$ implies $f\_2(w, x) \ne f\_2(x,y) \ne f\_2(y,z)$, which implies $f\_1(f\_2(w, x), f\_2(x,y)) \ne f\_1(f\_2(x, y), f\_2(y,z))$.

As we observed in the [previous post](https://cstheory.stackexchange.com/questions/11617/existence-of-colouring-matrices), we have, for example, $$20 \leadsto\_2 6 \leadsto\_2 4.$$ Therefore we also have $$20 \leadsto\_3 4.$$

However, **this is not optimal**! There is a computer-generated construction that shows that $$24 \leadsto\_3 4.$$ Note that this is not possible to achieve by merely composing any $2$-dimensional colouring functions.

(If we construct $d$-dimensional colouring functions by composing $2$-dimensional colouring functions, we do get an *asymptotically* optimal solution; for example, $c \leadsto\_2 \Theta(\log c)$, $c \leadsto\_3 \Theta(\log \log c)$, etc. However, this question is really about exact constants, especially for small values of $c, k, d$.)

## Questions

Of course ideally we would like to understand precisely when we have $c \leadsto\_d k$. But here are some more down-to-earth questions; resolving any of those would be helpful:

* Is there a *simple* (human-generated) function $f\colon 24 \leadsto\_3 4$? Or anything substantially better than $20 \leadsto\_3 4$?
* Is there a *simple* (human-generated) proof that $25 \leadsto\_3 4$ does not hold?
* More generally, can we construct optimal $3$-dimensional colouring functions?

**Edit:** Here is yet another example of a relevant question:

* By composition, we have $24 \leadsto\_5 3$. Can we do better, for example, does $25 \leadsto\_5 3$ hold?

## Notes

The existence of colouring functions is closely related to the chromatic number of a certain graph. For example, you can construct a graph $G(c,d)$ in which each $d$-tuple $(x\_1,x\_2,...,x\_d) \in [c]^d$ is a node, and there are edges between nodes $(x\_1,x\_2,...,x\_d)$ and $(x\_2,x\_3,...,x\_{d+1})$ for all $x\_1 \ne x\_2 \ne ... \ne x\_{d+1}$. Now the chromatic number of $G(c,d)$ is at most $k$ if and only if $c \leadsto\_d k$. However, while this interpretation is helpful from the perspective of understanding the asymptotics, I do not know if it helps with the above questions.

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

> **Comments:**
> **username_1**: An easy observation: It is again easy to see that existence of a 3-dimensional c-to-k coloring function is equivalent to a family of c(c−1) subsets A_ij (i≠j) of [k] such that A_ij ⊈ A_jk whenever i≠j≠k.  (This generalizes to arbitrary dimension, but that is not the point for now.)  To construct a 3-dimensional c-to-k coloring function for even k, it is tempting to assume that all A_ij’s have the same size k/2, but if we assume this, A_ij’s form a c-to-K coloring matrix, where $K=\binom{k}{k/2}$, by identifying k/2-subsets of [k] with integers in [K]. (cont)  
> **username_1**: (cont’d) In particular, we cannot construct a 3-dimensional 21-to-4 coloring function if we want all A_ij to have size 2. So we have to make these sets somewhat “unbalanced.”  
> **username_2**: The graph $G(c,d)$ = $L^{(d-1)}(\overrightarrow K_c)$, where $\overrightarrow K_c$ is the directed complete graph on $c$ vertices(between any two vertices both directed edges are included) and $L$ is the operation that return the the line graph (directed version).  

---

## 0 answers

