1
$\begingroup$

Let $C_n$ be an odd (undirected) cycle with $n$ vertices. Let $f$ be the proper 3-coloring of $C_n$ where one vertex is colored $2$ and we alternate $01$ otherwise (0101...012 coloring).

Let $g$ be the proper 3-coloring of $C_n$ where we alternate $012$ as far as we can, and then (in the case $n=1 \mod 3$) fill in appropriately the last vertex so that the coloring remains proper. For example, $C_7$ can be colored $0120121$ ($n=1 \mod 3$), and $C_9$ can be colored $012012012$ ($n=3 \mod 3$). $C_{11}$ can be colored $01201201201$ ($n=2 \mod 3$).

Let $F_k$ be the number of distinct walks on $k$ $f$-colored vertices of $C_n$ ($f(v_1)f(v_2)...f(v_k)$ where $v_1v_2...v_k$ is a walk on $C_n$).

Let $G_k$ be the number of distinct walks on $k$ $g$-colored vertices of $C_n$ ($g(v_1)g(v_2)...g(v_k)$ where $v_1v_2...v_k$ is a walk on $C_n$).

Can we prove that for all $n \geq 7$, $\lim_{k \to \infty} \frac{\log (F_k)}{k} \not = \lim_{k \to \infty} \frac{ \log (G_k)}{k}$?

This is a follow up question to

Counting walks on colored graphs

Thank you.

  • 0
    I'm not sure I believe the inequality. If I understand correctly, both colorings of $C_n$ have at least one place where the vertices are colored 0-1-2-0-1. Because of that, it seems to me that if $(f(v_1),\dots f(v_k))$ is in $F_k$ (or $G_k$) I suspect you can choose a walk on $G_k$ (or $F_k$) over that little 0-1-2-0-1 spot that gives you the same sequence. So it seems to me that $F_k \approx (\text{ or } =) G_k$. Maybe I'm missing something?2011-11-13
  • 0
    Perhaps I wasn't clear. $F_k$ is the number of distinct walks on the colors where the $v_1v_2...v_k$ range over all walks of length $k$ on $C_n$. So, for example, if $n=9$, $\lim_{k\to \infty}\frac{\log(G_k)}{k}=\log 2$.2011-11-14
  • 0
    Since $f$ and $g$ are proper, $00$, $11$ and $22$ are always forbidden. I guess for $n=3 \mod 3$, the labeling $g$ adds no new forbidden words, while for $f$, we add at least 2102 and 2012. I suppose that is enough for the case $n=3 \mod 3$.2011-11-14

1 Answers 1