# walks on proper coloring of odd cycles: comparing asymptotics

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.

-
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? –  Dimitrije Kostic Nov 13 '11 at 20:38
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$. –  Steve Nov 14 '11 at 0:48
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$. –  Steve Nov 14 '11 at 17:03

Here's a somewhat more systematic argument for the intuitively plausible result that the growth factor of the $F_k$ is bounded away from $2$ for $n\to\infty$ whereas the growth factor of the $G_k$ tends to $2$ for $n\to\infty$. I will use the exponential growth formula (Theorem IV.7 in Analytic Combinatorics (free download link)), which states that the radius of convergence of an analytic function at the origin (which for a rational function is the magnitude of the pole nearest to the origin) is the inverse of the growth factor of the coefficients.

First, for $F_k$, we have two cases. The case of even $n$ is easy. The colouring is $010\ldots0102$, and independently of $n$ the possible colour walks are given by arbitrarily long strings of the form $010\ldots010$ with $2$s in between. The generating function to count these has a factor $x$ for each $2$ and a factor $x+x^3+x^5+\dotso=x/(1-x^2)$ for the strings of the form $010\ldots010$, and this can be repeated any number of times, so with $u=x^2/(1-x^2)$ we have

$$f(x)=1+u+u^2+\dotso=\frac1{1-u}=\frac1{1-x^2/(1-x^2)}=\frac{1-x^2}{1-2x^2}\;.$$

Actually the last string of $0$s and $1$s can also end in a $1$, and there doesn't have to be a $2$ at the beginning, but these "finite-size effects" are just corrections in the numerator that don't affect the zeros of the denominator that determine the growth factor (which makes sense). The only poles of $f$ are at $1/\sqrt2$, so the growth factor in this case is $\sqrt2$.

In the case of odd $n$, the colouring is $010\ldots1012$, and now it makes a difference which side of the $2$ we go to and whether we return to the same side or the other side. The generating function again has a factor of $x$ for each $2$, but the factors for the strings of $0$s and $1$s are a bit more complicated. There's a factor of $2$ because we can go to either side of the $2$. Then we have the choice of either adding an odd number of alternating $0$s and $1$s and returning to the $2$ from the same side, or of adding an even number of at least $n-1$ $0$s and $1$s and returning to the $2$ from the other side. These correspond to contributions $x(1+x^2+x^4+\dotso)$ and $x^{n-1}(1+x^2+x^4+\dotso)$, respectively, so in this case we get (again neglecting finite-size effects) $u=2x(x+x^{n-1})/(1-x^2)$ and thus

$$f(x)=\frac1{1-u}=\frac1{1-2x(x+x^{n-1})/(1-x^2)}=\frac{1-x^2}{1-3x^2-2x^n}\;.$$

Here are the growth factors for the first few odd $n$:

$$\begin{array}{c|c} n&1/\rho_n\\ \hline 3&2\\ 5&1.824621\\ 7&1.765400\\ 9&1.743786\\ 11&1.736075\\ 13&1.733412 \end{array}$$

The growth factors clearly tend to $\sqrt3$, and I presume this wouldn't be difficult to show rigorously from the simple form of the denominator. This makes sense, since in the limit $n\to\infty$ there is no longer any gain from traversing the vast expanse of repeating $0$s and $1$s, so the $x^n$ term becomes negligible and the denominator is just $1-3x^2$.

For the $G_k$, the situation is somewhat more complicated. Setting up the complete generating functions would be a bit tedious, though possible, so I'll use a rough bound to show that the growth factor tends to $2$: I'll consider only the colour walks that reach and leave the final, irregular vertex from and to one of the two sides. Then the colour of that vertex and its neighbours becomes irrelevant, and we don't have to distinguish different cases depending on $n\bmod 3$.

Each part of the walk between two visits to the final vertex corresponds to a Dyck path that doesn't go above $n-2$ or below $0$. These are counted in this paper by the generating function

$$R_{n-2}(x)=\frac{U^*_{n-2}(x)}{U^*_{n-1}(x)}\;,$$

where the $U^*_n$ are defined in terms of the Chebyshev polynomials of the second kind by

$$U^*_n(x)=x^nU_k\left(\frac1{2x}\right)\;.$$

Again, we have a factor of $x$ for each occurence of the final vertex, and a factor of $xR_{n-2}(x)$ for each foray into the rest of the cycle ($x$ because it takes one step in addition to the Dyck path to get started), and we can repeat this any number of times, so the generating function (up to finite-size effects) is

$$f(x)=\frac1{1-xR_{n-2}(x)}=\frac{U_{n-1}(t)}{U_{n-1}(t)-xU_{n-2}(t)}$$

with $t=1/2x$. By a lucky coincidence (or perhaps not), the Chebyshev polynomials of the second kind satisfy the recurrence relation $U_n(t)=2tU_{n-1}(t)-U_{n-2}(t)$, which gives us

$$f(x)=\frac{2tU_{n-1}(t)}{U_n(t)}\;.$$

Thus, the growth factor is twice the largest root of $U_n$. The roots of $U_n$ are given by

$$x_k=\cos\frac {k\pi}{n+1}$$

for $k=1,\dotsc,n$, so the largest one is $\cos\pi/(n+1)$, which tends to $1$ as $n\to\infty$; thus the growth factor tends to $2$. Here are the growth factors for the first few values of $n$:

$$\begin{array}{c|c} n&1/\rho_n\\ \hline 1&0\\ 2&1\\ 3&\sqrt2\\ 4&1.618034\\ 5&\sqrt3\\ 6&1.801938\\ 7&1.847759 \end{array}$$

We can check that the first three values make sense: For $n=1$, there are no walks at all of the kind described; for $n=2$, there are no choices and thus only one walk for every $n$, and for $n=2$ there is a binary choice to make every second step when we're on the first vertex; thus these three growth factors are correct.

In summary, the growth factor for the $F_k$ for even $n$ is $\sqrt2$; the growth factors for the $F_k$ for odd $n$ tend to $\sqrt3$ from above for $n\to\infty$; and the growth factors for the $G_k$ tend to $2$ from below for $n\to\infty$. The crossover is at $N=7$ at the latest (taking into account that the factors for the $G_k$ are only lower bounds since we didn't count all the walks). Thus the claim in the question is correct.

-
The calculation for a given (perhaps relatively small $n$) is not so difficult and was answered in the previous question. Does the case $n=7$ clearly imply the rest of the cases? I am looking for a (perhaps simple) proof (if it exists) that the statement holds for any $n \geq 7$. –  Steve Nov 13 '11 at 16:56
@Steve: I see, sorry, I'd misunderstood the question -- I'll think about it some more... –  joriki Nov 13 '11 at 17:49
@Steve: I've updated with a more systematic approach -- I hope this meets the level of rigour you were aiming for? –  joriki Nov 15 '11 at 21:11
Thank you joriki. It will take me some time to work through the details, but at first glance, this looks very helpful. –  Steve Nov 15 '11 at 21:41
For lower bounds on $G_k$, would it be simpler to look at the "regular part." For example, let $C_7$, be coloured 0120121. Consider the string 012012 (as if it were a labeling of $P_6$). All walks from the first 0 have a unique representation. Is there a simple calculation of the growth rate of walks here? Is it greater than $F_k$ for $C_7$? –  Steve Nov 22 '11 at 15:19