MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question is related to my previous questions, say, this one and this one. Let $G$ be an infinite graph of bounded degree, and $\lambda>0$. Let $k=k_G(\lambda)$ be the minimal number of colors such that we can color $G$ in $k$ colors and all monochromatic $\lambda$-paths without repeating vertices have bounded lengths. (A $\lambda$-path is, by definition, a sequence of vertices such that the distance between two consecutive vertices in $G$ is at most $\lambda$, the length of a $\lambda$-path is the number of vertices in it.)

Question Is there a $G$ such that for some $\lambda>0$, the sequence $k_{G^n}(\lambda)$ grows faster than $n^{\alpha}$ for some $\alpha>0$? Would that be true if $G$ were the infinite binary tree? Here $G^n$ is the $n$-th direct power of $G$, i.e. the direct product of $n$ copies of $G$.

In the question cited above, $G$ was the line.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.