Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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