\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsmath, amsthm, amssymb} \usepackage{palatino, url, multicol} \usepackage[all]{xy} % declare theorem-like environments \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \newtheorem{prop}[thm]{Proposition} \newtheorem{fact}[thm]{Fact} \newtheorem{observation}[thm]{Observation} \newtheorem{claim}[thm]{Claim} \theoremstyle{definition} \newtheorem{defn}[thm]{Definition} \newtheorem{ex}[thm]{Example} \newtheorem{conjecture}[thm]{Conjecture} \newtheorem{open}[thm]{Open Problem} \newtheorem{problem}[thm]{Problem} \newtheorem{question}[thm]{Question} \theoremstyle{remark} \newtheorem{rem}[thm]{Remark} \newtheorem{note}[thm]{Note} \title{\bf Graph labelings and continuous factors of dynamical systems} \author{Stephen M. Shea\\ \small Department of Mathematics\\[-0.8ex] \small St. Anselm College\\[-0.8ex] \small Manchester, NH 03102\\ \small \tt{sshea@anselm.edu} } \date{\dateline{December 19, 2012}{-}{-}\\ \small Mathematics Subject Classifications: 05C78, 37A35, 37B40} \begin{document} \maketitle \begin{abstract} A labeling of a graph is a function from the vertex set of the graph to some finite set. Certain dynamical systems (such as topological Markov shifts) can be defined by directed graphs. In these instances, a labeling of the graph defines a continuous, shift-commuting factor of the dynamical system. We find sufficient conditions on the labeling to imply classification results for the factor dynamical system. We define the topological entropy of a (directed or undirected) graph and its labelings in a way that is analogous to the definition of topological entropy for a shift space in symbolic dynamics. We show, for example, if $G$ is a perfect graph, all proper $\chi(G)$-colorings of $G$ have the same entropy, where $\chi(G)$ is the chromatic number of $G$. % keywords are optional \bigskip\noindent \textbf{Keywords:} distinguishing labeling; entropy; finitary isomorphism; graph coloring; graph entropy; topological entropy \end{abstract} \section{Introduction} Let $G$ be an aperiodic irreducible directed graph on a finite set of vertices. Then $G$ (along with the shift map) defines a topological Markov chain $X$ where the symbols of $X$ are the vertices of $G$. Since the vertex set of $G$ is finite, $X$ has a finite alphabet. A labeling $f$ of $G$ is a function from the vertices of $G$ to some finite set. Examples of labelings include proper $k$-colorings and distinguishing labelings. A labeling of $G$ defines a continuous, shift-commuting factor map on $X$. The same holds when $X$ is given a shift invariant Markov measure. Call the image $Y$. Here, we ask what can we learn about the factor $Y$ from the labeling $f$. We define demarcating labelings of graphs and provide a class of factors of Markov processes defined by demarcating labelings that are finitarily isomorphic to Bernoulli schemes. We view graphs and their labelings as dynamical systems. We define the topological entropy of a (directed or undirected) graph and its labelings in a way that is analogous to the definition of topological entropy for a shift space in symbolic dynamics. We then bound and compute this entropy for certain classes of graphs. We show, for example, if $G$ is a perfect graph, all proper $\chi(G)$-colorings of $G$ have the same entropy, where $\chi(G)$ is the chromatic number of $G$. This does not hold for odd cycles of order greater than five. We define the entropy maximizing number of a graph to be the minimum number of labels necessary to label the graph so that the labeling has the same entropy as the graph. We show that for cycles, this number is no greater than three. \section{Entropy} \label{entropy} \subsection{Kolmogorov-Sinai Entropy} We are primarily interested in the measurable dynamical systems we call processes. A process is a quadruple $(X,\mathcal{U},\mu,T)$ where $X$ is the set of doubly infinite sequences on some alphabet $A$, $\mathcal{U}$ is the $\sigma$-algebra generated by the coordinates, $\mu$ is a shift invariant probability measure on $(X,\mathcal{U})$, and $T$ is the left shift by one. When we refer to a process $X$, we are referring to this quadruple. A process is a Bernoulli scheme if $\mu=p^{\mathbb{Z}}$ for some probability vector $p$. Building on the work of Shannon in \cite{Shan}, Kolmogorov introduced entropy into measurable dynamical systems \cite{Kolm}. See \cite{Walt} for a thorough introduction to entropy. Let $(X,\mathcal{U},\mu,T)$ and $(Y,\mathcal{V},\nu,S)$ be two processes. An isomorphism $\phi$ from $X$ to $Y$ is a bimeasurable equivariant map from a subset of $X$ of measure one to a subset of $Y$ of measure one which takes $\mu$ to $\nu$. If the map is not invertible, we say $\phi$ is a factor map (or that $Y$ is a factor of $X$). Ornstein proved that entropy is a complete isomorphism invariant for Bernoulli schemes \cite{O1}. Ornstein then showed that entropy is a complete isomorphism invariant for factors of Bernoulli schemes \cite{O2}. In 1979, Keane and Smorodinsky proved that entropy is a complete finitary isomorphism invariant for Bernoulli schemes \cite{KS1}. An isomorphism $\phi$ is finitary if for almost every $x \in X$ there exist integers $m \leq n$ such that the zero coordinates of $\phi(x)$ and $\phi(x')$ agree for almost all $x' \in X$ with $x[m,n]=x'[m,n]$, and similarly for $\phi^{-1}$. They then showed that two finite state Markov processes are isomorphic if and only if they have the same entropy and period \cite{KS2}. Rudolph was able to show that a countable state mixing Markov process is finitarily isomorphic to a Bernoulli scheme if and only if it has exponentially decaying return times \cite{R}. In unpublished work, Smorodinsky had previously shown that to be finitarily isomorphic to a Bernoulli scheme, a process must have exponentially decaying return times. See \cite{Ser} for more details on this result and finitary codes in general. \subsection{Topological Entropy} Motivated by the early success of Kolmogorov's entropy for measurable dynamical systems, Adler, Konheim and McAndrew developed a topological counterpart \cite{Adler}. Bowen \cite{B} and independently Dinaburg \cite{D} formulated a definition that is equivalent to that in \cite{Adler} on compact metric spaces. We will focus on the topological entropy of what is called a shift dynamical system. For a thorough introduction to symbolic dynamics, see \cite{LM}. Let $A$ be a finite set of states. The full shift $(A^{\mathbb{Z}},\sigma)$ is the set of all bi-infinite sequences of symbols in $A$ together with the shift map $\sigma$, where if $x \in A^{\mathbb{Z}}$, $(\sigma(x))_n=x_{n+1}$. A subshift (or shift space) $(X, \sigma)$ is a closed shift invariant subset of the full shift. Two-sided shift spaces are compact metric spaces. We say two shift spaces $(X,\sigma_1)$ and $(Y,\sigma_2)$ are topologically conjugate if there exists a homeomorphism $\phi: X \to Y$ such that $\phi \sigma_1= \sigma_2 \phi$. If we drop the condition that $\phi$ is invertible, we say $\phi$ is a factor map. Shifts of finite type (SFT) are shift spaces that can be described by some finite set of forbidden blocks. A shift space that is topologically conjugate to a SFT is itself a SFT. If a block is not forbidden, it is said to be allowable. A shift space is sofic if and only if it is a factor of a shift of finite type. Let $X$ be a subshift. Let $W_n$ be the set of allowable words in $X$ of length $n$. Let $|W_n|$ be the cardinality of $W_n$. Then the topological entropy of $X$ is \begin{equation} h_{top}(X)=\lim_{n \to \infty} \frac{ \log |W_n|}{n}. \end{equation} \noindent where we take $\log=\log_2$ (although one may choose any base). This definition is essentially equivalent to Shannon's notion of channel capacity for a discrete noiseless channel \cite{SW}. Many shift spaces can be described as walks on directed graphs. For a detailed introduction to graph theory, see \cite{CL}. A walk on a directed graph (or undirected graph) $G$ is a finite string of vertices in $V(G)$ $v_1,v_2,v_3...,v_k$ where $(v_i,v_{i+1}) \in E(G)$ for $1 \leq i \leq k-1$. The length of a walk $w=v_1,v_2,v_3...,v_k$, denoted $|w|$, is $k-1$. We say $G$ is irreducible if for any two vertices $u,v \in V(G)$, there exists a walk on $G$ beginning at $u$ and ending at $v$. Let our $G$ be an irreducible directed graph. The vertex shift $X_G$ is a shift space with states $V(G)$, and where the allowable blocks are the walks on $G$. Every SFT is topologically conjugate to a vertex shift \cite{LM}. The vertex shifts are sometimes called topological Markov shifts. We can relate the Kolmogorov-Sinai entropy of a process to the topological entropy of shift spaces as follows. Let $(X, \sigma)$ be a topological Markov chain. Let $M(X,\sigma)$ be the set of all $\sigma$-invariant probability measures on $X$. Let $h(X)$ be the topological entropy of $X$, and let $h_{\mu}(X)$ be the measure-theoretic entropy of $(X,\mu)$. Then, \begin{equation} \label{variation} h(X)=\sup\{h_{\mu}(T)| \mu \in M(X,\sigma)\}. \end{equation} \noindent Equation \ref{variation} is the variational principle. In \cite{D}, Dinaburg showed that for any metric space $X$ and continuous $\sigma: X \to X$, Equation \ref{variation} holds. If $X$ is a topological Markov chain, then $X$ has a unique measure of maximal entropy. That is, there exists a unique $\mu \in M(X,\sigma)$ such that $h_{\mu}(T) > h_{\mu'}(T)$ for any other $\mu' \in M(X,\sigma)$. Parry gave a formula for this measure (and proved his formula yielded the maximal entropy over all measures) \cite{Parry}. For this reason, the unique measure of maximal entropy for a topological Markov chain is sometimes called the Parry measure. While it was unknown to Parry at the time, and perhaps the dynamics community in general (as claimed in \cite{Kat}), Shannon had already found the formula for the measure of maximal entropy and showed it was maximal over all Markov measures. For more details on the variational principle and Parry measure, see Chapter 8 of \cite{Walt}. \subsection{Topological Graph Entropy} Let $G$ be a graph (or directed graph) with at most one edge between any two vertices. Let $W_k$ be the set of walks on $G$ of length $k-1$. We will only consider graphs where $W_k$ is nonempty for every positive integer $k$. Let $|W_k(G)|$ be the cardinality of $W_k$. \begin{defn} \label{graphent} The topological graph entropy of $G$ is \begin{center} $h_{top}(G)=\lim_{n\to \infty} \frac{log_2 (|W_n(G)|)}{n}$. \end{center} \end{defn} Let $f$ be a labeling of the vertices of $G$. A walk of length $k-1$ on the $f$ labeling of $G$ is a finite string $f(v_1),f(v_2),...,f(v_k)$, where $(v_i,v_{i+1}) \in E(G)$ for $1 \leq i \leq k-1$. Let $f(W_k(G))$ be the set of walks of length $k-1$ on the $f$ labeling of $G$. Let $|f(W_k(G))|$ be the cardinality of $f(W_k(G))$. \begin{defn} \label{labelent} The topological graph entropy of the $f$ labeling of $G$ is \begin{center} $h_{top}(f, G)=\lim_{n\to \infty} \frac{log_2 (|f(W_n(G))|)}{n}$. \end{center} \end{defn} Note that Definitions \ref{graphent} and \ref{labelent} are analogous to the definitions of topological entropy of a topological Markov chain and the continuous image of a topological Markov chain, respectively. Since every SFT is topologically conjugate to a topological Markov chain and sofic shifts are continuous factors of SFTs, Definitions \ref{graphent} and \ref{labelent} are analogous to the topological entropy of a SFT and sofic shift, respectively. \section{A Labeling Defines a Factor} \label{labdefinesfactor} We have and will continue to assume our graphs have finite vertex sets and that our dynamical systems have finite alphabets. In this section, we describe how a labeling of a directed graph can correspond to a continuous factor of a measurable or topological dynamical system. We then provide the details of our conjecture from \cite{LS} that relates distinguishing labelings to continuous factors of Bernoulli schemes. Let $X$ be a process (resp. subshift). Let $k$ be a positive integer. The process (resp. subshift) $X^{(k)}$ called the $k$-stringing (as in \cite{Sm}) or $k$-block presentation (as in \cite{LM}) of $X$ is defined as follows. The state space of $X^{(k)}$ is all allowable sequences of length $k$ in $X$, and $X_n^{(k)}=(X_n, X_{n+1},...,X_{n+k-1})$. A 1-block factor of a process or subshift $X$ is a function on the alphabet of $X$. The Curtis-Hedlund-Lyndon Theorem tells us that any continuous, shift-commuting factor map $f$ on $X$ is a finite map on $X$ \cite{Hed}. A map $f$ is finite if there exist nonnegative integers $m$ and $n$ such that for any $x \in X$, $f(x)_0=f(x_{-m}x_{-m+1}\ldots x_{n-1}x_n)_0$. That is to say, (up to a possible shift left by some finite number of coordinates), $f(X)$ is a 1-block factor of $X^{(k)}$ for some positive integer $k$. Let $X$ have alphabet $A$. Let $a \in A$ where $P(X_n=a)>0$. We say $a$ is a renewal state of $X$ if the $\sigma$-algebras $\mathcal{U}(X_{n+1},X_{n+2},...)$ and $\mathcal{U}(...,X_{n-2},X_{n-1})$ are independent given the event $[X_n=a]$. If there exists such an $a$, we say $X$ is a renewal process. A process $X$ is Markov if for all $a \in A$ where $P(X_n=a)>0$, $a$ is a renewal state in $X$. A process $Y$ is $k$-step Markov if $Y^{(k)}$ is Markov. A process $Z$ is variable length Markov if for some positive integer $k$, $Z^{(k)}$ is a renewal process. In 1983, Rissanen \cite{Ri} introduced the class of models we are calling variable length Markov processes. These processes have gone by several names including finitarily Markovian processes (\cite{MW}). Let $X_G$ be a topological Markov chain (vertex shift) associated with an irreducible directed graph $G$. Assign probabilities to the edges of $G$ so that for any vertex $v \in V(G)$, the sum of the probabilities of the outgoing edges of $v$ is one. Then there is a finite state Markov process $X$ defined by the directed graph $G$ where $P[X_{n+1}=v|X_n=u]=0$ if $(u,v) \not \in E(G)$ and otherwise, $P[X_{n+1}=v|X_n=u]=p$ where $p$ is the probability assigned to edge $(u,v)$. Suppose $X$ is a finite state Markov process defined by an irreducible directed graph $G$. For each $k \in \mathbb{Z^{+}}$, let $G_k$ be the directed graph where $V(G_k)$ is the state space of $X^{(k)}$, and $(u,v) \in E(G_k)$ if and only if $p[X^{(k)}_1=v|X^{(k)}_0=u]>0$. Then any continuous, shift-commuting factor of $X$ is a labeling of the vertices of $G_k$ for some positive integer $k$. For example, let $X$ be a Bernoulli scheme (or the full shift) on two symbols $0$ and $1$. Then for $k=1$, we have the graph in Figure 3.1. $G_2$ is the graph in Figure 3.2. If $X$ is an $m$-state Bernoulli scheme, then the $G_k$ are the De Bruijn graphs \cite{Bruijn}. \begin{multicols}{2} \begin{center} $\xymatrix{{0} \ar@(dl,ul)\ar@/^/[r]&{1} \ar@(dr,ur) \ar@/^/[l]}$\\ \bigskip Figure 3.1 \end{center} \begin{center} $\xymatrix{{00} \ar@(dl,ul)\ar@//[r]&{01}\ar@//[dl] \ar@//[d]\\ {10}\ar@//[u]\ar@//[ur]&{11}\ar@(dr,ur)\ar@//[l]}$\\ \bigskip Figure 3.2 \end{center} \end{multicols} Similarly, we can let $X$ be a SFT. Then $X$ can be described by a finite directed graph. For each $k \in \mathbb{Z^{+}}$, let $G_k$ be the directed graph where $V(G_k)$ is the state space of $X^{(k)}$, and $(u,v) \in E(G_k)$ if and only if $uv$ is not a forbidden word in $X^{(k)}$. Note that $k$-block presentation is a topological conjugacy and that any process that is topologically conjugate to a SFT is a SFT. Thus, $X^{(k)}$ is a SFT and $G_k$ is well-defined. Then any continuous factor of $X$ is a labeling of the vertices of $G_k$ for some positive integer $k$. For any (undirected or directed) graph $G$ that contains arbitrarily long walks, we can define $G_k$ (for $k \geq 2$) without going through a process or shift space. We define $V(G_k)$ to be the set of all walks in $k$ of length $k-1$, and we let $(u,v) \in E(G_k)$ if and only if when $u=v_1v_2...v_k$ then $v=v_2v_3...v_{k-1}v'$ for some $v' \in V(G)$ (where $v$ is again a walk of length $k-1$ in $G$). Call $G_k$ the $k$-block presentation of $G$. The line graph of a graph $G$, denoted $L(G)$ has vertex set $V(L(G))=E(G)$, and for $(u_1,v_1)$ and $(u_2,v_2)$ in $V(L(G))$, $((u_1,v_1),(u_2,v_2)) \in E(L(G))$ if and only if $v_1=u_2$. We remark that if $G$ is undirected, $G_2$ is not necessarily isomorphic to $L(G)$. Consider the path $P_3$ in Figure 3.3. The line graph of $P_3$ is just $P_2$, the graph shown in Figure 3.4. However, $G_2$ is the graph in Figure 3.5. In this example, we see how taking the $k$-block presentation of an undirected graph can be a directed graph. \begin{multicols}{3} \begin{center} $\xygraph{ !{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::} !{(0,0) }*+{{a}} ="a" !{(1,0) }*+{{b}} ="b" !{(2,0) }*+{{c}} ="c" "a"-"b" "b"-"c" } $\\ Figure 3.3: $P_3$ \end{center} \bigskip \begin{center} $\xygraph{ !{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::} !{(0,0) }*+{{ab}} ="a" !{(1,0) }*+{{bc}} ="b" "a"-"b" } $\\ Figure 3.4: $L(P_3)$ \end{center} \bigskip \begin{center} $\xygraph{ !{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::} !{(0,0) }*+{{ab}} ="a" !{(0,1) }*+{{ba}} ="b" !{(1,0) }*+{{bc}} ="c" !{(1,1)}*+{{cb}} ="d" "a":"b" "b":"a" "c":"d" "d":"c" "a":"c" "d":"b" } $\\ Figure 3.5: $(P_3)_2$ \end{center} \end{multicols} It is a simple exercise to show that for a directed graph $G$, $G_{k+1}$ is isomorphic to the $k$th iterate of the line graph on $G$. If we interpret $P_3$ as a directed graph $G$ with $(u,v)\in E(P_3)$ whenever $(v,u) \in E(P_3)$. Then $L(G) \cong (P_3)_2=G_2$. Let $f$ be a labeling on some $G_k$. We will refer to the finite factor map defined by $f$ with $f$ as well, writing $f:X\to Y$. If $X$ is a Markov process with measure $\mu$, then $Y$ has measure $f(\mu)$. In 1996, Albertson and Collins defined distinguishing labelings of undirected graphs. An automorphism $A$ of a graph $G$ is a permutation $p$ of $V(G)$ that preserves edge connectivity (i.e. $(p(u),p(v)) \in E(A(G))$ whenever $(u,v)\in E(G)$). A labeling of the vertices of a graph $G$, $f: V(G) \to \{1,2,...,r\}$, is $r$-distinguishing if the only automorphism of the graph that preserves all of the vertex labels is the identity. The distinguishing number of a graph $G$, denoted by $D(G)$, is the minimum $r$ such that $G$ has an $r$-distinguishing labeling \cite{AC}. In \cite{LS}, we conjecture the following. \begin{conjecture} \label{conj} Let $X=\{0,1\}^{\mathbb{Z}}$ with measure $\mu=(p_0,p_1)^{\mathbb{Z}}$ where $p_0 \not = p_1$. Let $G$ be the graph in Figure 3.1. Let $k>1$, and let $f$ be a labeling of $G_k$. Let $f: X \to Y$ denote the finite factor map defined by $f$. Then $Y$ is variable length Markov if and only if $f$ is $r$-distinguishing. \end{conjecture} \section{Distinguishing Labelings of Block Presentations of\\ Full Shifts} \label{distlabfull} We determine the automorphism group and distinguishing labelings of the graphs corresponding to $k$-block presentations of a full shift on $m$-symbols. When $m=2$, we get the automorphism group and distinguishing labelings for the $G_k$ in Conjecture \ref{conj}. Our work in this section generalizes some of the results in \cite{LS}. Let $m$ and $k$ be positive integers. Let \begin{center} $W(m,k)=\{x_1x_2...x_k| x_i \in \{1,2,3,...,m\}$ for $1 \leq i \leq k\}$. \end{center} \noindent In other words, $W(m,k)$ is the set of all $m$-ary blocks of length $k$. Let $G_{m,k}$ be a digraph where $V(G_{m,k})=W(m,k)$ and for $x=x_1x_2...x_k$ and $y=y_1y_2...y_k$ in $V(G_{m,k})$, $(x,y) \in E(G_{m,k})$ if and only if $y_i=x_{i+1}$ for all $i$ where $1 \leq i \leq k-1$. We will need the following lemmas. \begin{lem} \label{aut} Let $G$ be a directed graph. Let $p$ be an automorphism of $G$. Define a function $A$ on $V(G_k)$ where for $v=v_1v_2...v_k \in V(G_k)$, $A(v)=p(v_1)p(v_2)...p(v_k)$. Then $A$ is an automorphism of $G_k$. \end{lem} \begin{proof} Since $p$ is an automorphism of $G$, $(p(u),p(v)) \in E(G)$ whenever $(u,v) \in E(G)$. Then $p(v_1)p(v_2)...p(v_k)$ is a walk in $G_k$ whenever $v_1v_2...v_k$ is a walk in $G_k$. Thus, $A$ is a permutation of $V(G_k)$. Let $(u,v) \in E(G_k)$. If $u=u_1u_2...u_k$, $v=u_2u_3...u_kv'$ for some vertex $v' \in V(G)$ where $(u_k,v') \in E(G)$. Then $A(u)=p(u_1)p(u_2)...p(u_k)$ and$A(v)=p(u_2)p(u_2)...p(u_k)p(v')$. Therefore, $(A(u),A(v)) \in E(G_k)$. \end{proof} A walk $w$ on a graph $G$ from vertex $u$ to vertex $v$ is minimal if there does not exist a walk $w'$ on $G$ from $u$ to $v$ where $|w'|<|w|$. The proof of the following follows the proof of Lemma 3.7 in \cite{LS} with minor modifications. \begin{lem} \label{minwalk} Let $u$ and $v$ be distinct vertices in $G_{m,k}$. There exists a unique minimal walk in $G_{m,k}$ from $u$ to $v$. \end{lem} \begin{lem} \label{permwalk} Let $A$ be an automorphism of $G_{m,k}$. Let $u=u_1u_2...u_k$ and $v=v_1v_2...v_k$ be distinct vertices in $G_{m.k}$. Suppose there exists a permutation $p$ of $\{1,2,...,m\}$ such that $A(u)=p(u_1)p(u_2)...p(u_k)$ and $A(v)=p(v_1)p(v_2)...p(v_k)$. Let $w=u,a_1,a_2,...,a_n,v$ be the unique minimal walk from $u$ to $v$ in $G_{m,k}$. Then for any vertex $a_i=a_{i1}a_{i2}...a_{ik}$ on the minimal walk from $u$ to $v$, $A(a_i)=p(a_{i1})p(a_{i2})...p(a_{ik})$. \end{lem} \begin{proof} By Lemma \ref{minwalk}, there exists a minimal walk from $u$ to $v$ and from $A(u)$ to $A(v)$. Let $w=u,a_1,a_2,...,a_n,v$ be the unique minimal walk from $u$ to $v$ in $G_{m,k}$. Then for any $a_i=a_{i1}a_{i2}...a_{ik}$ where $1 \leq i \leq n$, let $A'(a_i)=p(a_{i1})p(a_{i2})...p(a_{ik})$. Then $\hat w=A(u),A'(a_1),A'(a_2),...,A'(a_n),A(v)$ is a walk from $A(u)$ to $A(v)$. Suppose there exists a shorter walk from $A(u)$ to $A(v)$. Then for some $n'0$ for all $n>N$. We are interested in \begin{equation} L(x,x')=\lim_{n\to \infty} \frac{M_n(x,x')}{H_n(x,x')}. \end{equation} For any process $X$, any $x,x' \in X$, and any $n \in \mathbb{N}$, $M_n(x,x') \leq 1$. If $x$ and $x'$ differ on infinitely many coordinates, $L(x,x')= 0$. \begin{thm} \label{main} Let $Y=\{0,1\}^{\mathbb{Z}}$ be a Bernoulli scheme with measure $\nu=(\frac{1}{3},\frac{2}{3})^{\mathbb{Z}}$. Let $\phi:Y \to X$ where $(\phi(y))_i=(y_i+y_{i+1})\mod 2$. For almost all $x \in X$, there exists $x' \in X$ such that $\mu(x'[-n,n])>0$ for all $n \in \mathbb{N}$ and $L(x,x')=1$. \end{thm} \begin{proof} Let $x \in X$. There are two words of length $n+1$ in $Y$ that map to $x[-n,-1]$ under $\phi$. Let $A_n$ and $B_n$ be these two words. So, if $\phi(y)[-n,-1]=x[-n,-1]$, then $0 < \nu(y[-n,0]=A_n) < 1$ and $0 < \nu(y[-n,0]=B_n) < 1$. We will refer to $A_n$ and $B_n$ as the possible pre-images of $x[-n,-1]$. Notice that $A_n$ and $B_n$ are duals of each other. That is, $A_n$ is obtained from $B_n$ by replacing every $0$ with a $1$ and every $1$ with a $0$. Let $A_n(0 )=$ card$\{y_i | -n \leq i \leq 0$, $y_i=0$ and $y[-n,0]=A_n\}$. Let $B_n(0)=$ card$\{y_i | -n \leq i \leq 0$, $y_i=0$ and $y[-n,0]=B_n\}$. Then $B_n(0)=n+1-A_n(0)$. For almost all $x\in X$, as $n\to \infty$, either \begin{equation} \label{x1} \mbox{(i) } \frac{A_n(0)}{n+1} \to \frac{1}{3} \mbox{ and } \frac{B_n(0)}{n+1} \to \frac{2}{3} \mbox{ or } \end{equation} \begin{equation} \label{x2} \mbox{(ii) } \frac{B_n(0)}{n+1} \to \frac{1}{3} \mbox{ and } \frac{A_n(0)}{n+1} \to \frac{2}{3}. \end{equation} \noindent In case (i), we obtain that $A_n$ is the true pre-image of $x[-n,-1]$ and in case (ii), $B_n$ is the true pre-image of $x[-n,-1]$. Let $C_n$ and $D_n$ be the two possible pre-images of $x[1,n]$. Let $C_n(0)=$ card$\{y_i | 1 \leq i \leq n+1$, $y_i=0$ and $y[1,n+1]=C_n\}$. Let $D_n(0)=$ card$\{y_i | 1 \leq i \leq n+1$, $y_i=0$ and $y[1,n+1]=D_n\}$. Then $D_n(0)=n+1-C_n(0)$. For almost all $x\in X$, as $n\to \infty$, (analogous to equations \ref{x1} and \ref{x2}) either \begin{equation} \label{x3} \mbox{(i) } \frac{C_n(0)}{n+1} \to \frac{1}{3} \mbox{ and } \frac{D_n(0)}{n+1} \to \frac{2}{3} \mbox{ or } \end{equation} \begin{equation} \label{x4} \mbox{(ii) } \frac{D_n(0)}{n+1} \to \frac{1}{3} \mbox{ and } \frac{C_n(0)}{n+1} \to \frac{2}{3}. \end{equation} \noindent In case (i), we obtain that $C_n$ is the true pre-image of $x[1,n]$ and in case (ii), $D_n$ is the true pre-image of $x[1,n]$. Now let $x$ be such that either equation \ref{x1} or \ref{x2} is satisfied and either equation \ref{x3} or \ref{x4} is satisfied. If for $x' \in X$, $L(x,x')=1$, then $x$ and $x'$ differ at only one coordinate. Without loss of generality suppose $x$ and $x'$ differ on the zeroth coordinate. The block $x[-n,n]$ has two possible pre-images. They are either $A_nC_n$ and $B_nD_n$ or $A_nD_n$ and $B_nC_n$. Without loss of generality, suppose the possible pre-images are $A_nC_n$ and $B_nD_n$. Then, since $x'$ differs from $x$ at only the zeroth coordinate, the possible pre-images of $x'[-n,n]$ are $A_nD_n$ and $B_nC_n$. $Y$ has measure $\nu$. Then $\mu(x'[-n,n])=\nu(A_nD_n)+\nu(B_nC_N)$, and $\mu(x[-n,n])=\nu(A_nC_n)+\nu(B_nD_N)$. Since $Y$ is a Bernoulli scheme, $\nu(A_nD_n)>0$ and $\nu(B_nC_n)>0$. Therefore, $\mu(x'[-n,n])>0$. We have that \begin{equation} M_n(x,x')=\frac{|(\nu(A_nC_n)+\nu(B_nD_N))-(\nu(A_nD_n)+\nu(B_nC_N))|}{(\nu(A_nC_n)+\nu(B_nD_N))+(\nu(A_nD_n)+\nu(B_nC_N))}. \end{equation} \noindent By equations \ref{x1} through \ref{x4}, for large $n$, $M_n(x,x')$ \begin{equation} \approx \frac{[(1/3)^{\frac{2n+1}{3}}(2/3)^{\frac{4n+2}{3}}+(2/3)^{\frac{2n+1}{3}}(1/3)^{\frac{4n+2}{3}}]-[(1/3)^{n+\frac{1}{2}}(2/3)^{n+\frac{1}{2}}+(2/3)^{n+\frac{1}{2}}(1/3)^{n+\frac{1}{2}}]}{[(1/3)^{\frac{2n+1}{3}}(2/3)^{\frac{4n+2}{3}}+(2/3)^{\frac{2n+1}{3}}(1/3)^{\frac{4n+2}{3}}]+[(1/3)^{n+\frac{1}{2}}(2/3)^{n+\frac{1}{2}}+(2/3)^{n+\frac{1}{2}}(1/3)^{n+\frac{1}{2}}]} \end{equation} \noindent This simplifies to \begin{equation} M_n(x,x') \approx \frac{(2^{\frac{2n+1}{3}}+1)-(2(2)^{\frac{2n+1}{6}})}{(2^{\frac{2n+1}{3}}+1)+(2(2)^{\frac{2n+1}{6}})}. \end{equation} \noindent Then, \begin{equation} \lim_{n\to \infty} M_n(x,x')= \lim_{n\to\infty} \frac{(2^{\frac{2n+1}{6}})-2}{(2^{\frac{2n+1}{6}})+2}=1. \end{equation} \noindent Since $H_n(x,x')=1$ for all $n$, we find that $L(x,x')=1$. \end{proof} The property of Theorem \ref{main} is an unusual property. It cannot exist in a process that is variable length Markov. \begin{thm} \label{Var} Let $X$ be a variable length Markov process. For almost all $x \in X$, there does not exist $x' \in X$ such that $\mu(x'[-n,n])>0$ for all $n \in \mathbb{N}$ and $L(x,x')=1$. \end{thm} \begin{proof} Since $X$ is variable length Markov, there exists a word $R$ with length $|R|$ in $X$ such that the $\sigma$-algebras $\mathcal{U}(X_{|R|+1},X_{|R|+2},...)$ and $\mathcal{U}(...,X_{-1},X_{0})$ are independent given the event $X[1,|R|]=R$. For almost all $x\in X$, for all $n\in \mathbb{N}$, there exists an integer $n_1 < -n$ such that $x[n_1+1,n_1+|R|]=R$ and a positive integer $n_2 > n$ such that $x[n_2+1, n_2+|R|]=R$. Let $x$ be one of these points. Suppose $x' \in X$ such that $L(x,x')=1$. Then $x$ and $x'$ differ on only 1 coordinate. Suppose that coordinate is $j$. Let $n_1, n_2 \in \mathbb{Z}$ be such that $x[n_1+1,n_1+|R|]=x'[n_1+1,n_1+|R|]=R$, $x[n_2+1,n_2+|R|]=x'[n_2+1,n_2+|R|]=R$ and $n_1+|R| < j < n_2+1$. Let $N > \max\{|n_1+1|, |n_2+|R||\}$. For $n>N$, let \begin{equation} \alpha=\frac{\mu(x[-n,n_1] \cap x[n_1+1,n_1+|R|])}{\mu(x[n_1+1,n_1+|R|])}, \end{equation} \noindent and \begin{equation} \beta=\frac{\mu(x[n_2+1,n_2+|R|]\cap x[n_2+|R|+1,n])}{\mu(x[n_2+1,n_2+|R|])}. \end{equation} \noindent Since $n_1+|R| < j < n_2+1$, \begin{equation} \alpha=\frac{\mu(x'[-n,n_1] \cap x'[n_1+1,n_1+|R|])}{\mu(x'[n_1+1,n_1+|R|])}, \end{equation} \noindent and \begin{equation} \beta=\frac{\mu(x'[n_2+1,n_2+|R|]\cap x'[n_2+|R|+1,n])}{\mu(x'[n_2+1,n_2+|R|])}. \end{equation} \noindent Since $R$ is a renewal state in $X^{(|R|)}$, for all $n>N$, \begin{equation} \mu(x[-n,n])=(\alpha) \mu(x[n_1+1,n_2+|R|])(\beta), \end{equation} \noindent and \begin{equation} \mu(x'[-n,n])=(\alpha) \mu(x'[n_1+1,n_2+|R|])(\beta). \end{equation} \noindent Then, for all $n>N$, \begin{equation} \label{M1} M_n(x,x')=\frac{|(\alpha) \mu(x[n_1+1,n_2+|R|])(\beta)-(\alpha) \mu(x'[n_1+1,n_2+|R|])(\beta)|}{(\alpha) \mu(x[n_1+1,n_2+|R|])(\beta)+(\alpha) \mu(x'[n_1+1,n_2+|R|])(\beta)} \end{equation} \begin{equation} \label{M2} =\frac{|\mu(x[n_1+1,n_2+|R|])- \mu(x'[n_1+1,n_2+|R|])|}{\mu(x[n_1+1,n_2+|R|])+ \mu(x'[n_1+1,n_2+|R|])}. \end{equation} By equations \ref{M1} and \ref{M2}, for all $n>N$, $M_n(x,x')=M_N(x,x')$. Therefore, $L(x,x')=M_N(x,x')$. If $M_N(x,x')=1$, then $\mu(x'[-N,N])=0$. This contradicts that $\mu(x'[-n,n])>0$ for all $n \in \mathbb{N}$. Therefore, for almost all $x \in X$, there does not exist $x' \in X$ such that $\mu(x'[-n,n])>0$ for all $n \in \mathbb{N}$ and $L(x,x')=1$. \end{proof} Theorems \ref{main} and \ref{Var} imply the following corollary. \begin{cor} \label{xnotvar} Let $Y=\{0,1\}^{\mathbb{Z}}$ be a Bernoulli scheme with measure $\nu=(\frac{1}{3},\frac{2}{3})^{\mathbb{Z}}$. Let $\phi:Y \to X$ where $(\phi(y))_i=(y_i+y_{i+1})\mod 2$. Then $X$ is not variable length Markov. \end{cor} There are more direct proofs that our example process $X$ in Corollary \ref{xnotvar} is not variable length Markov. We believe the specific property of the conclusion of Theorem \ref{main} is interesting in its own right. For simplicity, we chose a probability vector of $(1/3,2/3)$ for the Bernoulli scheme $Y$ in Theorem \ref{main}, but any measure $(p,1-p)^{\mathbb{Z}}$ where $p \not = 1/2$ will yield the same result. \section{Entropy of Chromatic Labelings} \label{entchrom} For the rest of the article, entropy of a graph $G$ means topological graph entropy, and we will drop the subscript $top$ in $h_{top}(G)$. The degree of a vertex $v$, denoted $deg(v)$, is the number of vertices in $G$ that are adjacent to $v$. We let $\Delta(G)=\max_{v \in V(G)}\{deg(v)\}$ and $\delta(G)=\min_{v \in V(G)}\{deg(v)\}$. If all vertices $v \in V(G)$ have degree $m$, we say $G$ is $m$-regular. Let $G$ be a directed graph. The outgoing degree of $v \in V(G)$, denoted $od(v)$, is the number of vertices $u \in V(G)$ such that $(v,u) \in E(G)$. We will say $G$ is $m$-regular if $od(v)=m$ for all $v \in V(G)$. We denote the clique number of $G$ by $\omega(G)$. Perron-Frobenius theory can often be used to compute the topological entropy of a graph and its labelings. We refer the reader to \cite{LM} for a more detailed description of the applications of Perron-Frobenius theory in entropy calculations. The following results follow directly from this theory. \begin{lem} \label{reg} Let $G$ be an $m$-regular graph (directed or undirected). Then $h(G)=\log m$. \end{lem} \begin{lem} \label{deltabounds} Let $G$ be an undirected graph. Then, $\log(\delta(G)) \leq h(G) \leq \log(\Delta(G))$. In particular, $\log ((\omega(G))-1) \leq h(G) $. \end{lem} We will say a coloring of $G$ is a chromatic labeling if it is a proper $\chi(G)$-coloring of $G$, where $\chi(G)$ is the chromatic number of $G$. For the rest of this section, we will assume our graphs do not have self loops (edges $(u,u)$). \begin{lem} \label{cliquechrom} Let $G$ be an undirected graph. Let $f$ be a proper $r$-coloring of $G$. Then \begin{center} $\log (\omega(G)-1) \leq h(f,G) \leq \log (r-1)$. \end{center} \end{lem} \begin{proof} Let $\{v_1,v_2,...,v_m\}$ be a clique in $G$. Since $f$ is proper, $f(v_i) \not = f(v_j)$ when $i \not = j$. Then the number of distinct walks of length $k-1$ on $\{f(v_1),f(v_2),...,f(v_m)\}$ is $m(m-1)^{k-1}$. Any walk on the labeling of this clique is a walk on the labeling of $G$. Therefore, $|f(W_k(G))| \geq m(m-1)^k$. It follows that $\log (m-1) \leq h(f,G)$. Since $\omega(G)$ is the order of the largest clique in $G$, $\log (\omega(G)-1) \leq h(f,G)$. Let $C=\{c_1, c_2, ..., c_{r}\}$ be the colors used in the proper coloring of $G$. We have $|f(W_k(G))| \leq r(r-1)^{k-1}$. Therefore, \begin{center} $h(f,G) \leq \lim_{k \to \infty} \frac{k \log(r-1)}{k}=\log (r-1)$. \end{center} \end{proof} \noindent In particular, if $f$ is a chromatic labeling of $G$, Lemma \ref{cliquechrom} implies \begin{equation} \label{cliqchrom} \log (\omega(G)-1) \leq h(f,G) \leq \log (\chi(G)-1). \end{equation} Note that there are graphs with small clique number and large chromatic number. Mycielski's Theorem states that for all integers $k \geq 2$, there exists a graph $G$ with clique number $2$ and chromatic number $k$ \cite{Myc}. So, for certain classes of graphs, these bounds may not yield a lot of information. For other classes of graphs, such as perfect graphs, the bounds yield more information. A graph is perfect if each of its vertex induced subgraphs $H$ is such that the chromatic number of $H$ is equal to the clique number of $H$. Lemma \ref{cliquechrom} implies the following. \begin{thm} \label{perchrom} Let $G$ be an undirected perfect graph with $\chi(G)>1$. Then for any chromatic labeling $f$ of $G$, \begin{center} $h(f,G)=\log(\omega(G)-1)=\log (\chi(G)-1)$. \end{center} \end{thm} We can extend Theorem \ref{perchrom} to certain graphs that are not perfect. \begin{thm} \label{nonperchrom} Let $G$ be an undirected graph with $\chi(G)>1$. If $G$ has a clique of size $\chi(G)$, then for any chromatic labeling $f$ of $G$, \begin{center} $h(f,G)=\log(\omega(G)-1)=\log (\chi(G)-1)$. \end{center} \end{thm} \begin{proof} $G$ cannot have a clique of size greater than $\chi(G)$. So, if $G$ has a clique of size $\chi(G)$, then $\chi(G)=\omega(G)$. We apply Lemma \ref{cliquechrom} to see that $h(f,G)=\log(\omega(G)-1)=\log (\chi(G)-1)$. \end{proof} We now present an example of an undirected graph that has chromatic labelings with different entropies. By Theorem \ref{nonperchrom}, such an example cannot have a clique as large as the chromatic number of the graph. \begin{ex} \label{cycleex} Consider the undirected odd cycle $C_9$. Let $f$ (resp. $g$) be the labeling of $C_9$ in Figure 6.1 (resp. Figure 6.2). For every vertex $v \in C_9$, $v$ is adjacent to two vertices, say $u$ and $u'$. The coloring $g$ is such that $g(u') \not = g(u)$. Therefore, $h(g,C_9)=\log 2$. The labeling $f$ assigns one vertex the color $r$, and alternates $b$ and $w$ otherwise. We thank \cite{stack} for the following calculation. We will find a generating function $G(x)$ where the coefficient of $x^k$ is (neglecting finite-size effects) $|f(W_k(C_9))|$. Counting the walks from $r$, we have the choice to go to either side of $r$. Once we have decided which way to move, we can either traverse at least $8$ vertices and then return to $r$ from the the other side of $r$, or we can return to $r$ from the same side that we left on. This yields a generating function $G(x)=\sum_{i=0}^\infty u^i$ where $u=2x[x(1+x^2+x^4+...)][x^8(1+x^2+x^4+...)]=\frac{2x(x+x^8)}{1-x^2}$. Then, \begin{equation} G(x)=\frac{1}{1-u}=\frac{1}{1-\frac{2x(x+x^8)}{1-x^2}}=\frac{1-x^2}{1-3x^2-2x^9}. \end{equation} \noindent The exponential growth formula of \cite{FS} implies that the growth rate of the coefficients of $G(x)$ (and thus, the set $f(W_k(C_9))$) is the inverse of the absolute value of the singularity of $G(x)$ nearest the origin. Here we find that singularity to be approximately .5734. This gives a growth rate of approximately 1.744. Thus, $h(f,C_9) \approx \lim_{n \to \infty} \frac{\log (1.744^n)}{n}=\log 1.744$. \begin{multicols}{2} \begin{center} $\xygraph{ !{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::} !{(0,.5) }*+{\bullet_{r}} ="a" !{(1,1) }*+{\bullet_{b}} ="b" !{(2,1) }*+{\bullet_{w}} ="c" !{(3,1)}*+{\bullet_{b}} ="d" !{(4,1) }*+{\bullet_{w}} ="e" !{(4,0) }*+{\bullet_{b}} ="f" !{(3,0) }*+{\bullet_{w}} ="g" !{(2,0)}*+{\bullet_{b}} ="h" !{(1,0)}*+{\bullet_{w}} ="i" "a"-"b" "b"-"c" "c"-"d" "d"-"e" "e"-"f" "f"-"g" "g"-"h" "h"-"i" "i"-"a" } $\\ Figure 6.1 \end{center} \begin{center} $\xygraph{ !{<0cm,0cm>;<1cm,0cm>:<0cm,1cm>::} !{(0,.5) }*+{\bullet_{r}} ="a" !{(1,1) }*+{\bullet_{b}} ="b" !{(2,1) }*+{\bullet_{w}} ="c" !{(3,1)}*+{\bullet_{r}} ="d" !{(4,1) }*+{\bullet_{b}} ="e" !{(4,0) }*+{\bullet_{w}} ="f" !{(3,0) }*+{\bullet_{r}} ="g" !{(2,0)}*+{\bullet_{b}} ="h" !{(1,0)}*+{\bullet_{w}} ="i" "a"-"b" "b"-"c" "c"-"d" "d"-"e" "e"-"f" "f"-"g" "g"-"h" "h"-"i" "i"-"a" } $\\ Figure 6.2 \end{center} \end{multicols} \end{ex} We now generalize Example \ref{cycleex}. \begin{thm} \label{oddcyclediff} For any odd cycle $C_n$ where $n > 5$, there exist proper 3-colorings of $C_n$, $f$ and $g$, such that $h(f,C_n) \not = h(g,C_n)$. \end{thm} \begin{proof} Let $n$ be an odd integer $>5$. Let $f$ be the proper 3-coloring of $C_n$ where one vertex is colored $r$ and we alternate $bw$ otherwise ($bwbw...bwr$ coloring). Let $g$ be the proper 3-coloring of $C_n$ defined as follows. For $n=3 \mod 3$, or $n=2 \mod 3$, $g$ repeats the pattern $rbw$. For example, $C_9$ can be colored $rbwrbwrbw$ and $C_{11}$ can be colored $rbwrbwrbwrb$. For $n=1 \mod 3$, $g$ repeats the pattern $rbw$ for $n-1$ consecutive vertices, and then fills in appropriately (with a $b$) the last vertex so that the coloring remains proper. For example, $C_7$ can be colored $rbwrbwb$. We begin by showing that if for some odd integer $n$, $h(f,C_n) \not = h(g,C_n)$, then $h(f,C_{n+6}) \not = h(g, C_{n+6})$. Since $f$ and $g$ are proper colorings, the words $rr$, $ww$ and $bb$ are always forbidden. In addition, the set $f(W_k(C_n))$ forbids $r(bg)^mr$ and $r(gb)^mr$ for all $m$ in $[1,\frac{n-3}{2}]$ (when $k>n$). This completely characterizes $f(W_k(C_n))$. So, for $k>(n+2)$, $|f(W_k(C_n))|>|f(W_k(C_{n+2}))|$. If $n$ is a multiple of $3$, then $g(W_k(C_n))$ only forbids $rr$, $bb$, and $ww$. We know that $h(g,C_n)=\log 2=h(C_n)$. So, if $n$ is a multiple of $3$ and $h(f,C_n) \not = h(g,C_n)$, then $h(f, C_{n+6}) \not = h(g,C_{n+6})$. Now suppose $n=2 \mod 3$. The set $g(W_k(C_n))$ for $k>n$ is characterized by the forbidden words $rr$, $bb$, $ww$, $(wrb)^{\frac{n-2}{3}}w$, and $(wbr)^{\frac{n-2}{3}}w$. So, for $k>(n+6)$, $|g(W_k(C_n))|<|g(W_k(C_{n+6}))|$. Since, for $k>(n+2)$, $|f(W_k(C_n))|>|f(W_k(C_{n+2}))|$, if $h(f,C_n) \not = h(g,C_n)$, then $h(f,C_{n+6})\not = h(g, C_{n+6})$. Finally, suppose $n=1 \mod 3$. The set $g(W_k(C_n))$ for $k>n$ is characterized by the forbidden words $rr$, $bb$, $ww$, $(wrb)^{\frac{n-4}{3}}wr$, and $(rwb)^{\frac{n-4}{3}}rw$. So, for $k>(n+6)$, $|g(W_k(C_n))|<|g(W_k(C_{n+6}))|$. Since, for $k>(n+2)$, $|f(W_k(C_n))|>|f(W_k(C_{n+2}))|$, if $h(f,C_n) \not = h(g,C_n)$, then $h(f,C_{n+6})\not = h(g, C_{n+6})$. Finally, we must show that for $n=7,9$, or $11$, $h(f,C_n) \not = h(g,C_n)$. The case $n=9$ was done in Example \ref{cycleex}. Similar to the calculation for $h(f,C_9)$ in Example \ref{cycleex}, we find the generating function for the number of walks on the $f$-labeling of $C_7$ to be \begin{equation} G_{C_7}(x)=\frac{1-x^2}{1-3x^2-2x^7} \end{equation} \noindent and the generating function for the number of walks on the $f$-labeling of $C_{11}$ to be \begin{equation} G_{C_{11}}(x)=\frac{1-x^2}{1-3x^2-2x^{11}}. \end{equation} \noindent We find the growth rates of the coefficients of $G_{C_7}$ and $G_{C_{11}}$ are approximately $1.765$ and $1.736$, respectively. Thus, $h(f,C_7) \approx \log 1.765$ and $h(f,C_{11}) \approx \log 1.736$. For both $C_7$ and $C_{11}$, we show that the entropy of the labeling $g$ is greater than the entropy of the labeling $f$. To accomplish this, we will find a lower bound for the entropy of $g$ that exceeds the entropy of the labeling $f$. Both $g(C_7)$ and $g(C_{11})$ contain the subgraph $P_6$ labeled $rbwrbw$. Let $G_k$ be the number of walks on $k$ labeled vertices beginning and ending at (and possibly visiting in between) the first vertex $r$. Then $G_k \subset g(W_k(C_7))$ and $G_k \subset g(W_k(C_{11}))$. A Dyck path is a lattice path in $\mathbb{Z}^2$ from the point $(0,0)$ to the point $(2n,0)$ consisting of two types of steps: up-steps (1,1) and down-steps (1,-1). A Dyck path also has the restriction that it never passes below the $x$-axis. All walks in $G_k$ are Dyck paths with the restriction that the path never go above the line $y=5$ (and below $y=0$). From \cite{Ilic} or \cite{Georg}, the generating function for the number of restricted Dyck paths from $(0,0)$, to $(2n,0)$ that do not touch the line $y=m$ are given by \begin{center} $R_{m}(x)=\frac{U_m^*(x)}{U_{m+1}^*(x)}$, \end{center} \noindent where $U_{m}^*(x)=x^mU_m(\frac{1}{2x})$ and $U_m$ is the Chebyshev polynomial of the second kind. So, the generating function for $G_k$ is \begin{center} $R_6(x)=\frac{U_6^*(x)}{U_7^*(x))}=\frac{U_6(\frac{1}{2x})}{xU_7(\frac{1}{2x})}$. \end{center} \noindent The growth factor of $G_k$ will be twice the largest root of $U_7$. The roots of this Chebysev polynomial are $x_j=\cos(\frac{j\pi}{8})$ for $j \in [1,7]$ \cite{Kythe}. Since $2\cos(\pi/8) \approx 1.848$, $h(g,C_7) > h(f,C_7)$ and $h(g, C_{11})>h(f,C_{11})$. We thank \cite{stack} for suggesting \cite{Ilic} and the use of Dyck paths to bound the growth rates of the walks on $g$. \end{proof} Interestingly, the condition that $n >5$ in Theorem \ref{oddcyclediff} is necessary. \begin{prop} If $f$ and $g$ are chromatic labelings of $C_5$, then $h(f,C_5)=h(g,C_5)$. \end{prop} \begin{proof} Let the vertices of $C_5$ be $1,2,3,4,$ and $5$ where $i$ is adjacent to $(i+1) \mod 5$ for all $i \in V(C_5)$. For any chromatic labeling of $C_5$, there must be three consecutive vertices with three distinct colors. Without loss of generality, let $f(1)=g(1)=r$, $f(2)=g(2)=b$ and $f(3)=g(3)=w$. Now, there are only three possible ways to color 4 and 5. They are $bw$, $rb$ and $rw$. Suppose $f(4)=b$ and $f(5)=w$. Suppose $g(4)=r$ and $g(5)=b$. Then, for any $k \in \mathbb{N}$, there exists a bijection $\psi: f(W_k(C_5)) \to g(W_k(C_5))$ that maps every occurrence of $w$ to $r$. Now suppose $f$ as before, and let $g(4)=r$ and $g(5)=w$. Then for any $k \in \mathbb{N}$, there exists a bijection $\phi: f(W_k(C_5)) \to g(W_k(C_5))$ that maps every occurrence of $b$ to $r$. In either case, we get that for all $k \in \mathbb{N}$, $|f(W_k(C_5))|=|g(W_k(C_5))|$. Therefore, for any two chromatic labelings $f$ and $g$ of $C_5$, we have $h(f,C_5)=h(g,C_5)$. \end{proof} We can then use the methods from Example $\ref{cycleex}$ to find that the entropy of any chromatic labeling of $C_5$ is approximately $\log 1.825$. \section{Entropy of Distinguishing Labelings} \label{entdist} If a graph has trivial automorphism group, then any labeling is distinguishing. In these cases, putting the restriction on a labeling that it is distinguishing gives us no new information about the entropy of that labeling. So, suppose the automorphism group of $G$, denoted $Aut(G)$, is not trivial. The distinguishing number of a graph $G$, denoted by $D(G)$, is the minimum $r$ such that $G$ has an $r$-distinguishing labeling \cite{AC}. In \cite{AC}, Albertson and Collins showed that if $Aut(G)$ is abelian, $D(G) \leq 2$ and if $Aut(G)$ is dihedral, $D(G) \leq 3$. This leads to the following proposition. \begin{prop} \label{distbasic} (i) Let $G$ be an undirected graph where $Aut(G)$ is abelian. Let $f$ be a distinguishing labeling of $G$ with $D(G)$ labels. Then $h(f,G) \leq \log 2$. If $f$ is also a proper coloring of $G$, $h(f,G)=0$.\\ (ii) Let $H$ be an undirected graph where $Aut(H)$ is dihedral. Let $g$ be a distinguishing labeling of $H$ with $D(H)$ labels. Then $h(g,H) \leq \log 3$. If $g$ is also a proper coloring of $H$, $h(g,H) \leq \log 2$. \end{prop} \begin{proof} If $Aut(G)$ is abelian, $D(G) \leq 2$ \cite{AC}. Then, $f(W_k(G)) \leq 2^k$. Therefore, $h(f,G) \leq \log 2$. If $f$ is also proper, by Lemma \ref{cliquechrom}, $h(f,G)=0$. If $Aut(H)$ is dihedral, $D(H) \leq 3$ \cite{AC}. Then, $g(W_k(H)) \leq 3^k$. Therefore, $h(g,H) \leq \log 3$. If $g$ is also proper, by Lemma \ref{cliquechrom}, $h(g,H) \leq \log 2$. \end{proof} Similar propositions can be deduced from other results in \cite{AC} and subsequent papers on distinguishing labelings. As we did in Section \ref{entchrom}, we now look specifically at cycles. Let a $D^*$-labeling of $G$ be a distinguishing labeling of $G$ with $D(G)$ labels. Note that for any even cycle, the entropy of a chromatic labeling is 0. \begin{thm} For any $D^*$-labeling $f$ of $C_3$, $h(f,C_3)= \log 2$. For any $D^*$-labeling $f$ of $C_4$, $h(f,C_4)=\log 2$. For $n \geq 5$ (even or odd), there exists a $D^*$-labeling $f$ of $C_{n}$ such that $h(f,C_{n}) \geq \log \Phi$ (where $\Phi$ is the golden ratio). \end{thm} \begin{proof} From \cite{AC}, $D(C_3)=3$, and $D(C_4)=3$. Therefore, $h(f,C_3)=h(C_3)$. Let $1,2,3,4$ be the vertices of $C_4$ where $i$ is adjacent to $(i+1) \mod 4$ for $i \in [1,4]$. Any $D^*$-labeling $f$ of $C_4$ is of the form $rrbw$ on $1234$. In other words, there must exist two adjacent vertices labeled same color. All walks in $f(W_k(C_4))$ that hit $b$ or $w$ have one representation. For each $k \in \mathbb{N}$ there is only one walk, $r^k$, that does not hit $b$ or $w$. This walk has two representations (one starting at each $r$). So, $|f(W_k(C_4))|=|W_k(C_4)|-1$. Therefore, $h(f,C_4)=h(C_4)$. The graphs $C_3$ and $C_4$ are $2$-regular. By Lemma \ref{reg}, $h(C_3)=h(C_4)=\log 2$. From \cite{AC}, $D(C_5)=3$. The chromatic labeling $rbwbw$ of $C_5$ is also distinguishing. We saw in Section \ref{entchrom}, that the entropy of this labeling is approximately $\log 1.825$ and certainly larger than $\log \Phi$. Let $C_n$ be a cycle of order $n \geq 6$. Let $1,2,\ldots,n$ be the vertices of $C_n$ where $i$ is adjacent to $(i+1) \mod n$. From \cite{AC}, $D(C_n)=2$ and the labeling that assigns $1$, $2$ and $4$ the color $r$ and all other vertices the color $b$ is distinguishing. Now consider the subgraph and path, $H$, with labels $f(n-1)f(n)f(1)f(2)=bbrr$. Any walk that is a concatenation of odd strings of $b$'s and odd strings of $r$'s can be realized on $H$. Any walk on the labeling of $H$ that contains both an $r$ and a $b$ has a unique presentation. The string of all $r$'s and the string of all $b'$ each have 2 representations. Therefore, the entropy of $H$ is equal to the entropy of the the path $P_4$ on four vertices. Using Perron-Frobenius theory, one can calculate $h(P_4)=\log (\frac{1+\sqrt{5}}{2})$. Therefore, $h(f,C_n) \geq \log (\frac{1+\sqrt{5}}{2})$. \end{proof} \section{Entropy of Distinguishing Chromatic Labelings} In \cite{CT}, Collins and Trenk defined a distinguishing chromatic labeling to be a labeling that is both distinguishing and a proper coloring. The distinguishing chromatic number of a graph $G$, $\chi_D(G)$, is the minimum number of labels needed for a distinguishing chromatic labeling of $G$. Since we are working with proper colorings, we will assume our graphs have no self-loops. Also, we will take all graphs in this section to be undirected. Lemma \ref{cliquechrom} implies following result, which is analogous to Theorem \ref{perchrom}. \begin{thm} \label{distperchrom} Let $G$ be a graph where $\chi_D(G)=\omega(G)$. Then for any distinguishing chromatic labeling $f$ of $G$ with $\chi_D(G)$ colors, $h(f,G)=\log(\omega(G)-1)=\log(\chi_D(G)-1)$. \end{thm} If a graph $G$ has no nontrivial automorphisms, then $\chi_D(G)=\chi(G)$. For any perfect graph $G$, $\chi(G)=\omega(G)$. So, a perfect graph $G$ that has no nontrivial automorphisms would meet the conditions of Theorem \ref{distperchrom}. To our knowledge, the class of graphs $G$ where $\omega(G)=\chi_D(G)$ has not been completely classified. With Theorem 4.5 in \cite{CT}, the authors prove that for all connected graphs $G$, $\chi_D(G) \leq 2 \Delta(G)$. Furthermore, we have equality if and only if $G=K_{\Delta,\Delta}$ or $C_6$. This result and Lemma \ref{cliquechrom} yield the following proposition. \begin{prop} Let $G$ be a connected graph. Let $f$ be a distinguishing chromatic labeling of $G$ with $\chi_D(G)$ colors. Then $\log (\omega(G)-1) \leq h(f,G) \leq \log(2 \Delta(G) -1)$. Futhermore, if $G \not = K_{\Delta,\Delta}$ or $C_6$, $\log (\omega(G)-1) \leq h(f,G) < \log(2 \Delta(G) -2)$. \end{prop} \section{Demarcating Labelings} \label{secrdem} Let $f$ be a labeling of a graph $G$. If there exists $v \in V(G)$ and $w_1w_2...w_k \in f(W_k(G))$ where we can (from the walk $w_1w_2\ldots w_k$) determine an $i \in [1,k]$ such that $f^{-1}(w_i)=v$, then we say $f$ is demarcating. The following lemma appeared in \cite{LS}. \begin{lem}\label{rdemM} Let $G$ be an irreducible aperiodic directed graph. Let $\mu$ be a shift invariant Markov measure on $G$ and denote with $X$ the Markov process defined by $G$ and $\mu$. Let $f$ be a labeling of $G$. Let $Y$ be the factor of $X$ defined by $f$. If $f$ is demarcating, then $Y$ is variable length Markov. \end{lem} Recall that it is still an open question whether (Kolmogorov-Sinai) entropy is a complete finitary isomorphism invariant for continuous factors of Markov processes. By the work of Keane and Smorodinsky in \cite{KS1}, it would suffice to show that every continuous factor of a Markov process is finitarily isomorphic to a Bernoulli scheme. The following theorem is progress in this direction. \begin{thm} \label{finisom} Let $G$ be an irreducible aperiodic directed graph. Let $\mu$ be a shift invariant Markov measure on $G$ and denote with $Z$ the Markov process defined by $G$ and $\mu$. Let $f$ be a demarcating labeling of $G$. Let $Z'$ be the factor of $Z$ defined by $f$. Then $Z'$ is finitarily isomorphic to a Bernoulli scheme. \end{thm} \begin{proof} Rudolph showed that every countable state Markov process with exponentially decaying return times is finitarily isomorphic to a Bernoulli scheme \cite{R}. So, it suffices to show that $Z'$ is finitarily isomorphic to a countable state Markov process with exponentially decaying return times. By Lemma \ref{rdemM}, $Z'$ is variable length Markov. Then there exists a positive integer $k$ such that $Z'^{(k)}$ is a renewal process. To simplify notation, let us denote $Z'^{(k)}$ by $X$. Let $a$ be a renewal state in $X$. Next, we will construct a finitary isomorphism from $X=(X,\mathcal{U},\mu,T)$ to a countable state Markov process $Y=(Y,\mathcal{V},\nu,S)$. This portion of our proof is essentially the same as the proof of Theorem 3.2 in \cite{Shea}. Let $\phi:X\to Y$ so that for $x \in X$, $(\phi(x))_i=a$ if $x_i=a$. If $x_i \not = a$, define $(\phi(x))_i=(a,\alpha_1,\alpha_2,...\alpha_j)$ where for $1\leq l \leq j$, $x_{i-j+l}=\alpha_l$, $\alpha_l \not = a$ and $x_{i-j}=a$. With full probability, $x_{i-j}=a$ for some positive integer $j$. Therefore, $\phi$ is well defined on a subset of $X$ that has measure one. For some positive integer $n$, $(\phi(x))_0$ is a record of $x[n-1,0]$ when $x_{n-1}$ is the last occurrence of the state $a$ in $x$. Since $X$ is a finite state process, $Y$ is a countable state process. Let $b$ be a state in the alphabet of $Y$. To show that $Y$ is Markov, we need to show that the $\sigma$-algebras $\mathcal{V}(Y_{n+1},Y_{n+2},...)$ and $\mathcal{V}(...,Y_{n-2},Y_{n-1})$ are independent given the event $[Y_n=b]$. Recall that if $\phi(x)=y$, $y_n$ is simply the history of the chain $x$ before time $n$ back to the last occurrence of the renewal state $a$. By how $\phi$ is defined, $\phi^{-1}\mathcal{V}(...,Y_{n-2},Y_{n-1})$ is a sub-algebra of $\mathcal{U}(...,X_{n-2},X_{n-1})$. Since $a$ is a renewal state in $X$, when $X_{n+1-j}=a$ and $X_{n+1-i}\not = a$ for $0 \leq i < j$, $\phi^{-1}\mathcal{V}(Y_{n+1},Y_{n+2},...)$ is a sub-algebra of $\mathcal{U}(X_{n+1-j},X_{n+2-j},...)$ . If $x_{n+1-j}=a$ and $x_{n+1-i}\not = a$ for $0 \leq i < j$, then $b=y_n=(\phi(x))_n=(x_{n+1-j},x_{n+2-j},...,x_n)$. Given $Y_n=b$, $\phi^{-1}\mathcal{V}(Y_{n+1},Y_{n+2},...)$ is a sub-algebra of $\mathcal{U}(X_{n+1},X_{n+2},...)$. Given $Y_n=b$, $\phi^{-1}\mathcal{V}(...,Y_{n-2},Y_{n-1})$ is a sub-algebra of $\mathcal{U}(...,X_{n-j-1},X_{n-j})$. Since $a$ is a renewal state in $X$, given the event $[Y_n=b]$, $\mathcal{U}(...,X_{n-j-1},X_{n-j})$ and $\mathcal{U}(X_{n+1},X_{n+2},...)$ are independent. Therefore, the $\sigma$-algebras $\mathcal{V}(Y_{n+1},Y_{n+2},...)$ and $\mathcal{V}(...,Y_{n-2},Y_{n-1})$ are independent given the event $[Y_n=b]$, and $Y$ is Markov. Now we need to show that $\phi$ is invertible. Suppose $b=(a_1,a_2,...,a_m)$, $a_1=a$, and $a_i \in A$ for $1 \leq i \leq m$. If $y_n=b$, then $(\phi^{-1}(y))_n=a_m$. The inverse is a 1-block code. Since $(\phi(x))_n$ is simply the history of the chain $x$ before time $n$ back to the last occurrence of the renewal state $a$, and $\phi^{-1}$ is a 1-block code, $\phi$ is a finitary isomorphism. We now show that $Y$ has exponentially decaying return times. $Z$ is a finite-state aperiodic Markov process. By the work of Keane and Smorodinsky in \cite{KS2}, $Z$ is finitarily isomorphic to a Bernoulli scheme. To be finitarily isomorphic to a Bernoulli scheme, a Markov process must have exponentially decaying return times (see \cite{Ser}, for example). Therefore, $Z$ has exponentially decaying return times. Since $Z'$ is a continuous factor of $Z$, $Z'$ has exponentially decaying return times. Since $a$ is a state in $Z'^{(k)}$, $a$ is a word of length $k$ in $Z'$. Since $Z'$ has exponentially decaying return times, the probability of first return to $a$ in $Z'$ must decay exponentially. Therefore, the probability of first return to $a$ in $Z'^{(k)}$ must decay exponentially. Since $a$ has the same distribution in $Y$ as $a$ has in $Z'^{(k)}$, the probability of first return to $a$ in $Y$ must decay exponentially. Therefore, $Y$ has exponentially decaying return times. Since $k$-stringing is a finitary isomorphism (even a continuous isomorphism) and finitary isomorphism is transitive, $Z'$ is finitarily isomorphic to $Y$, a countable state Markov chain with exponentially decaying return times. Rudolph's result \cite{R} implies $Y$ is finitarily isomorphic to a Bernoulli scheme. Again, since finitary isomorphism is transitive, $Z'$ is finitarily isomorphic to a Bernoulli scheme. \end{proof} This leads immediately to the following corollary that Kolmogorov-Sinai entropy is a complete finitary isomorphism invariant for continuous factors of Markov processes defined by demarcating labelings. \begin{cor} Let $G$ and $H$ be irreducible aperiodic directed graphs. Let $\mu$ and $\nu$ be shift invariant Markov measures on $G$ and $H$, respectively. Denote with $X$ (resp. $Y$) the Markov process defined by $G$ and $\mu$ (resp. $H$ and $\nu$). Let $f$ and $g$ be demarcating labelings of $G$ and $H$, respectively. Let $X'$ (resp. $Y'$) be the factor of $X$ defined by $f$ (resp. $Y$ defined by $g$). Then $X'$ and $Y'$ are finitarily isomorphic if and only if $h(X')=h(Y')$. \end{cor} \begin{proof} Entropy is a finitary isomorphism invariant. Therefore, if $X'$ is finitarily isomorphic to $Y'$, then $h(X')=h(Y')$. Now suppose $h(X')=h(Y')$. By Theorem \ref{finisom}, $X'$ and $Y'$ are finitarily isomorphic to Bernoulli schemes $B_1$ and $B_2$, respectively. Since entropy is a finitary isomorphism invariant, $h(X)=h(B_1)=h(B_2)=h(Y)$. By \cite{KS1}, $B_1$ and $B_2$ are finitarily isomorphic. Since finitary isomorphism is transitive, $X$ and $Y$ are finitarily isomorphic. \end{proof} The previous results demonstrates a relationship between a graph theoretic notion of a labeling and a classification result in ergodic theory. We know that topological entropy is related to measure-theoretic entropy through the variational principle (see \cite{D}). One of the advantages of our definition for topological graph entropy is that in special situations, all entropies align. \begin{cor} \label{align} Let $G$ be an irreducible aperiodic directed graph. Let $\mu$ be the unique maximal shift invariant Markov measure on $G$ (the so-called Parry measure) and denote with $X$ the Markov process defined by $G$ and $\mu$. Let $f$ be a demarcating labeling of $G$. Let $Y$ be the process defined by the continuous factor map $f:X \to Y$. If $h(X)=h(Y)$, then $h_{top}(G)=h_{top}(f,G)=h(X)=h(Y)$, and $Y$ is finitarily isomorphic to $X$. \end{cor} \begin{proof} By Theorem \ref{finisom}, $Y$ is finitarily isomorphic to a Bernoulli scheme $B_1$. Finite state irreducible aperiodic Markov processes are finitarily isomorphic to Bernoulli schemes \cite{KS2}. So, $X$ is finitarily isomorphic to a Bernoulli scheme $B_2$. Since entropy is a finitary isomorphism invariant, $h(X)=h(B_2)=h(B_1)=h(Y)$. By \cite{KS1}, $B_1$ is finitarily isomorphic to $B_2$. Since finitary isomorphism is transitive, $X$ is finitarily isomorphic to $Y$. Let $Z$ be the topological Markov shift defined by $G$. If $G$ is assigned the unique Markov measure of maximal entropy, then by the variational principle, the topological entropy of $Z$ equals the Kolmogorov-Sinai entropy of $X$ ($h(Z)=h(X)$). Since $h_{top}(G)=h(Z)$, $h_{top}(G)=h(X)$. Let $Z'=f(Z)$. The topological entropy of the labeling $f$, $h_{top}(f,G)$, equals the topological entropy of the shift space $Z'$ ($h_{top}(f,G)=h(Z')$). A factor map cannot increase topological entropy. Since $\mu$ is a measure of maximal entropy on $G$ and $h(X)=h(Y)$, $f(\mu)$ is a measure of maximal entropy on $Z'$. By the variational principle, $h(Z')=h(Y)$. Therefore, $h_{top}(G)=h_{top}(f,G)=h(X)=h(Y)$. \end{proof} For a label $a$ in a labeling $f$ of $G$, let $f^{-1}(a)=\{v \in V(G)|f(v)=a\}$ and let $|f^{-1}(a)|$ be the cardinality of $f^{-1}(a)$. We have the following simple lemma. \begin{lem} \label{uniquepreimage} Let $G$ be a directed or undirected graph. Let $f$ be a labeling of $G$. If for some label $a$, $|f^{-1}(a)|=1$, then $f$ is demarcating. \end{lem} Lemma \ref{uniquepreimage} shows that finding a minimum $r$ for a graph $G$ such that $G$ has a demarcating labeling with $r$ labels is trivial. If the graph has greater than $2$ vertices, the minimum $r$ is always $2$ since we can assign one vertex one label and every other vertex the other label. Lemma \ref{uniquepreimage} gives a way to compute a lower bound when counting the number of demarcating labelings of a given graph. Using Lemma \ref{uniquepreimage}, we can find a lower bound by counting the number of labelings where one label has a unique pre-image. If our graph represents a process (such as a $k$-stringing of a Bernoulli scheme), the labelings define continuous factors. Since demarcating labelings define variable length Markov factors (by Lemma \ref{rdemM}), Lemma \ref{uniquepreimage} gives a way to find a lower bound on the number of variable length Markov continuous factors of a given Bernoulli scheme or Markov process. Lemma \ref{uniquepreimage} also tells us that if $G$ has a nontrivial automorphism that fixes a vertex, there exists a demarcating labeling of $G$ that is not distinguishing. Suppose $u$ is the fixed vertex. Let $f$ be a 2-labeling of $G$ such that $f(u)=a$ and $f(v)=b$ for all other $v \in V(G)$. We use cyclic notation to denote a permutation of the vertices. For $k \geq 2$, $v_1, v_2, ...,v_k$ some set of vertices in $V(G)$, $(v_1v_2...v_k)$ denotes the cycle that maps $v_1 \to v_2$, $v_2 \to v_3$,...,$v_{k-1} \to v_k$, and $v_k \to v_1$. We denote the identity on a vertex by $(v_1)$. Any permutation can be written as a product of disjoint cycles $p=(c_1)(c_2)...(c_n)$ where for $i \in [1,n]$, $(c_i)$ denotes a cycle. \begin{lem} \label{notdemnotdist} Let $G$ be a graph. Let $p=(c_1)(c_2)...(c_n)$ be an automorphism of $G$ such that for all $v \in V(G)$, $p(v) \not = v$. Let $f$ be a labeling of $G$ where for any $j \in [1,n]$, if $u,v \in c_j$, $f(u)=f(v)$. Then $f$ is not distinguishing and $f$ is not demarcating. \end{lem} \begin{proof} Since $f$ is a labeling of $G$ where for any $j \in [1,n]$, if $u,v \in c_j$, $f(u)=f(v)$, $f$ preserves the automorphism $p$. Therefore, $f$ is not distinguishing. An automorphism of $G$ preserves edge-connectivity. So, if $(u,v) \in E(G)$, $(p(u),p(v))$ is an element of $E(G)$. Let $w=w_1w_2...w_k$ be a walk on $G$. Let $f(w)=f(w_1)f(w_2)...f(w_k)$ be a walk on the labeling of $G$. Since $p$ preserves edge-connectivity, the image $p(w)=p(w_1)p(w_2)...p(w_k)$ is a walk on $G$. Since $f$ is a labeling of $G$ where for any $j \in [1,n]$, if $u,v \in c_j$, $f(u)=f(v)$, $f(p(w))=f(w)$. For all $v \in V(G)$, we supposed $p(v) \not = v$. Then, for any walk $\omega=\omega_1\omega_2...\omega_k$ on the labeling $f$ of $G$, there are two walks $w$ and $p(w)$ on $G$ such that $f(w)=f(p(w))$, and $w_i \not = p(w)_i$ for any $i \in [1,k]$. Therefore, $f$ is not demarcating. \end{proof} \begin{thm} \label{demimpliesdist} Let $G$ be a graph. Suppose $|Aut(G)|>1$, and if $p$ is a non-trivial automorphism of $G$, then $p(v) \not = v$ for all $v \in V(G)$. A labeling $f$ of $G$ is not distinguishing if and only if there exists an automorphism $q=(c_1)(c_2)...(c_n)$ of $G$ where for any $j \in [1,n]$, if $u,v \in c_j$, $f(u)=f(v)$. Furthermore, if $f$ is demarcating, then $f$ is distinguishing. \end{thm} \begin{proof} By Lemma \ref{notdemnotdist}, it suffices to show that if $f$ is not distinguishing then there exists an automorphism $q=(c_1)(c_2)...(c_n)$ of $G$ where for any $j \in [1,n]$, if $u,v \in c_j$, $f(u)=f(v)$. If $f$ is not distinguishing, then there exists a non-trivial automorphism $q$ of $G$ that $f$ preserves. Then for a cycle $c_j \in q$ where $(c_j)=(v_1v_2..v_k)$, we have $f(v_1)=f(v_2)$, $f(v_2)=f(v_3),\ldots,f(v_{k-1})=f(v_k)$, and $f(v_k)=f(v_1)$. Therefore, for all $u,v \in c_j$, $f(u)=f(v)$. \end{proof} Let $G$ be a $k$-block presentation of the full shift on two symbols. By Theorem \ref{autkblock} there is one non-trivial automorphism $p$ of $G$, and $p(v) \not = v$ for all $v \in V(G)$. So, $G$ meets the conditions of Theorem \ref{demimpliesdist}. Therefore, any demarcating labeling of $G$ is a distinguishing labeling of $G$. We now present an example that shows a distinguishing labeling is not always demarcating. \begin{ex} \label{Quas} We thank Mahsa Allahbakhshi and Anthony Quas for the following example. Let $X$ be the full shift on two symbols $0$ and $1$. Let $G$ be the associated directed graph (see Figure 3.1). Let $G_5$ be the 5-block presentation of $G$. Then the vertices of $G_5$ are blocks of 0's and 1's of length 5 (e.g. 11010). Consider the labeling $f$ of $G_5$ where $f(v)=r$ if $v=00111$ or $v=01011$, and $f(v)=b$ otherwise. By Corollary \ref{distkblocklabel}, $f$ is distinguishing. (A non-distinguishing labeling would have to map 00111 and 11000 to the same label, for example). We now show that the labeling $f$ is not demarcating. In every walk on the $f$-labeling of $G_5$, $rr$, $rbr$, $rbbr$, and $rbbbr$ are forbidden. So any walk on the labeling of $G_5$ looks like $w=b^{m_1}rb^{m_2}rb^{m_3}...rb^{m_n}$ where each $m_i \geq 4$. Let's consider the pre-image set of $w$ with respect to $f$. The vertices in $G_5$ are blocks of length 5 where for $u=(u_1u_2u_3u_4u_5)$ and $v=(v_1v_2v_3v_4v_5)$ in $V(G_5)$, $(u,v) \in E(G_5)$ if $v_j=u_{j+1}$ for $1 \leq j \leq 4$. We will drop the redundancy and write $uv$ as $u_1u_2u_3u_4u_5v_5$. We have \begin{center} $1^{m_1+4}(00111)1^{m_2-4}(00111)1^{m_3-4}\ldots(00111)1^{m_n-4}$\\ and\\ $0^{m_1+4}(01011)0^{m_2-4}(01011)0^{m_3-4}\ldots(01011)0^{m_n-4}$ \end{center} \noindent in $f^{-1}(w)$. Therefore, $f$ is not demarcating. Note that one can show that this $Y$ is variable length Markov, and thus, not a counterexample to Conjecture \ref{conj}. \end{ex} \section{Labelings that Maximize Topological Graph Entropy} \label{secentmax} Corollary \ref{align} presents a situation where the entropy of $G$ does not decrease under the labeling $f$ of $G$. In other words, this is a situation where for the labeling $f$ of $G$, $h_{top}(f,G) = h_{top}(G)$. Here, we focus specifically on the labelings that maximize entropy. \begin{defn} Let $G$ be a graph (directed or undirected). Let $f$ be a labeling of $G$. We say that $f$ is an entropy maximizing labeling if $h_{top}(f,G)=h_{top}(G)$. The entropy maximizing number of $G$, denoted $M(G)$, is the minimum number of labels needed for an entropy maximizing labeling of $G$. \end{defn} If $f$ is injective, $h(G)=h(f,G)$. So, $M(G) \leq |V(G)|$ for all graphs $G$. We have the following simple result. \begin{prop} Let $G$ be an undirected graph (with no self-loops). If $h(G)= \log (\omega(G)-1)$, then $M(G) \leq \omega(G)$. Let $H$ be a directed graph (allowing self-loops). Suppose for some $U \subset V(H)$, if $u,v \in U$, $(u,v)$ and $(v,u)$ are in $E(H)$. If $h(H)=\log |U|$, then $M(H) \leq |U|$. \end{prop} \begin{proof} Let $f$ be a labeling of $G$ that labels each vertex in some clique of size $\omega(G)$ in $G$ uniquely. Let $F_k$ be the walks on the labelings of this clique in $G$. Then $F_k \subset f(W_k(G))$. We have $|F_k|=\omega(G)(\omega(G)-1)^{k-1}$. Therefore, $|f(W_k(G))| \geq \omega(G)(\omega(G)-1)^{k-1}$. So, $h(f,G) \geq \log (\omega(G)-1)$. Since $h(f,G) \leq h(G)$ for any labeling $f$, $h(f,G) = \log(\omega(G)-1)$. Let $g$ be a labeling of $H$ so that each vertex in $U$ is labeled uniquely. Let $G_k$ be the walks on the labelings of $U$ in $H$. Then, $G_k \subset g(W_k(H))$. We have $|G_k|=|U|^{k}$. Therefore, $|g(W_k(H))| \geq |U|^{k}$. So, $h(g,H) \geq \log |U|$. Since $h(g,H) \leq h(H)$ for any labeling $g$, $h(g,H)= \log |U|$. \end{proof} \begin{prop} \label{cyclemax} For any undirected cycle $C_n$, $M(C_n) \leq 3$. \end{prop} \begin{proof} By Lemma \ref{reg}, $h(C_n)=\log 2$. We consider three cases. \noindent Case 1: Suppose $n = 3 \mod 3$. Let $f$ be the $rbwrbw...rbw$ labeling of the vertices of $C_n$. Then every vertex is adjacent to two vertices with distinct colors. For each $k \in \mathbb{N}$, $f(W_k(C_n))=W_k(C_3)$. Then $h(f, C_n)=h(H)$. By Lemma \ref{reg}, $h(C_3)=\log 2$. \noindent Case 2: Suppose $n=1 \mod 3$. Let $f$ be the $rbwrbw...rbwr=(rbw)^{\frac{n-1}{3}}r$ labeling of the vertices of $C_n$. Then every vertex is adjacent to two distinctly labeled vertices. Therefore, $h(f,C_n)=\log 2$. \noindent Case 3: Suppose $n=2 \mod 3$. Let $rwwbr$ be the labeling of $C_5$. Let $rwwbrwwb$ be the labeling of $C_8$. Let $rwwbrwwb(rwb)^m$ be the labeling of $C_{8+3m}$. In all cases, every vertex is next to two distinctly labeled vertices. Therefore, $h(f, C_n)=\log 2$. \end{proof} The upper bound is sharp. Since there does not exist a 2-coloring of $C_3$ with entropy $\log 2$, $M(C_3)=3$. It is not the case that $M(C_n)=3$ for all cycles $C_n$. The $rrbb$ labeling of $C_4$ has entropy $\log 2$. \section*{Acknowledgements} I am grateful to Mike Keane for our many conversations on finitary isomorphisms and to Karen Collins for helpful lessons on distinguishing and distinguishing chromatic labelings. I also thank Andrew Lazowksi for continued conversation regarding our work in \cite{LS}. \begin{thebibliography}{33} \bibitem{Adler} R. Adler, A. Konheim and M. McAndrew. Topological entropy. {\em Trans. Amer. Math. Soc.}, 114: 309-319, 1965. \bibitem{AC} M. O. Albertson and K. L. Collins. Symmetry breaking in graphs. {\em Electron. J. of Combin.}, 3: \#R18, 1996. \bibitem{B} R. Bowen. Entropy for group endomorphisms and homogeneous spaces. {\em Tran. Amer. Math. Soc.}, 153: 401-414, 1971. \bibitem{Bruijn} N. de Bruijn. A combinatorial problem. {\em Nederl. Akad. Wetensch., Proc.}, 49: 758-764, 1946 $=$ {\em Indagationes Math.}, 8: 461-467, 1946. \bibitem{CL} G. Chartand and L. Lesniak. {\em Graphs and digraphs, fourth edition}. Chapman and Hall/CRC, Boca Raton, FL, 2005. \bibitem{CT} K. Collins and A. Trenk. The distinguishing chromatic number. {\em Electon. J. Combin.}, 13(1): \#R16, 2006. \bibitem{D} E. I. Dinaburg. The correlation between topological entropy and metric entropy. {\em Dokl. Akad. Nauk SSSR}, 190: 19-22, 1970. \bibitem{FS} P. Flajolet and R. Sedgewick. {\em Analytic combinatorics}. Cambridge University Press, Cambridge, 2009. \bibitem{Georg} E. Georgiadis, D Callan, and Q. Hou. Circular digraph walks, k-balanced strings, lattice paths and Chebyshev polynomials. {\em Electron. J. Combin.}, 15: \#R108, 2008. \bibitem{Ham} R. Hamming. Error detecting and error correcting codes. {\em Bell System Tech. J.}, 29(2): 147-160, 1950. \bibitem{Hed} G. Hedlund. Endomorphisms and automorphisms of the shift dynamical systems. {\em Math. Systems Theory} 3: 320-375, 1969. \bibitem{stack} (http://math.stackexchange.com/users/6622/joriki): \newblock ``walks on proper coloring of odd cycles: comparing asymptotics," \newblock Mathematics, 2011, \newblock URL http://math.stackexchange.com/q/81689 (version: 2011-11-15). \bibitem{Ilic} Al. Ili\'{c} and An. Ili\'{c}. \newblock On the number of restricted Dyck paths. 2011, URL http://www.pmf.ni.ac.rs/filomat, 2011. \bibitem{Kat} A. Katok. Fifty years of entropy in dynamics: 1958-2007. {\em J. Mod. Dyn.}, 1(4): 545-596, 2007. \bibitem{KS1} M. Keane and M. Smorodinsky. Bernoulli schemes of the same entropy are finitarily isomorphic. {\em Ann. of Math.}, 109(2): 397-406, 1979. \bibitem{KS2} M. Keane and M. Smorodinsky. Finitary isomorphisms of irreducible Markov shifts. {\em Israel J. Math.}, 34(4): 281-286, 1979. \bibitem{Kolm} A. N. Kolmogorov. A new metric invariant of transitive dynamic systems and automorphism in Lebesgue spaces. {\em Dokl, Akad. Nauk. SSSR} 119: 861-864, 1958. \bibitem{Kythe} P. Kythe and M. Sch\"{a}ferkotter. {\em Handbook of computational methods for integration}. Chapman \& Hall/CRC, Boca Raton, FL, 2005. \bibitem{LS} A. Lazowski and S. Shea. Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs. {\em Electron. J. Combin.} 19(1): \#R1, 2012. \bibitem{LM} D. Lind and B. Marcus. {\em An introduction to symbolic dynamics and coding}. Cambridge Univ. Press, Cambridge, 1995. \bibitem{MW} G. Morvai and B. Weiss. On estimating the memory for finitarily Markovian processes. {\em Ann. I.H. Poincare-PR}, 43: 15-30, 2007. \bibitem{Myc} J. Mycielski. Sur le coloriage des graphs. {\em Colloq Math.}, 3: 161-162, 1955. \bibitem{O1} D. Ornstein. {\em Ergodic theory, randomness, and dynamical systems.} Yale University Press, 1974. \bibitem{O2} D. Ornstein. Factors of Bernouli shifts are Bernoulli shifts. {\em Advances in Math.}, 5: 349-364, 1970. \bibitem{Parry} W. Parry. Intrisic Markov chains. {\em Trans. Amer. Math. Soc.}, 112: 55-66, 1964. \bibitem{Ri} J. Rissanen. A universal data compression system. {\em IEEE Trans. Inform.}, 29: 656-664, 1983. \bibitem{R} D. Rudolph. A mixing Markov chain with exponentially decaying return times is finitarily Bernoulli. {\em Ergodic Theory, Dynam. Systems}, 2: 85-97, 1982. \bibitem{Ser} J. Serafin. Finitary codes, a short survey. {\em Dynamics and stochastics}, 262-273, IMS Lecture Notes Monogr. Ser., 48, Inst. Math. Statist., Beachwood, OH, 2006. \bibitem{Shan} C. Shannon. A mathematical theory of communication. {\em Bell Systems Technical Journal}, 27: 379-423, 623-656, 1948; Republished, University of Illinois Press Urbana, IL, 1963. \bibitem{SW} C. Shannon and W. Weaver. {\em The mathematical theory of communication}, Univ. of Illinois Press, Urbana, Ill, 1963. \bibitem{Shea} S. Shea. Notes on Finitary isomorphism markers in countable state Markov processes. {\em Markov Process. Related Fields}, 18(2): 323-332, 2012. \bibitem{Sm} M. Smorodinsky. Finitary isomorphism of m-dependent processes. {\em Symbolic dynamics and its applications} Contemp. Math. 135: 373-376, 1992. \bibitem{Walt} P. Walters. {\em An introduction to ergodic theory}. Graduate Texts in Mathematics 79. Springer-Verlag, New York-Berlin, 1982. \end{thebibliography} \end{document}