Counting walks on proper colorings of odd cycles - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T03:01:14Z http://mathoverflow.net/feeds/question/79932 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79932/counting-walks-on-proper-colorings-of-odd-cycles Counting walks on proper colorings of odd cycles Stephen Shea 2011-11-03T14:52:25Z 2011-11-03T15:32:10Z <p>Let $G$ be an undirected odd cycle. Let $f$ be a proper 3-coloring of $G$. If $w=v_1v_2...v_k$ is a walk on $k$ vertices of $G$, let $f(w)=f(v_1)f(v_2)...f(v_k)$. Let <code>$W_k=\{f(w)|w$</code> is a walk on $k$ vertices in <code>$G\}$</code>. Let $|W_k|$ be the cardinality of $W_k$. </p> <p>Is it true that $\lim_{k \to \infty} \frac{\log |W_k|}{k}=\log 2$ regardless of the order of $G$ and the choice of $f$?</p> <p>Thank you.</p> http://mathoverflow.net/questions/79932/counting-walks-on-proper-colorings-of-odd-cycles/79941#79941 Answer by Ori Gurel-Gurevich for Counting walks on proper colorings of odd cycles Ori Gurel-Gurevich 2011-11-03T15:32:10Z 2011-11-03T15:32:10Z <p>Certainly not. Take the coloring that is alternating black and white, except for a single red. </p>