8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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) $\endgroup$ – Tsuyoshi Ito Jun 2 '12 at 21:29
  • 3
    $\begingroup$ (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.” $\endgroup$ – Tsuyoshi Ito Jun 2 '12 at 21:29
  • $\begingroup$ 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). $\endgroup$ – hbm Jun 3 '12 at 12:03

Your Answer

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

Browse other questions tagged or ask your own question.