This is a generalisation of the following post: 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 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, 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.
