Generalisation of the Hammersley-Clifford Theorem on Bipartite Graphs
Nishant Chandgotia
The Hammersley-Clifford theorem states that if the support of a Markov random field has a safe symbol then it is a Gibbs state with some nearest neighbour interaction. In this paper we generalise the theorem with an added condition that the underlying graph is bipartite. Taking inspiration from \cite{brightwell2000gibbs we introduce a notion of folding for configuration spaces proving that if all Markov random fields supported on $X$ are Gibbs with some nearest neighbour interaction so are Markov random fields supported on the `folds' and `unfolds' of $X$.
gebihammersley.tex
% uncomment this part for dvi
%\documentclass{amsart}
%\usepackage[latin1]{inputenc}
%\usepackage{color}
%\usepackage{amssymb}
%\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% comment out for dvi
\documentclass[oneside, book,10 pt]{amsart}
\usepackage{color}
\usepackage{cancel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[normalem]{ulem}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage[mathscr]{eucal}
\bibliographystyle{plain}
\usepackage{graphicx}
\usepackage{pstricks}
\usepackage[active]{srcltx}
\usepackage{fancyhdr}
\usepackage{verbatim}
\usepackage{fullpage}
\usepackage{hyperref}
\hypersetup{
colorlinks = true, %Colours links instead of ugly boxes
urlcolor = blue, %Colour for external hyperlinks
linkcolor = red, %Colour of internal links
citecolor = blue %Colour of citations
}
%\usepackage{bbm}
\usepackage{caption}
\usepackage{float}
\newcommand{\reminder}[1]{\centerline{\fbox{\parbox{12.5cm}{#1}}}}
\pagestyle{fancy}
\fancyhf{}
\fancyfoot[C]{\footnotesize \thepage\ }
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
%%%%%%%%%%%%%%%%%%%%%%%

\newtheorem{thm}{Theorem}[section]
\newtheorem*{thm*}{Theorem}
\newtheorem{lemma}[thm]{Lemma}
\newtheorem{corollary}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}
\newtheorem*{prop*}{Proposition}

\newtheorem*{defn}{Definition}
\newtheorem*{theorem}{Theorem}
\newtheorem{remark}[thm]{Remark}
\numberwithin{equation}{section}

\title{Generalisation of the Hammersley-Clifford Theorem on Bipartite Graphs}
\author{
Nishant Chandgotia}

\address{
Department of Mathematics\\ University of British Columbia,Canada}
\email {nishant@math.ubc.ca}

\subjclass[2010]{Primary 60K35; Secondary 82B20, 37B10}
\keywords{Markov random fields, Gibbs states, nearest neighbour interaction, folding, dismantleable, Hammersley-Clifford, symbolic dynamics}
\def\F{{\mathcal F}}
\def\A{{\mathcal A}}
\def\N{\mathbb N}
\def \O{\mathcal O}
\newcommand{\Z}{\mathbb{Z}}
\def \B{\mathcal B}
\def \P{\mathbb P}
\def \Ex{\mathbb E}
\def \R{\mathbb R}
\def \G{\mathcal G}
\def \V{\mathcal V}
\def \E1{\mathcal E}
\def \M{\mathbf{M}}
\def \Gi{\mathbf{G}}
\def\p{\prime}
\def \H{\mathcal H}
\begin{document}
\maketitle
\begin{abstract} The Hammersley-Clifford theorem states that if the support of a Markov random field has a safe symbol then it is a Gibbs state with some nearest neighbour interaction. In this paper we generalise the theorem with an added condition that the underlying graph is bipartite. Taking inspiration from \cite{brightwell2000gibbs} we introduce a notion of folding for configuration spaces proving that if all Markov random fields supported on $X$ are Gibbs with some nearest neighbour interaction so are Markov random fields supported on the `folds' and `unfolds' of $X$.
\end{abstract}
\section{Introduction}
A Markov random field(MRF) can be viewed as a collection of jointly distributed random variables indexed by the vertices of an undirected graph(denoted by $\G$) satisfying the conditional independence condition: the conditional distributions of the random variables on two finite separated sets are independent given the value of the random variables on the complement of their union. We are interested in determining conditions on the topological support of MRFs such that they are Gibbs states with some nearest neighbour interaction, that is, the distribution of the random variables on a finite set given their value on the outer boundary can be expressed as a normalised product of `weights' associated with patterns on complete subgraphs. The well-known Hammersley-Clifford theorem gives one such condition, a positivity assumption on the MRF given by the presence of a safe symbol in the support, also referred to as the vacuum state. We shall focus on the case where these random variables are finite valued.

In this paper we view MRFs outside the boundary of safe symbols, folding in the notion of graph folding into our context.
Given a finite undirected graph $\H$ we say that a vertex $a$ can be folded into vertex $b$ if the neighbours of $b$ contain the neighbours of $a$. By removing $a$ from $\H$ we obtain a fold of the graph. A graph is called dismantlable if there is a sequence of folds which leads to a single vertex with or without a loop. These notions of folding and dismantlability were introduced by Nowakowski and Winkler in \cite{nowakowskiwinkler} as a characterisation of cop-win graphs.

The presence of folding in $\H$ endows the space of homomorphisms $Hom(\G,\H)$ with some useful properties. Indeed if $a$ can be folded into $b$ in $\H$ then any appearance of $a$ in any homomorphism can be changed to $b$ to obtain another homomorphism. However to say that the supports of MRFs are homomorphism spaces is a rather strong assumption. Therefore we abstract some of the properties satisfied by these spaces and introduce a notion of folding in closed configuration spaces $X\subset\A^{\V}$ where $\A$ is a finite set of symbols corresponding to the vertices of $\H$ and $\V$ is the set of vertices of $\G$ which is assumed bipartite. $X$ is said to have a safe symbol $\star\in\A$ if $\star$ can replace any other symbol in any configuration in that space. In such a case any symbol can be folded into $\star$.

In \cite{brightwell2000gibbs} Brightwell and Winkler established many properties which are preserved under folding and unfolding of graphs. To this we add a `Hammersley-Clifford' property which we describe next.

A specification is a consistent collection of probability distributions of patterns on finite sets given the pattern on their complement. Every MRF supported on a configuration space $X$ yields a specification on $X$ which is Markovian, that is, the distribution of patterns on the finite sets given the pattern on their complement depends solely on the pattern on their outer boundary. Similarly a Gibbs state with a nearest neighbour interaction on $X$ yields a specification on $X$ which is Gibbsian in nature. An MRF is a Gibbs state with some nearest neighbour interaction if and only if the corresponding Markov specification is a Gibbs specification with some nearest neighbour interaction. Given a configuration space $X$, in section 3 of \cite{chandgotiameyerovitch} following \cite{petersen_schmidt1997} we reparametrised specifications on $X$ to obtain Markov and Gibbs cocycles on $X$. The set of these cocycles have a natural vector space structure. Moreover the space of Gibbs cocycles with nearest neighbour interactions is contained in the space of Markov cocycles, the difference of the dimensions of which measures the extent to which $X$ satisfies the conclusion of the Hammersley-Clifford theorem. Thus the Hammersley-Clifford theorem can be restated in terms of cocycles- if $X$ has a safe symbol then the space of Markov and Gibbs cocycles with nearest neighbour interactions on $X$ are the same.(Theorem \ref{Theorem:Strong_Hammersley-Clifford})

We call a configuration space $X$ Hammersley-Clifford if the spaces of Markov and Gibbs cocycles with nearest neighbour interactions on $X$ are the same. Generalising Hammersley-Clifford theorem for bipartite graphs we prove in this paper that the folds and unfolds of Hammersley-Clifford spaces are Hammersley-Clifford.(Theorems \ref{thm:main theorem} and \ref{thm:G-invariant main theorem}) Further we show that if a configuration space can be folded into another then the quotient spaces of their Markov cocycles and Gibbs cocycles with nearest neighbour interactions are isomorphic.(Theorem \ref{thm:extension of a Gibbs cocycle} and Corollary \ref{corollary:folds_quotient_isomorphic}) The proof is constructive; the corresponding ``weights"(interactions) can be obtained directly using our proof.(Lemma \ref{lemma:construction_of_V^prime}) We also obtain versions of the theorem when the space of cocycles is invariant under a subgroup of automorphisms of the graph.

There has been some work regarding conditions under which the conclusion of the Hammersley-Clifford theorem holds and some examples where it does not: J. Moussouris provided examples of MRFs on a finite graph which are not Gibbs states for any nearest neighbour interaction \cite{mouss}. When the underlying graph is finite, there are algebraic conditions on the support \cite{sturmfel} where the conclusion of the Hammersley-Clifford theorem holds. In \cite{laur} Lauritzen proves that when the underlying graph is finite and decomposable then every MRF is a Gibbs state with some nearest neighbour interaction. This is in contrast with our work where the graphs are bipartite which can be decomposable if and only if they are a tree. If the underlying graph is $\mathbb{Z}$ and the MRF is shift-invariant then the conclusion of the Hammersley-Clifford theorem holds without any further assumptions \cite{Markovfieldchain}. Furthermore, in that setting any MRF is a stationary Markov chain. When $\A$ is a general measure space, theorems 10.25 and 10.35 in \cite{Georgii} provide certain mixing conditions which guarantee the conclusion as well.
Even when the underlying graph is $\mathbb{Z}$, this conclusion can fail for countable $\mathcal{A}$ (Theorem 11.33 in \cite{Georgii}), or if we drop the assumption of shift-invariance \cite{dob}.
 When the underlying graph is $\mathbb{Z}^d$ and $d>1$, the conclusion fails even in the shift-invariant and finite alphabet case (Chapter 5 in \cite{Chandgotia} and section 9 of \cite{chandgotiameyerovitch}). In \cite{chandgotiameyerovitch} was analysed the space of Markov and Gibbs cocycles on $Hom(\Z^d, C_n)$ where $d\geq 2$, $C_n$ was an $n$-cycle and $n\neq 4$. Here we show that $Hom(\G, C_4)$ is Hammersley-Clifford for any bipartite graph $\G$. 

Section \ref{section:Background and Notation} begins with well-known notions related to this work e.g. MRFs and Gibbs States, invariance under group actions and the Hammersley-Clifford theorem. In subsection \ref{subsection:Hammersley-Clifford} we take inspiration from symbolic dynamics to define n.n.constraint spaces. In subsection \ref{subsection:cocycles} we introduce Markov and Gibbs cocycles and their relationship to the Hammersley-Clifford theorem. Section \ref{section:Hamm-cliff space} builds up the necessary background for this work. In subsection \ref{subsection:Hamm-cliff spaces} we introduce Hammersley-Clifford spaces and in subsection \ref{subsection:Markov-similar} we introduce Markov-similarity and $V$-good pairs. In subsection \ref{subsection:Graphfolding} we introduce folding. Section \ref{section: main results} states and proves the main results of this paper. Since the proofs are technical we work out a concrete example of our results in subsection \ref{subsection:concrete}. Finally we conclude with some further questions in section \ref{section:conclude}.

A small note on the notation: The calligraphic symbols $\G$ and $\H$ represent graphs and the symbols in bold font $\M$, $\Gi$ represent the space of cocycles. Among the symbols in regular font $X$ represents a closed space of configurations, $G$ a subgroup of automorphisms of the graph $\G$, $x, y$ configurations, $A$, $F$ subset of the set of vertices of $\G$,  $u$, $v$, $w$ the vertices of $\G$ and $a, b$ elements of the alphabet $\A$. In almost all cases $a$ is folded into the symbol $b$.
\section{Background and Notation} \label{section:Background and Notation}
\subsection{MRFs}
\large
By a graph $\G=(\V, \E1)$ we mean a countable locally finite undirected graph without any self loops or multiple edges. The adjacency relation is denoted by $\sim$. Given any set $F\subset \V$ the \emph{boundary of the set $F$} is defined as the set of vertices outside the set $F$ which are adjacent to $F$, that is,
$$\partial F=\{u\in \V\setminus F\:|\:\text{ there exists }v\in F \text{ s.t. } u \sim v\}.$$
Sometimes this is also called the external vertex boundary of the set $F$.

Given a finite set $\A$, $\A^\V$ is a compact topological space under the product topology. For any finite set $F\subset \V$ and $a\in \A^F$ we denote by $[a]_F$ the cylinder set
$$[a]_F=\{x\in \A^\V\:|\:x|_F=a\}.$$
Similarly given $x\in \A^\V$ and $F\subset \V$, $[x]_F$ denotes the cylinder set $[x|_F]_F$. Also for any symbol $b\in \A$ and set $F\subset \V$
$$[b]_F=\{x\in \A^\V\:|\:x_v=b\text{ for all }v\in F \}.$$
The collection of cylinder sets generate the Borel $\sigma$-algebra on $\A^\V$. The set $\A$ will be referred to as an \emph{alphabet} with finitely many \emph{symbols} which when placed on vertices of the graph $\G$ yield \emph{configurations}, that is, elements of $\A^\V$ and \emph{patterns}, that is, elements of $\A^F$ for some set $F\subset \V$.

An \emph{MRF} is a Borel probability measure $\mu$ on $\A^\V$ with the property that for all finite sets $A, B\subset \V$ such that $\partial A\subset B\subset A^c$ and $a\in \A^A, b\in \A^B$ satisfying $\mu([b]_B)>0$
$$\mu([a]_A\:|\:[b]_B)= \mu([a]_A\:|\:[b]_{\partial A}).$$
An equivalent definition is the following: If $x$ is a point chosen randomly according to the measure $\mu$, and $A, B\subset\V$ are finite \emph{separated }sets in $\G$(meaning $u\nsim v$ for all $u\in A$ and $v\in B$), then conditioned on $x|_{\V\setminus (A\cup B)}$, $x|_{A}$ and $x|_B$ are independent random variables. Here we restrict our attention to boundaries of thickness $1$. In general thicker boundaries can also be considered for similar notions.

A stronger notion of an MRF obtained by requiring this conditional independence for all sets $A, B\subset \V$ which are separated in $\G$(finite or not) is called a \emph{global MRF}. This paper is concerned with the former notion of independence, where both $A$ and $B$ are assumed to be finite.

\subsection{Gibbs States with Nearest Neighbour Interactions}
Let $d_\G$ denote the graph distance on $\G$. Given any finite set $A\subset \V$ let $diam(A)$ denote the \emph{diameter of the set $A$} defined by
$$diam(A)= \max_{u, v\in A}d_{\G}(u,v).$$
Given a closed configuration space $X\subset \A^\V$ and $F\subset \V$, denote by $\B_F(X)$ \emph{the language of $X$ on $F$} defined as the set of allowed patterns on $F$, that is,
$$\B_F(X)=\{a\in \A^F\:|\: \text{ there exists }x\in X\text{ s.t. }x|_{F}=a\}.$$
Note that $\B_\V(X)=X$. Denote by $\B(X)$ \emph{the language of $X$} defined as the set of all allowed patterns on finite sets, that is,
$$\B(X)= \bigcup_{F\subset \V\text{ finite}}\B_F(X).$$
From the following lemma we see that the language completely describes the configuration space. 
\begin{prop}\label{Proposition:language gives all}
Let $\A$ be a finite set, $\G=(\V, \E1)$ be a graph and $X, Y\subset \A^{\V}$ be closed sets. Then $X\subset Y$ if and only if $\B_A(X)\subset \B_A(Y)$ for all $A\subset \V$ finite.
\end{prop}

By definition if $X\subset Y$ then $\B_A(X)\subset \B_A(Y)$ for all finite sets $A\subset \V$. The converse stands true because $X$ and $Y$ are closed.

A closed configuration space relevant to us is the \emph{support} of a probability measure $\mu$ denoted by $supp(\mu)$ and defined as the intersection of all closed sets $X\subset \A^\V$ with full measure.

An interaction on $X$ is a real-valued function on the language, $V: \B(X)\longrightarrow \R$ satisfying certain summability conditions. A \emph{nearest neighbour interaction} is an interaction $V$ on $X$ such that it is supported on patterns on cliques(complete subgraphs) of $\G$, that is, $V(a)=0$ for all patterns $a\in \B_F(X)$ where $diam(F)>1$. If the underlying graph $\G$ is bipartite then a nearest neighbour interaction is an interaction supported on patterns on edges and vertices. We will use patterns and their corresponding cylinder sets interchangeably, that is, we will often denote patterns $a\in \A^F$ by $[a]_A$ or $[x]_A$ where $x|_A=a$.

A\emph{ Gibbs state with a nearest neighbour interaction $V$} is an MRF $\mu$ such that for all $x\in supp(\mu)$ and $A, B\subset \V$ finite satisfying $\partial A\subset B\subset A^c$
$$\mu([x]_A\:|\:[x]_B)= \frac{\prod_{C\subset A\cup \partial A}e^{V([x]_C)}}{Z_{A, x|_{\partial A}}}$$
where $Z_{A, x|_{\partial A}}$ is the uniquely determined normalising factor dependent upon $A$ and $x|_{\partial A}$ so that $\mu(X)=1$.

Note that Gibbs states with nearest neighbour interactions and MRFs can be distinguished by conditional distributions mentioned in the equation above. In subsection \ref{subsection:cocycles} we will consider a parameterisation of the space of conditional probability distributions to formally study the distinction at that level. Also note that by this definition of Gibbs states the constraints on the support are extrinsic; there is an intrinsic way of constraining the support by allowing the interactions to be infinite. This leads to a different notion of Gibbs states which we will not pursue.

This paper is concerned with conditions on the support of MRFs, which imply that they are Gibbs with some nearest neighbour interaction.

\subsection{Invariant Spaces, Measures and Interactions}
An \emph{automorphism} of the graph $\G$ is a bijection on the vertex set $g:\V\longrightarrow \V$ which preserves the adjacencies, that is, $u\sim v$ if and only if $gu\sim gv$. Let the group of all automorphisms of the graph $\G$ be denoted by $Aut(\G)$.

There is a natural action of $Aut(\G)$ on patterns and configurations: given $a\in \A^F$, $x\in \A^\V$ and $g\in Aut(\G)$ we have $ga\in \A^{gF}$ and $gx\in \A^\V$ given by
$$(ga)_{gv}= a_v\text{ and}$$
$$(gx)_v= x_{g^{-1}v}.$$
This induces an action on measures on the space $\A^\V$ given by
$$(g\mu)(L)=\mu(g^{-1}L)$$
for all measurable sets $L\subset \A^\V$.


For a given subgroup $G\subset Aut(\G)$, a set of configurations $X\subset \A^\V$ is said to be \emph{$G$-invariant} if $gX=X$ for all automorphisms $g\in G$. Similarly a measure $\mu$ on $\A^\V$ is said to be $G$-invariant if $g\mu= \mu$ for all $g\in G$. Note, for any subgroup $G\subset Aut(\G)$, if $\mu$ is a $G$-invariant probability measure then $supp(\mu)$ is also a $G$-invariant configuration space.
If $\G=\Z$ and $G$ is the group of translations of $\Z$, then $G$-invariant closed spaces of configurations in $\A^\Z$ are precisely the shift spaces (theorem 6.1.21, \cite{LM}) and $G$-invariant probability measures correspond to stationary stochastic processes on the $\Z$ lattice.

Let $X\subset \A^\V$ be a closed configuration space invariant under a subgroup $G\subset Aut(\G)$. Then $G$ acts on the interactions on $X$: Given an interaction $V$ on $X$ for all $a\in \A^F$ and $g\in G$
$$gV([a]_F)= V([g^{-1}a]_{g^{-1}F}).$$

\subsection{Hammersley-Clifford Theorem and The Support of MRFs} \label{subsection:Hammersley-Clifford}As in \cite{Markovfieldchain,chandgotiameyerovitch}, closed subsets $X\subset \A^\V$ will be called \emph{topological Markov fields} if for all $x,y\in X$ and finite $F\subset \V$ satisfying $x|_{\partial F}= y|_{\partial F}$ there exists $z\in X$ such that
$$z_v=\begin{cases}
x_v&\text{ if }v\in F\\
y_v&\text{ if }v\in \V\setminus F.
\end{cases}•$$
The support of every MRF is a topological Markov field. If the underlying graph is finite then further $X\subset \A^\V$ is the support of an MRF if and only if it is a topological Markov field. If $G$ is the group of translations of the $\Z$ lattice then $X\subset \A^\Z$ is the support of a $G$-invariant MRF if and only it is a non-wandering(a certain irreducibility condition) $G$-invariant n.n.constraint space(also known as nearest neighbour shifts of finite type). However in general characterising the support of an MRF seems to be a much harder question. This is not even known in case the graph is $\Z^2$ for MRFs invariant under translations.(Question 1 in section 10 of \cite{chandgotiameyerovitch})

A closed configuration space $X\subset \A^\V$ is said to have a safe symbol $\star$ if for all $A\subset \V$ and $x\in X$ we can `legally' replace the symbols on $A$ by $\star$, that is, there exists $y\in X$ satisfying
\begin{equation*}
y_{v}=\begin{cases}
x_v\text{ if }v\in A\\
\star\:\:\text{ if }v\in A^c.
\end{cases}•
\end{equation*}•
We will now state the Hammersley-Clifford Theorem.

\begin{thm}[Hammersley-Clifford Theorem, weak version \cite{HammersleyClifford71,Preston,Chandgotia}]\label{Theorem:Weak_Hammersley-Clifford}
Let a graph $\G=(\V, \E1)$, a configuration space with a safe symbol $X\subset \A^\V$ and an MRF $\mu$ be given such that $supp(\mu)=X$. Then
\begin{enumerate}
\item The measure $\mu$ is Gibbs for some nearest neighbour interaction.
\item If $\mu$ is a $G$-invariant MRF for some subgroup $G\subset Aut(\G)$ then $\mu$ is a Gibbs state for some $G$-invariant nearest neighbour interaction.
\end{enumerate}
\end{thm}

This theorem led to the sparkling of our interest in the field: the study of conditions on the support of MRFs which imply that they are Gibbs. We will now see that the support of measures mentioned in the previous theorem have more structure than it seems.

The following definitions take inspiration from symbolic dynamics(\cite{LM}). Let $\F$ be a given set of patterns on finite sets. Then the configuration space with constraints $\F$ is defined to be
\begin{eqnarray*}
X_\F=\{x\in \A^\V\:|\text{ patterns from }\F\text{ do not appear in }x\}.
\end{eqnarray*}•
A set of constraints $\F$ is called \emph{nearest neighbour} if $\F$ consists of patterns on cliques, that is, for all $[a]_F\in \F$, $diam(F)\leq 1$.

A \emph{n.n.constraint space} is a configuration space with nearest neighbour constraints. Note that if $\G$ is bipartite then $\F$ consists of patterns on edges and vertices. These spaces correspond to nearest neighbour shifts of finite type which are replete in the sphere of symbolic dynamics.

\noindent\textbf{Examples: }
\begin{enumerate}
\item\emph{(The hard core model)} Here the alphabet $\A=\{0,1\}$ and the constraint set is given by
$$\F=\{[1,1]_{u,v}\:|\:u\sim v\}.$$
This constrains the configurations so that symbols on adjacent vertices cannot both be $1$.
\item\emph{(The space of $3$-colourings)} Here the alphabet $\A=\{0,1,2\}$ and the constraint set is given by
$$\F=\{[i,i]_{v,w}\:|\: v\sim w \text{ and }i\in \{0,1,2\}\}.$$
This constrains the configurations so that symbols on adjacent vertices are distinct.
\end{enumerate}

Note that the n.n.constraint spaces given above are of a very special class, namely the constraints on all edges of the graph $\G$ are the same. These configuration spaces correspond to homomorphism spaces defined as the following: Given an undirected graph $\H=(\V_\H, \E1_\H)$ without multiple edges \emph{a homomorphism} from $\G$ to $\H$ is a map $x:\V\longrightarrow \V_\H$ such that for all $v\sim w$ in $\G$, $x_v\sim x_w$ in $\H$. \emph{The space of all homomorphisms }from $\G$ to $\H$ is denoted by $Hom(\G, \H)$. For instance the hard core model is the space $Hom(\G, \H)$ where $\H$ is given by figure \ref{figure:hardsquaregraph}
\begin{figure}[h]
\includegraphics[angle=0,
width=.2\textwidth]{hardsquaregraph.pdf}
\caption{Domain graph for the hard core model \label{figure:hardsquaregraph}}
\end{figure}
and the space of $3$-colourings is $Hom(\G, C_3)$ where $C_3$ is the $3$-cycle with vertices $0$, $1$ and $2$. Also note that the hard core model has a safe symbol $0$ but the space of $3$-colourings does not have any safe symbol.
Given graphs $\G$ and $\H$, $Hom(\G,\H)$ is an n.n.constraint space where the constraint is given by 
$$\F=\{[a,b]_{v,w}\:|\: a\nsim b\in \V_H\text{ and }v\sim w\in \V\}.$$

\noindent Then for all $x\in X_\F$ and vertices $v\sim w\in \V$, $x_v\sim x_w$ which implies $x\in Hom(\G, \H)$. Conversely for all homomorphisms $x\in Hom(\G,\H)$ and vertices $v\sim w\in \V$ we have $[x]_{\{v,w\}}\notin \F$ and hence $x\in X_\F$.

N.N.Constraint spaces arise naturally in the study of MRFs as is shown in the following propositions.
\begin{prop}\label{Proposition: nearest neighbour is TMF}
Let $\A$ be some finite set, $\G=(\V, \E1)$ be a graph and $X\subset \A^{\V}$ be an n.n.constraint space. Then $X$ is a topological Markov field.
\end{prop}
\begin{proof}
Consider $A\subset \V$ finite and $x, y\in X$ such that $x|_{\partial A}= y|_{\partial A}$. We want to prove that $z\in \A^\V$ defined by
\begin{equation*}
z_v=
\begin{cases}
x_v\ if\ v\in A\cup \partial A\\
y_v\ if\ v\in A^c
\end{cases}
\end{equation*}•
is an element of $X$. Let $B\subset \V$ be a clique. If $B\cap A\neq \phi$ then $B\subset A\cup \partial A$ and $z|_{B}= x|_B\in \B_B(X)$ else $B\cap A= \phi$ implying $z|_{B}= y|_B\in \B_B(X)$. Since $X$ is an n.n.constraint space $z\in X$.
\end{proof}
The following proposition completes the bridge between MRFs and n.n.constraint spaces.
\begin{prop}\label{Proposition: TMF is nearest neighbour}
Let $\G=(\V, \E1)$ be a given graph and $X$ be a topological Markov field on the graph $\G$ with a safe symbol. Then $X$ is an n.n.constraint space.
\end{prop}
\noindent\textbf{Remark:} If $\mu$ is an MRF then $supp(\mu)$ is a topological Markov field. Thus this proposition implies that if a measure $\mu$ satisfies the hypothesis of the weak Hammersley-Clifford theorem(Theorem \ref{Theorem:Weak_Hammersley-Clifford}), that is, if $\mu$ is an MRF such that $supp(\mu)$ has a safe symbol then $supp(\mu)$ is an n.n.constraint space. The conclusion of this proposition does not hold without assuming presence of a safe symbol. (comments following proof of proposition 3.5 in \cite{Markovfieldchain})
\begin{proof}
Let $\star$ be a safe symbol for $X$. Consider the set
\begin{eqnarray*}
\F=\{a\in \A^A\:|\: A\subset \V \text{ forms a clique and there does not exist }x\in X \text{ such that } x|_A=a\}.
\end{eqnarray*}•
Note that $ X\subset X_\F$ and if $A\subset \V$ is a clique then $\B_A(X_\F)= \B_A(X)$. We want to prove that $X_\F\subset X$. We will proceed by induction on $n\in \N$, the hypothesis being: Given $A\subset \V$ such that $|A|=n$, $\B_A(X_\F)\subset \B_A(X)$.

The base case follows immediately. Suppose for some $n\in \N$, given $A\subset \V$ satisfying $|A|\leq n$, $\B_A(X_\F)\subset \B_A(X)$.

For the induction step consider $A\subset \V$ such that $|A|=n+1$. There are two cases to consider: If $A$ is a clique then $\B_A(X_\F)=\B_A(X)$. If $A$ is not a clique then there exists $v\in A$ such that $|\partial\{v\}\cap A|<n$. Let $a\in \B_A(X_\F)$. We will prove that $a\in \B_A(X)$. Now $|\left(\{v\}\cup \partial\{v\}\right)\cap A|, |A\setminus \{v\}|\leq n$, thus the induction hypothesis implies
$$a|_{(\{v\}\cup \partial\{v\})\cap A}\in \B_{(\{v\}\cup \partial\{v\})\cap A}(X)$$
and
$$a|_{A\setminus \{v\}}\in \B_{A\setminus \{v\}}(X).$$
Consider $x,y\in X$ such that
$$x|_{(\{v\}\cup \partial\{v\})\cap A}= a|_{(\{v\}\cup \partial\{v\})\cap A}$$
and
$$y|_{A\setminus \{v\}}= a|_{A\setminus \{v\}}.$$
Since $\star$ is a safe symbol for $X$ therefore
$x^\star, y^\star\in \A^\V$ given by
$$x^\star_w=\begin{cases}
x_w\ if\ w\in (\{v\}\cup \partial\{v\})\cap A\\
\star\ \ \ otherwise
\end{cases}•$$
and
$$y^\star_w=\begin{cases}
y_w\ if\ w\in A\setminus\{v\}\\
\star\ \ \ otherwise
\end{cases}•$$
are elements of $X$. Note that $x^\star_w=x_w= a_w$, $y^\star_w =y_w= a_w$ if $w\in \partial\{v\}\cap A$ and $x^\star_w= y^\star_w= \star$ if $w\in A^c$. Therefore $x^\star|_{ \partial\{v\}}= y^\star|_{ \partial\{v\}}$. Since $X$ is a topological Markov field, $z\in \A^\V$ defined by
\begin{equation*}
z_w=
\begin{cases}
x^\star_w\ if\ w\in \{v\}\cup \partial \{v\}\\
y^\star_w\ otherwise
\end{cases}•
\end{equation*}•
is an element of $X$. But $z_v= x^\star_v= x_v= a_v$ and $z_w= y^\star_w= y_w= a_w$ if $w\in A\setminus \{v\}$. Hence $z|_A=a\in \B_A(X)$. This completes the induction. By proposition \ref{Proposition:language gives all} $X_{\F}\subset X$. Hence $X= X_\F$.
\end{proof}

N.N.Constraint spaces allow us to change configurations one site at a time provided the edge-constraints are satisfied. To state this rigorously we define the following: given $x\in \A^\V$, and distinct vertices $w_1, w_2, \ldots, w_r \in\V$ and $c_1, c_2, \ldots, c_r\in \A$ we denote by $\theta^{w_1, w_2,\ldots, w_r}_{c_1, c_2,\ldots,c_r}(x)$ an element of $\A^\V$ given by
\begin{equation*}
(\theta^{w_1,w_2, \ldots, w_r}_{c_1, c_2,\ldots, c_r}(x))_u=
\begin{cases}
x_u\text{ if }u\neq w_1, w_2\ldots, w_r\\
c_i\ \text{ if }u=w_i\text{ for some }1\leq i \leq r.
\end{cases}
\end{equation*}•

\begin{prop}\label{prop:changing_remain_nnconstraint}
Let $\G=(\V, \E1)$ be a bipartite graph. Suppose $X\subset \A^\V$ is an n.n.constraint space and $x\in X$. Let $w_1, w_2, \ldots, w_r \in\V$ be distinct vertices such that $w_i \nsim w_j$ for $1\leq i,j \leq r$ and $c_1, c_2, \ldots, c_r\in \A$ such that $[c_i, x_{w^\prime}]_{\{w_i, w^\prime\}}\in \B_{\{w_i, w^\prime\}}(X)$ for all $w^\prime\sim w_i$ and $1\leq i \leq r$. Then $\theta^{w_1, w_2, \ldots, w_r}_{c_1, c_2\ldots, c_r}(x)\in X$.
\end{prop}
Specialising to $r=1$, if $X\subset \A^\V$ is an n.n.constraint space and $x\in X$ then for $v\in \V$ and $c\in \A$, $\theta^v_c(x)\in X$ if and only if $[x_w,c]_{\{w,v\}}\in \B_{\{w,v\}}(X)$ for all $w\sim v$.
\begin{proof}
The constraint set for $X$ consists only of patterns on edges and vertices. Thus it is sufficient to check for all $v\sim w$ that
$$[\theta^{w_1, w_2, \ldots, w_r}_{c_1, c_2\ldots, c_r}(x)]_{\{v,w\}}\in \B_{\{v,w\}}(X).$$

Since $w_i\nsim w_j$ for all $1\leq i,j\leq r$ at most one among $v$ and $w$ is $w_i$ for some $1\leq i\leq r$. If both of them are not equal to $w_i$ then
$$[\theta^{w_1, w_2, \ldots, w_r}_{c_1, c_2\ldots, c_r}(x)]_{\{v,w\}}=[x]_{\{v,w\}}\in\B_{\{v,w\}}(X). $$
Otherwise we may assume $v=w_i$ for some $1\leq i \leq r$ giving us
$$[\theta^{w_1, w_2, \ldots, w_r}_{c_1, c_2\ldots, c_r}(x)]_{\{v,w\}}=[c_i,x_w]_{\{w_i,w\}}\in\B_{\{w_i,w\}}(X). $$
\end{proof}

\subsection{The Asymptotic Relation, Cocycles and the Strong Version of the Hammersley-Clifford Theorem} \label{subsection:cocycles}
This subsection shall closely follow section 3 of \cite{chandgotiameyerovitch}. Given a closed configuration space $X\subset \A^\V$ the set of \emph{asymptotic pairs} is given by
$$\Delta_X=\{(x,y)\in X\times X\:|\: x,y \text{ differ at finitely many sites}\}.$$
In the case when the graph $\G= \Z^d$ and $X$ is a configuration space invariant under translation, the asymptotic relation coincides with the \emph{homoclinic relation}. If $\G$ is finite then $\Delta_X=X\times X$.
Following \cite{brightwell2000gibbs} a space is called \emph{frozen} if
$$\Delta_X=\{(x,x)\:|\:x\in X\}.$$


%We will now parametrise the space of conditional probabilities incontingent of measures. This is the well known formalism of \emph{Markov specifications}.
%
%Any MRF $\mu$ yields conditional probabilities of the form $\mu([a]_F\:|\: [b]_{\partial F})$ for all finite set of vertices $F\subset \V$ and patterns $a\in \A^F$, $b\in \A^{\partial F}$ where $\mu([b]_{\partial F})>0$. The collection of such conditional probabilities is called \emph{Markov specification} associated with $\mu$. It may so happen that there are two distinct MRFs which correspond to the same Markov specification. Determining conditions under which the specification completely determines the Markov measure is a challenging problem \cite{burtonsteiffnonuniquesft} but will not be part of the discussion here.
%
%More generally, consider a topological Markov field $X\subset \A^\V$. A \emph{Markov specification} on $X$ is an assignment for each finite set $F\subset \V$ and pattern $b\in \B_{\partial F}(X)$ on the boundary of $F$ a probability measure $\Theta_{F,b}$ on $\B_F(X)$ satisfying the following conditions:
%\begin{enumerate}
%\item\textbf{Support Condition:} For any finite $F\subset \V$ and patterns $a\in \B_F(X)$, $b\in \B_{\partial F}(X)$ the probability $\Theta_{F, b}(a)>0$ if $a\vee b\in \B_{F\cup \partial F}$, that is,
%$$supp(\Theta_{F,b})=\{a\in\B_F(X)\:|\:a\vee b \in \B_{F\cup \partial F}(X) \}.$$
%\item\textbf{Markov Condition:} For any finite set $F\subset \V$ and pattern $b\in \B_{\partial F}(X)$, the probability measures $\Theta_{F,b}$ is an MRF on the induced subgraph on $F$.
%\item
%\textbf{Consistency Condition:} For any $F\subset H\subset \V$ and patterns $b\in \B_{\partial F}(X)$, $c\in \B_{\partial H}$ where $b_v=c_v$ for all $v\in \partial F\cap \partial H$, then for any $a\in \B_F(X)$
%$$\Theta_{F, b}(a)=\frac{\Theta_{H,c}([a\vee b]_{F\cup \partial F})}{\Theta_{H,c}([b]_{\partial F})}.$$
%\end{enumerate}•
%
%Given any MRF $\mu$ such that the $supp(\mu)=X$, the collection of conditional probabilities on $\B_F(X)$ obtained for every finite set $F\subset \V$ form a specification for $X$. Conversely, given any markov specification $\Theta$ on a topological Markov field $X$ there exists an MRF $\mu$ such that the \emph{associated} Markov specification is $\Theta$\cite{Georgii}. Furthermore if the underlying graph $\G$ is amenable, then given a specification invariant under a subgroup of automorphisms $G\subset Aut(\G)$, there exists a $G$-invariant MRF $\mu$ associated with the Markov specification $\Theta$. However, there may be $G$-invariant Markov specifications on a topological Markov field $X$ such that there is no $G$-invariant MRF $\mu$ such that $supp(\mu)=X$. In the case when the underlying graph is $\Z^d$ and $G$ is the set of translations such an example has been provided in \cite{chandgotiameyerovitch}.

Following \cite{chandgotiameyerovitch} we shall now parametrise the space of conditional probabilities. A (real-valued) \emph{$\Delta_X$-cocycle} is a function $M:\Delta_X\longrightarrow \R$ satisfying
\begin{eqnarray*}\label{equation:cocycle_condition}
M(x,z)=M(x,y)+M(y,z) \text{ whenever }(x,y),(y,z)\in \Delta_X.
\end{eqnarray*}
If $M$ is a $\Delta_X$-cocycle then for all pairs $(x,y)\in \Delta_X$ 
\begin{eqnarray}
M(x,y)+M(y,x)=M(x,x)=M(x,x)+M(x,x)=0.\label{equation:flip_gives_negative_same_0}
\end{eqnarray}
A $\Delta_X$-cocycle is called a \emph{Markov cocycle} if in addition for any $(x, y)\in \Delta_X$, the value $M(x,y)$ depends only upon patterns on vertices where $x$ and $y$ differ and its boundary, that is, if $F$ is the set of vertices where $x$ and $y$ differ then
$$M(x,y)=c_{x|_{F\cup \partial F}, y|_{F\cup \partial F}}.$$
Given a subgroup $G\subset Aut(\G)$, a $G$-invariant $\Delta_X$-cocycle is a $\Delta_X$-cocycle $M$ which satisfies
$$M(x,y)=M(gx, gy)$$
for all $(x,y)\in \Delta_X$ and $g\in G$.

Any MRF $\mu$ yields a Markov cocycle $M$ on $supp(\mu)$ by
\begin{equation}\label{equation:specification_to_cocycle}
M(x,y)= \log\left(\frac{\mu([y]_\Lambda)}{\mu([x]_{\Lambda})}\right)\text{ for all }(x,y)\in \Delta_{supp(\mu)}
\end{equation}
for any $\Lambda\supset F\cup \partial F$ where $F$ is the set of vertices where $x$ and $y$ differ. Since $\mu$ is an MRF the right hand side is independent of the choice of $\Lambda$. For example the uniform MRF(where conditioned on the boundary, all patterns are equiprobable) yields the Markov cocycle $M=0$ and if the graph $\G$ is finite then any MRF $\mu$ yields the cocycle
\begin{equation*}
M(x,y)= \log\left(\frac{\mu(y)}{\mu(x)}\right)\text{ for all }x,y\in supp(\mu).
\end{equation*}
The function $\rho:\Delta_{supp(\mu)}\longrightarrow \R_+$ given by $\rho(x,y)=e^{M(x,y)}$ is the $\Delta_X$-Radon-Nikodym cocycle of $\mu$ as in \cite{petersen_schmidt1997}. This correspondence can be further generalised; given a topological Markov field we can consider a system of consistent conditional probability distributions with the Markov property called Markov specifications. There is a bijective correspondence between the space of Markov cocycles and Markov specifications. For a more detailed discussion on this topic see \cite{chandgotiameyerovitch}.

% : If $\Theta$ is a Markov specification on $X$, the corresponding Markov cocycle is given by
%$$M(x,y)=\log(\Theta_{F,[y]_{\partial F}}([y]_{\partial F}))-\log(\Theta_{F,[y]_{\partial F}}([x]_{\partial F}))$$
%where $(x,y)\in \Delta_X$ such that $x_v=y_v$ for all $v\in F^c$.
%
%Conversely, given a Markov cocycle $M$ on $X$, the corresponding specification $\Theta$ is given by
%$$\Theta_F$$

Given a topological Markov field $X$, \emph{the Gibbs cocycle }on $X$ corresponding to an interaction $V$ is a $\Delta_X$-cocycle given by
$$M(x,y)=\sum_{A\subset \V \text{ finite}}V([y]_A)-V([x]_A) \text{ for all } (x,y)\in \Delta_X.$$

Note that the sum is finite since there are only finitely many non-zero terms whenever $(x,y)\in \Delta_X$. Evidently any Gibbs cocycle with a nearest neighbour interaction is a Markov cocycle. This corresponds to the fact that every Gibbs state with a nearest neighbour interaction is an MRF.

Thus the distinction between MRFs and Gibbs state with a nearest neighbour interaction on the level of measures naturally yields a distinction on the level of corresponding cocycles.

\begin{prop}
Let $\mu$ be an MRF and $M$ be a Markov cocycle on $supp(\mu)$ given by
\begin{equation*}
M(x,y)= \log\left(\frac{\mu([y]_\Lambda)}{\mu([x]_{\Lambda})}\right)\text{ for all }(x,y)\in \Delta_{supp(\mu)}
\end{equation*}
for any $\Lambda\supset F\cup \partial F$ where $F$ is the set of vertices where $x$ and $y$ differ. Then $\mu$ is a Gibbs state with a nearest neighbour interaction if and only if $M$ is a Gibbs cocycle with some nearest neighbour interaction.
\end{prop}

The proof follows from the discussions preceding the proposition.

Let $X$ be a topological Markov field. We shall denote the set of all Markov cocycles by $\M_X$ and the set of all Gibbs cocycles with nearest neighbour interactions by $\Gi_X$ . Given a subgroup $G\subset Aut(\G)$ we denote by $\M^G_X$ the set of all $G$-invariant Markov cocycles and by $\Gi^G_X$ the space of all Gibbs cocycles with $G$-invariant nearest neighbour interactions. Note that the space of $G$-invariant Gibbs cocycles with nearest neighbour interactions is not always the same as the space of Gibbs cocycles with $G$-invariant nearest neighbour interaction. An example can be found in section 5 of \cite{chandgotiameyerovitch}.


The space of Markov cocycles has a natural vector space structure. Indeed given $M_1, M_2\in \M_X$ and $c\in \R$
$$cM_1+ M_2\in \M_X$$
where the addition is point-wise, that is, $(cM_1+M_2)(x,y)= cM_1(x,y)+M_2(x,y)$ for all $(x,y)\in \Delta_X$. Similarly $\Gi_X$ and when given a subgroup $G\subset Aut(\G)$, $\M^G_X$ and $\Gi^G_X$ are subspaces of $\M_X$. If $\G$ is a finite graph the conditions under which $\M_X= \Gi_X$ are very similar to the balanced conditions as mentioned in \cite{mouss}.

A close inspection of the proof of the weak version of the Hammersley-Clifford theorem(theorem \ref{Theorem:Weak_Hammersley-Clifford}) yields another formulation in terms of cocycles. We will not use this or the weaker version for proving the results stated in this paper.
\begin{thm}[Hammersley-Clifford, strong version] \label{Theorem:Strong_Hammersley-Clifford}Let $X$ be a topological Markov field with a safe symbol. Then:
\begin{enumerate}
\item
Any Markov cocycle on $X$ is a Gibbs cocycle with a nearest neighbour interaction, that is, $\M_X=\Gi_X$.
\item
Given a subgroup $G\subset Aut(\G)$ every $G$-invariant Markov cocycle on $X$ is a Gibbs cocycle with some $G$-invariant nearest neighbour interaction, that is, $\M^G_X=\Gi^G_X$.
\end{enumerate}•
\end{thm}

Given a topological Markov field $X$ with a safe symbol, any MRF $\mu$ such that the $supp(\mu)=X$ yields by equation $\ref{equation:specification_to_cocycle}$ a Markov cocycle on $X$. Moreover if $\mu$ is invariant under a subgroup $G\subset Aut(\G)$ then the cocycle obtained is also invariant under the same. By theorem \ref{Theorem:Strong_Hammersley-Clifford} the cocycle is Gibbs with a $G$-invariant nearest neighbour interaction. Thus we know that the measure is Gibbs with some $G$-invariant nearest neighbour interaction. Hence theorem \ref{Theorem:Strong_Hammersley-Clifford} generalises theorem \ref{Theorem:Weak_Hammersley-Clifford}. However the proof of the first part of this version follows from theorem \ref{Theorem:Weak_Hammersley-Clifford} with the additional knowledge that given a Markov cocycle on a topological Markov field $X$ with a safe symbol there exists a corresponding MRF $\mu$ such that $supp(\mu)=X$. This in turn is implied by arguments very similar to those in the proof of proposition 3.2 in \cite{chandgotiameyerovitch}. The second part of the theorem can be proved using theorem 2.0.6 in \cite{Chandgotia}, noting that the conclusion holds even if the MRF is not invariant under $G$ but the corresponding Markov cocycle is.

We seek a generalisation of theorem \ref{Theorem:Strong_Hammersley-Clifford} when the graph $\G$ is bipartite.




\section{Hammersley-Clifford Spaces and Foldings}
\label{section:Hamm-cliff space}
\subsection{Hammersley-Clifford Spaces}
\label{subsection:Hamm-cliff spaces}
A topological Markov field $X\subset \A^\V$ is called \emph{Hammersley-Clifford} if the space of Markov cocycles on $X$ is equal to the space of Gibbs cocycles on $X$, that is, $\M_X= \Gi_X$. If $X$ is invariant under the some subgroup $G\subset Aut(\G)$ then $X$ is said to be \emph{$G$-Hammersley-Clifford} if $\M^G_X= \Gi^G_X$.

\noindent\textbf{Examples:}
\begin{enumerate}
\item
A frozen space of configurations. \label{enumerate:frozen_configurations}

If $X$ is frozen then $\Delta_X$ is the diagonal relation. Then $M\equiv 0$ is the only Markov cocycle on the space. It is Gibbs for the interaction $V\equiv 0$.
\item
A topological Markov field with a safe symbol.\label{enumerate:tmf_safe_symbol}

Theorem \ref{Theorem:Strong_Hammersley-Clifford} implies that any $G$-invariant configuration space with a safe symbol is $G$-Hammersley-Clifford for any subgroup $G\subset Aut(\G)$.

\item
$Hom(\G,Edge)$ where $Edge$ consists of two vertices $0$ and $1$ connected by a single edge. \label{enumerate:homomorphisms_edge}

If $\G$ is not bipartite then $Hom(\G, Edge)$ is empty. If $\G$ is bipartite and connected, then $Hom(\G, Edge)$ consists of two configurations only. It follows that $Hom(\G, Edge)$ is $G$-Hammersley-Clifford for any subgroup $G\subset Aut(\G)$ and graph $\G$.

\item
$Hom(\Z^d, C_n)$ where $C_n$ is an n-cycle, $d>1$ and $n\neq 4$.\label{enumerate:homomorphisms_cycle}\cite{chandgotiameyerovitch}

This gives examples of Hammersley-Clifford spaces which are not $G$-Hammersley-Clifford spaces for some subgroup $G\subset Aut(\Z^d)$. It will follow from theorem \ref{thm:G-invariant main theorem} below and example \ref{enumerate:homomorphisms_edge} above that $Hom(\G, C_4)$ is both Hammersley-Clifford and $G$-Hammersley-Clifford for all bipartite graphs $\G$ and subgroups $G\subset Aut(\G)$.
\end{enumerate}

\subsection{Markov-similar and $V$-Good Pairs}\label{subsection:Markov-similar}
Suppose we are given a closed configuration space $X$, a Markov cocycle $M\in \M_X$ and an interaction $V$ on $X$. If $M$ is not Gibbs with the interaction $V$ we might be still interested in the extent to which it is not. An asymptotic pair $(x,y)\in \Delta_X$ is called \emph{(M,V)-good} if
$$M(x,y)=\sum_{S\subset \V\text{ finite}}\left(V([y]_S)- V([x]_S)\right).$$
In most cases the Markov cocycle $M$ will be fixed, so we will drop $M$ and call a pair $V$-good instead of $(M,V)$-good. An asymptotic pair $(x,y)\in \Delta_X$ is said to be \emph{Markov-similar} to $(z,w)$ if there is a finite set $A\subset \V$ such that
\begin{eqnarray*}
x_u&=&y_u\text{, }\\
z_u&=&w_u\text{ for }u\in A^c
\end{eqnarray*}•\
and
\begin{eqnarray*}
x_u&=&z_u\text{,}\\
y_u&=&w_u\text{ for }u \in A\cup \partial A.
\end{eqnarray*}•
Being $V$-good is infectious.
\begin{prop}\label{prop:V-goodness_equivalence_markov_similar}
Let $X$ be an n.n.constraint space, $M$ a Markov cocycle and $V$ a nearest neighbour interaction on $X$. The set of $V$-good pairs is an equivalence relation on $X$. Additionally if $(x,y),(z,w)\in \Delta_X$ are Markov similar then $(x,y)$ is $V$-good if and only if $(z,w)$ is $V$-good.
\end{prop}
\begin{proof} The reflexivity and symmetry of the relation $V$-good follows from equation \ref{equation:flip_gives_negative_same_0} and the cocycle condition implies that the relation is transitive. Thus the relation is an equivalence relation.

Let $(x,y), (z,w)\in \Delta_X$ be Markov-similar pairs. Since $M$ is a Markov cocycle
\begin{equation}
M(x,y)= M(z,w).\label{equation:Markovsimilarcocycleequal}
\end{equation}•
Let $A\subset \V$ be a finite set such that
$$x_u=z_u\text{ and }y_u=w_u$$
for $u\in A\cup \partial A$ and
$$x_u=y_u\text{ and }z_u=w_u$$
for $u \in A^c$. If $S\subset \V$ is a clique then either $S\subset A\cup \partial A$ or $S\subset A^c$.
If $S\subset A\cup \partial A$ then
$$x|_S= z|_S\text{ and }y|_S=w|_S$$
implying
$$V([y]_S)-V([x]_S)=V([w]_S)-V([z]_S).$$
If $S\subset A^c$ then
$$x|_S=y|_S\text{ and }z|_S=w|_S$$
implying
$$V([y]_S)-V([x]_S)=V([w]_S)-V([z]_S)=0.$$
Since $V$ is a nearest neighbour interaction
$$\sum_{S\subset\V\text{ finite}}V([y]_S)-V([x]_S)=\sum_{S\subset\V\text{ finite}}V([w]_S)-V([z]_S).$$
Since $(x,y)$ is a $V$-good pair by equation \ref{equation:Markovsimilarcocycleequal}
$$M(z,w)=M(x,y)=\sum_{S\subset \V\text{ finite}}\left(V([y]_S)- V([x]_S)\right)=\sum_{S\subset\V\text{ finite}}V([w]_S)-V([z]_S)$$
completing the proof.
\end{proof}

\begin{corollary}\label{corollary:chain_of_V-goodness}
Let $X$ be an n.n.constraint space, $M$ a Markov cocycle and $V$ a nearest neighbour interaction on $X$. Suppose for some $(x,y)\in \Delta_X$ there exists a chain $x=x_1, x_2, x_3, \ldots, x_n=y$ such that each $(x_i, x_{i+1})\in \Delta_X$ and is Markov similar to a $V$-good pair. Then $(x,y)$ is $V$-good.
\end{corollary}

This follows from lemma \ref{prop:V-goodness_equivalence_markov_similar}






\subsection{Graph and Configuration Folding}
\label{subsection:Graphfolding}
We shall now introduce graph folding and extract some of its properties so as to define folding for configuration spaces. Graph folding was introduced in \cite{nowakowskiwinkler} and used in \cite{brightwell2000gibbs} so as to prove a slew of properties which are satisfied by a given graph if and only if it is satisfied by its folds. Fix some finite undirected graph $\H=(\V_\H,\E1_\H)$ without multiple edges. For any vertex $a\in \H$ we say that $\H\setminus\{a\}$ is a \emph{fold} of the graph $\H$ if there exists $b\in \H\setminus\{a\}$ such that
$$\{c\in \V_\H\:|\: c\sim a\}\subset \{c\in \V_\H\:|\: c\sim b\}.$$
In such a case we say that $a$ is folded into $b$.

For example in the 4-cycle $C_4$ the vertex $3$ can be folded into the vertex $1$. However no vertex can be folded in the 3-cycle $C_3$.
\begin{figure}[h]
\includegraphics[angle=0,
width=.3\textwidth]{C4.pdf}
\caption{$C_4$ and $C_3$}
\end{figure}

For any vertex $v\in \V$ the \emph{$n$-ball around $v$} is given by
$$D_n(v)=\{w\in \V\:|\: d_\G(v,w)\leq n\}$$
where $d_\G$ is the graph distance on $\G$.

We wish to generalise the following property:

\begin{prop} Consider a bipartite graph $\G=(\V,\E1)$, a graph $\H=(\V_\H, \E1_\H)$ and vertices $a,b\in \V_\H$ where the vertex $a$ can be folded into the vertex $b$. Let $X=Hom(\G, \H)$. Then for all edges $(v_1,v_2), (v_2, v_3)\in \E1$ and $c\in \V_\H$, $[a,c]_{\{v_1, v_2\}}\in \B_{\{v_1, v_2\}}(X)$ implies
\begin{eqnarray*}
[b,c]_{\{v_1, v_2\}}\in \B_{\{v_1, v_2\}}(X)\\
\left[c,b\right]_{\{v_2, v_3\}}\in \B_{\{v_2, v_3\}}(X)\text{ and}\\
\left[b\right]_{\partial D_1(v_1)}\in \B_{\partial D_1(v_1)}(X).
\end{eqnarray*}•
\end{prop}
\begin{proof} Since $a\sim c$ and $a$ can be folded into the vertex $b$ we have $b\sim c$. Consider partite classes $P_1, P_2\subset \V$ of $\G$ such that $v_1\in P_1$. Then the configuration $x\in \V^{\V_\H}$ given by
$$x_{v}=\begin{cases}
b\text{ if }v\in P_1\\
c\text{ if }v\in P_2\end{cases}$$
is an element of $Hom(\G, \H)$. Thus
\begin{gather*}
[b,c]_{\{v_1, v_2\}}=[x]_{\{v_1,v_2\}}\in \B_{\{v_1, v_2\}}(X)\\
\left[c,b\right]_{\{v_2, v_3\}}=[x]_{\{v_2,v_3\}}\in \B_{\{v_2, v_3\}}(X)\text{ and}\\
\left[b\right]_{\partial D_1(v_1)}=[x]_{\partial D_1(v_1)}\in \B_{\partial D_1(v_1)}(X).
\end{gather*}•
\end{proof}


For the rest of the paper fix a bipartite graph $\G=(\V, \E1)$. Let $X\subset \A^\V$ be an n.n.constraint space. Given distinct symbols $a,b\in \A$, we say that $a$ can be \emph{folded} into $b$ if for all edges $(v_1,v_2), (v_2, v_3)\in \E1$ and $c\in \A$, $[a,c]_{\{v_1, v_2\}}\in \B_{\{v_1, v_2\}}(X)$ implies
\begin{eqnarray}
[b,c]_{\{v_1, v_2\}}\in \B_{\{v_1, v_2\}}(X), \label{equation:foldingdefn1}\\
\left[c,b\right]_{\{v_2, v_3\}}\in \B_{\{v_2, v_3\}}(X)\text{ and}\label{equation:foldingdefn2}\\
\left[b\right]_{\partial D_1(v_1)}\in \B_{\partial D_1(v_1)}(X).\label{equation:foldingdefn3}
\end{eqnarray}•
In such a case, $X\cap (\A\setminus\{a\})^\V$ is called a \emph{fold} of $X$ and $X$ is called a \emph{unfold} of $X\cap (\A\setminus\{a\})^\V$. Note that $X\cap (\A\setminus\{a\})^\V$ is still an n.n.constraint space and is obtained by forbidding the symbol $a$ in $X$. Further if $X$ is invariant under a subgroup $G\subset Aut(\G)$ then $X\cap (\A\setminus\{a\})^\V$ is also invariant under G. Let $X_{a}$ denote the fold $X\cap (\A\setminus\{a\})^\V$. The idea of folding is captured by equation \ref{equation:foldingdefn1} while equations \ref{equation:foldingdefn2} and \ref{equation:foldingdefn3} are reminiscent of homomorphism spaces. Indeed if an n.n.constraint space $X$ satisfies equation \ref{equation:foldingdefn1} then for all $x\in X$ and $v\in \V$ such that $x_v=a$, the configuration $\theta^v_b(x)\in X$. Thus if $a$ folds into $b$ then any appearance of $a$ in any configuration in $X$ can be replaced by $b$. Recall that a safe symbol can replace any other symbol. Thus the notion of folding generalises the notion of a safe symbol.

\begin{prop}\label{prop:fold_generalise_fold}
Let $\G=(\V, \E1)$ be a bipartite graph. Let $X\subset \A^\V$ be an n.n.constraint space with a safe symbol $\star$. Then any symbol $a\in \A\setminus\{\star\}$ can be folded into $\star$. The resulting fold $X_a$ is also an n.n.constraint space with the same safe symbol $\star$.
\end{prop}

Indeed $X_a$ is obtained just by forbidding the symbol $a$ from $X$ and $\star$ is still a safe symbol. In general it is not necessary that the symbol being folded into has to be a safe symbol. For instance given any bipartite graph $\G$ the space $Hom(\G,C_4)$, can be folded in two steps to $Hom(\G,Edge)$, yet $C_4$ does not have any safe symbol. Note that the unfold of an n.n.constraint space with a safe symbol need not have a safe symbol.
For example if $\H$ is the graph given by figure \ref{figure:safe_symbol}
\begin{figure}[h]
\includegraphics[angle=0,
width=.1\textwidth]{safesymbol.pdf}
\caption{$\H$\label{figure:safe_symbol}}
\end{figure}
then for any bipartite graph $\G$ the top vertex is a safe symbol in the space $Hom(\G, H)$.\newpage 
\noindent However if we attach trees to $\H$ to obtain $\H^\prime$ given by figure \ref{figure:fold_to_safe}
\begin{figure}[h]
\includegraphics[angle=0,
width=.2\textwidth]{foldtosafe.pdf}
\caption{$\H^\prime$\label{figure:fold_to_safe}}
\end{figure}
then $Hom(\G, \H^\prime)$ does not have any safe symbol but can be folded into $Hom(\G, \H)$ by folding in the trees attached to $\H$.

Folding induces a natural map between the spaces of configurations and their cocycles as demonstrated by the following proposition.

\begin{prop} \label{proposition:induced_map_cocycles}
Let $\G$ be a bipartite graph and $G\subset Aut(\G)$ be a subgroup. Suppose $X\subset \A^\V$ is a $G$-invariant n.n.constraint space and let $X_a$ be its fold. Then the linear map $F: \M^G_X\longrightarrow \M^G_{X_a}$ given by $F(M)= M|_{\Delta_{X_a}}$ is surjective and $F(\Gi^G_X)=\Gi^G_{X_a}$.
\end{prop}

\begin{proof}


If $M\in \Gi^G_X$ then the restriction of the $G$-invariant nearest neighbour interaction for $M$ to $X_a$ gives us a $G$-invariant nearest neighbour interaction for $F(M)$ proving that $F(M)\in \Gi^G_{X_a}$. Thus $F(\Gi^G_X)\subset\Gi^G_{X_a}$. We will construct a map $\phi^\star: \M^G_{X_a}\longrightarrow \M^G_X$ such that $\phi^\star(\Gi^G_{X_a})\subset \Gi^G_{X}$ and $F\circ \phi^\star$ is the identity map on $\M^G_{X_a}$. Note that this is sufficient to conclude that $F$ is surjective and $F(\Gi^G_X)=\Gi^G_{X_a}$ thereby completing the proof.

The folding induces a mapping $\phi:X\longrightarrow X_a$ given by
\begin{equation*}
\phi(x)_v=\begin{cases}x_v\text{ if }x_v\neq a\\
b\ \ \text{ if }x_v =a
\end{cases}
\end{equation*}•
for all $x\in X$ and $v\in \V$. Let $g\in G$ and $x\in X$. Then
$$(\phi(gx))_v=\begin{cases}
(gx)_v=x_{g^{-1}v}\text{ if }x_{g^{-1}v}\neq a\\
b\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{ if }(gx)_v=x_{g^{-1}v}=a
\end{cases}•$$
and
$$(g(\phi(x))_v=(\phi(x))_{g^{-1}v}=\begin{cases}
x_{g^{-1}v}\text{ if }x_{g^{-1}v}\neq a\\
b\ \ \ \ \ \ \text{ if }x_{g^{-1}v} =a.
\end{cases}•$$
Therefore $\phi$ commutes with the action of $G$. Note that $\phi|_{X_a}$ is the identity.

The map $\phi$ in turn induces a map between the cocycles which we shall now describe. Let $M \in \M_{X_a}^G$ be a Markov cocycle. Consider $M^\prime: \Delta_X\longrightarrow \R$ given by
$$M^\prime(x,y)= M(\phi(x), \phi(y)).$$
We will prove that $M^\prime\in \M^G_X$. 

\noindent\emph{Cocycle condition:} If $(x,y), (y,z)\in \Delta_X$ then
$$M^\prime(x,y)+ M^\prime(y,z)=M(\phi(x), \phi(y))+M(\phi(y), \phi(z))= M(\phi(x),\phi(z))= M^\prime(x,z).$$

\noindent\emph{Markov condition: } If $(x,y), (z,w)\in \Delta_X$ are Markov-similar then $(\phi(x), \phi(y)), (\phi(z), \phi(w))\in \Delta_{X_{a}}$ are Markov-similar as well implying $M(\phi(x),\phi(y))= M(\phi(z), \phi(w))$ and thus 
\begin{eqnarray*}
M^\prime(x, y)&=&M(\phi(x), \phi(y))\\
&=& M(\phi(z), \phi(w))\\
&=& M^\prime(z,w)
\end{eqnarray*}•
which verifies the Markov condition for $M^\prime$.

\noindent\emph{$G$-invariance condition: }
Since $\phi$ commutes with the action of $G$, for all $g\in G$
$$M^\prime(gx,gy)=M(\phi(gx), \phi(gy))=M(g(\phi(x)), g(\phi(y)))=M(\phi(x), \phi(y))= M^\prime(x,y).$$
Hence $M^\prime\in \M^G_X$. Moreover if $M\in \Gi^G_{X_a}$ with a $G$-invariant nearest neighbour interaction $V$, then for all $(x,y)\in \Delta_{X}$
$$M^\prime(x,y)=M(\phi(x),\phi(y))= \sum_{A\subset \V\text{ finite }}V([\phi(y)]_A)-V([\phi(x)]_A)$$
proving that $V\circ \phi$ is a $G$-invariant nearest neighbour interaction for $M^\prime$.

Thus the map $\phi^\star: \M^G_{X_a}\longrightarrow \M^G_{X}$ given by
$$\phi^\star(M)(x,y)=M(\phi(x), \phi(y))$$
satisfies $\phi^\star(\Gi^G_{X_a})\subset \Gi^G_{X}$. Moreover since $\phi|_{X_a}$ is the identity map on $X_a$ therefore $\phi^\star( M)|_{\Delta_{X_a}}=M$ for all $M\in \M^G_{X_a}$ proving $F\circ \phi^\star$ is the identity map on $\M_{X_a}$.
\end{proof}

Given a $G$-invariant topological Markov field $Y \subset X$ there is always a linear map $F:\M^G_X\longrightarrow \M^G_Y$ given by $F(M)=M|_{\Delta_{Y}}$ and $F(\Gi^G_X)\subset \Gi^G_Y$. However if $Y$ cannot be obtained by a sequence of folds starting with $X$, then this map need not be surjective. Indeed, consider the following example:

Let $\H$ be the graph given by figure \ref{figure:safe_symbol}. Let $X=Hom(\Z^2, \H)$ and $Y=Hom(\Z^2,C_3)$. Since there is a graph embedding from the 3-cycle $C_3$ to $\H$ it follows that $Hom(\Z^2,C_3)\subset Hom(\Z^2,\H)$. Let $\sigma$ denote the group of translations of the $\Z^2$ lattice. Since the top vertex of $\H$ is a safe symbol for $Hom(\Z^2,\H)$ it follows from the strong Hammersley-Clifford theorem(theorem \ref{Theorem:Strong_Hammersley-Clifford}) that $\M^\sigma_X=\Gi^\sigma_X$. Therefore $F(\M^\sigma_X)\subset \Gi^\sigma_{Y}$. However by proposition 5.3 in \cite{chandgotiameyerovitch}, $\Gi^\sigma_Y\subsetneq\M^\sigma_Y$. It follows that $F(\M^\sigma_X)\subsetneq \M^\sigma_{Y}$.

\section{The Main Results}\label{section: main results}
\begin{thm}\label{thm:main theorem}
Let $\G=(\V, \E1)$ be a bipartite graph, $\A$ a finite alphabet and $X\subset \A^\V$ a Hammersley-Clifford n.n.constraint space . Then the folds and unfolds of $X$ are also Hammersley-Clifford.
\end{thm}

The $G$-invariant version of theorem \ref{thm:main theorem} holds as well.
\begin{thm}\label{thm:G-invariant main theorem}
Let $\G=(\V, \E1)$ be a bipartite graph, $\A$ a finite alphabet, $G\subset Aut(\G)$ a subgroup and $X\subset \A^\V$ a $G$-Hammersley-Clifford n.n.constraint space. Then the folds and unfolds of $X$ are also $G$-Hammersley-Clifford.
\end{thm}

We know that all frozen spaces of configurations are $G$-Hammersley-Clifford for all subgroups $G\subset Aut(\G)$. We can construct many more examples of Hammersley-Clifford spaces by using these theorems.

\begin{enumerate}

\item
N.N.Constraint space with a safe symbol.

By proposition \ref{prop:fold_generalise_fold} starting with an n.n.constraint space with a safe symbol $\star$ we can fold all the symbols one by one into the symbol $\star$ resulting in $\{\star\}^\V$ which is frozen. Thus these theorems generalise theorem \ref{Theorem:Strong_Hammersley-Clifford} in the case when $\G$ is a bipartite graph. Furthermore any configuration space which can be folded into a space with a safe symbol is still Hammersley-Clifford. For instance given the graph $\H^\prime$ in figure \ref{figure:fold_to_safe}, even though $Hom(\G, \H^\prime)$ does not have any safe symbol, it is $G$-Hammersley-Clifford for any subgroup $G\subset Aut(\G)$.


\item
$Hom(\G,Edge)$ where $Edge$ consists of two vertices $0$ and $1$ connected by a single edge.

By these theorems a configuration space which can be folded into $Hom(\G,Edge)$ is still Hammersley-Clifford. For example if $\H$ is the graph given by figure \ref{figure:foldtoedge}
\begin{figure}[h]
\includegraphics[angle=0,
width=.2\textwidth]{foldtoedge.pdf}
\caption{A graph which folds to the Edge graph \label{figure:foldtoedge}}
\end{figure}
then it can be folded to the graph $Edge$ and hence $Hom(\G, \H)$ is $G$-Hammersley-Clifford for any subgroup $G\subset Aut(\G)$.
\item
%Grayscale discrete images can be considered as graph homomorphisms from $\Z^2$ to colours graded $1$ to $n$ where $1$ represents the colour white and $n$ the colour black. Further, adjacent colours must be `close' to each other in the sense that if $v,w\in \Z^2$ are adjacent then for a discrete image $x$, $|x_v-x_w|\leq m$ where $m<<n$. Thus the space of grayscale discrete images can be considered as a space of
Consider the space $Hom(\G, \H_{n,m})$ where $\H_{n,m}$ is a graph with vertices $\V_{\H_{n,m}}=\{1, 2, \ldots, n\}$ and edges given by $(i,j)\in \E1_{\H_{n,m}}$ if and only if $|i-j|\leq m$.\\
\begin{figure}[h]
\includegraphics[angle=0,
width=.4\textwidth]{H92.pdf}
\caption{$\H_{9,2}$}
\end{figure}
%Image processing assumes an MRF on the space $Hom(\Z^2, \H_{n,m})$. For practical applications it is of interest to determine conditions under which it is Gibbs with some nearest neighbour interaction.

The sequence of folds $1$ to $2$, $2$ to $3$, $3$ to $4$, \ldots, $n-1$ to $n$ yields the space $\{n\}^{\G}$ from $Hom(\G, \H_{n,m})$ proving that it is $G$-Hammersley-Clifford for any subgroup $G\subset Aut(\G)$. A graph $\H$ is called \emph{dismantlable} if there exists a sequence of folds on the graph leading to a single vertex. By these theorems, if $\H$ is dismantlable then $Hom(\G, \H_{n,m})$ is $G$-Hammersley-Clifford for any subgroup  $G\subset Aut(\G)$.

\end{enumerate}

Note that although these are homomorphism spaces, the theorems are true in the general setting of configuration spaces. These specific examples have been chosen for convenience.

\subsection{A Concrete Example:}\label{subsection:concrete}
We will first work out the following example to illustrate the key ideas of the proof. 

Suppose $\H$ and $\H^\prime$ are graphs given by figure \ref{figure:Hprime}.
\begin{figure}[h]
\includegraphics[angle=0,
width=.4\textwidth]{concretegraph.pdf}
\caption{Graphs $\H$ and $\H^\prime$\label{figure:Hprime}}
\end{figure}
Let $X= Hom(\Z^2, \H)$. Then by folding the vertex $a$ into the vertex $b$ we obtain the space $X_a=Hom(\Z^2, \H^\prime)$.

Note that $X$ does not have any safe symbol but $b$ is a safe symbol for $X_a$. Let $\sigma\subset Aut(\Z^2)$ denote the subgroup of all translations of $\Z^2$. By the strong Hammersley-Clifford theorem(theorem \ref{Theorem:Strong_Hammersley-Clifford}) $X_a$ is $\sigma$-Hammersley-Clifford. We will prove that $X$ is $\sigma$-Hammersley-Clifford.

Let $M\in \M^\sigma_X$ be a $\sigma$-invariant Gibbs cocycle. Then $M|_{\Delta_{X_a}}$ is a $\sigma$-invariant Markov cocycle on $X_a$ and hence a Gibbs cocycle with some $\sigma$-invariant nearest neighbour interaction, which we will call $V$.

For $e, f,g, h, i\in \V_\H$ and $v\in \Z^2$ consider the configuration $x= \left[\begin{smallmatrix}&e&\\f&g&h\\&i&\end{smallmatrix}\right]^v$ given by
$$x_u=\begin{cases}
g\text{ if }u=v\\
e\text{ if }u=v+(0,1)\\
f\text{ if }u=v-(1,0)\\
h\text{ if }u=v+(1,0)\\
i\text{ if }u=v-(0,1)\\
b\text{ if }u\in D_1(v)^c.
\end{cases}$$
For all $v\in \Z^2$ let $x^v= \left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v$. Consider a $\sigma$-invariant nearest neighbour interaction $V^\prime$ as follows:
\begin{enumerate}
\item If $v \sim w \in \Z^2$, $[e,f]_{\{v,w\}}\in \B_{\{v,w\}}(X_a)$ then
\begin{eqnarray}
V^\prime([e,f]_{\{v,w\}})&=&V([e,f]_{\{v,w\}})\text{ and}\nonumber\\
V^\prime([e]_v)&=&V([e]_v).\label{equation:1_concrete_interaction}
\end{eqnarray}•
\item
The interaction between $a$ and $d$ is $0$, that is, for all $v \sim w \in \Z^2$
\begin{eqnarray}
V^\prime([a,d]_{\{v,w\}})=0.\label{equation:2_concrete_interaction}
\end{eqnarray}•
\item
The single site interaction for $[a]_v$ for all $v\in\Z^2$ is given by
\begin{eqnarray*}
V^\prime([a]_v)&=&M\left( \left[\begin{smallmatrix}&d&\\d&b&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right)+V([b]_v)+V([b,d]_{\{v,v+(1,0)\}})+V([b,d]_{\{v,v-(1,0)\}})\\
&&+V([b,d]_{\{v,v+(0,1)\}})+V([b,d]_{\{v,v-(0,1)\}}).
\end{eqnarray*}
By equations \ref{equation:1_concrete_interaction} and \ref{equation:2_concrete_interaction} this implies that the pair $ \left(\left[\begin{smallmatrix}&d&\\d&b&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right)$ is $V^\prime$-good.
\item
Let
\begin{eqnarray*}
V^\prime([a,c]_{\{v, v+(1,0)\}})&=&M\left( \left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&d&\\d&a&c\\&d&\end{smallmatrix}\right]^v\right)+V([d]_{v+(1,0)})-V([c]_{v+(1,0)})\\
&&+V([d,b]_{\{v+(1,0), v+(1,1)\}})+V([d,b]_{\{v+(1,0), v+(2,0)\}})\\
&&+V([d,b]_{\{v+(1,0), v+(1,-1)\}})-V([c,b]_{\{v+(1,0), v+(1,1)\}})\\
&&-V([c,b]_{\{v+(1,0), v+(2,0)\}})-V([c,b]_{\{v+(1,0), v+(1,-1)\}}).
\end{eqnarray*}•
By equations \ref{equation:1_concrete_interaction} and \ref{equation:2_concrete_interaction} the previous equation implies that the pair $ \left(\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&d&\\d&a&c\\&d&\end{smallmatrix}\right]^v\right)$ is $V^\prime$-good. Similarly we can define $V^\prime([a,c]_{\{v,v-(1,0)\}})$, $V^\prime([a,c]_{\{v,v+(0,1)\}})$ and $V^\prime([a,c]_{\{v,v-(0,1)\}})$, the corresponding expressions of which will imply that the pairs $ \left(\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&d&\\c&a&d\\&d&\end{smallmatrix}\right]^v\right)$, \\$ \left(\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&c&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right)$, $ \left(\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v, \left[\begin{smallmatrix}&d&\\d&a&d\\&c&\end{smallmatrix}\right]^v\right)$
are $V^\prime$-good.
\end{enumerate}•


Since $V$ and $M$ are $\sigma$-invariant it follows that $V^\prime$ is also $\sigma$-invariant. We want to prove that $V^\prime$ is an interaction for $M$. Equivalently we want to prove that all asymptotic pairs are $V^\prime$-good. Let $(x,y)\in \Delta_X$. Since any appearance of $a$ in the elements of $X$ can be replaced by $b$, by replacing all the $a$'s outside the set of sites where $x$ and $y$ differ and its boundary we can obtain a pair $(x^1,y^1)\in \Delta_{X}$ which is Markov-similar to $(x,y)$ and has finitely many $a$'s. Thus by proposition \ref{prop:V-goodness_equivalence_markov_similar} it is sufficient to prove that pairs $(x,y)\in \Delta_X$ with finitely many $a$'s are $V^\prime$-good. Since the $a$'s can be replaced by $b$'s one by one and any pair in $\Delta_{X_a}$ is $V^\prime$-good by lemma \ref{corollary:chain_of_V-goodness} it is sufficient to prove that pairs in $X$ in which a single $a$ is replaced by $b$ are $V^\prime$-good. Since $a$ can be folded into $b$ and $\partial\{a\}=\{c,d\}$ any such pair is Markov-similar to a pair of the type $\left(\left[\begin{smallmatrix}&e&\\f&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&e&\\f&b&h\\&i&\end{smallmatrix}\right]^v\right)$ for some $v\in \Z^2$ and $e, f,g, h, i\in \{c,d\}$.

The pairs
$$\left(\left[\begin{smallmatrix}&e&\\f&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\f&a&h\\&i&\end{smallmatrix}\right]^v\right), \left(\left[\begin{smallmatrix}&d&\\f&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&h\\&i&\end{smallmatrix}\right]^v\right),\left(\left[\begin{smallmatrix}&d&\\d&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&i&\end{smallmatrix}\right]^v\right),\left(\left[\begin{smallmatrix}&d&\\d&a&d\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right)$$
are Markov-similar to
$$\left(\left[\begin{smallmatrix}&e&\\d&a&d\\&d&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right), \left(\left[\begin{smallmatrix}&d&\\f&a&d\\&d&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right),\left(\left[\begin{smallmatrix}&d&\\d&a&h\\&d&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right),\left(\left[\begin{smallmatrix}&d&\\d&a&d\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v\right)$$ 
respectively. Since $e, f,g, h, i\in \{c,d\}$, these pairs are $V^\prime$-good. Thus each adjacent pair in the chain
$$\left[\begin{smallmatrix}&e&\\f&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\f&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&d&\\d&a&d\\&d&\end{smallmatrix}\right]^v,
\left[\begin{smallmatrix}&d&\\d&b&d\\&d&\end{smallmatrix}\right]^v,
\left[\begin{smallmatrix}&e&\\f&b&h\\&i&\end{smallmatrix}\right]^v$$
is $V^\prime$-good. By corollary \ref{corollary:chain_of_V-goodness} the pair $\left(\left[\begin{smallmatrix}&e&\\f&a&h\\&i&\end{smallmatrix}\right]^v,\left[\begin{smallmatrix}&e&\\f&b&h\\&i&\end{smallmatrix}\right]^v\right)$ is $V^\prime$-good. This completes the proof.

\subsection{Proof of theorems \ref{thm:main theorem} and \ref{thm:G-invariant main theorem}}


We will now prove theorems \ref{thm:main theorem} and \ref{thm:G-invariant main theorem}. The proof will give an explicit way of computing the interaction as well. It should also be noted that theorem \ref{thm:main theorem} is a special case of theorem \ref{thm:G-invariant main theorem}. Yet we separate the proofs so as to separate the various complications.

\

\noindent\emph{Proof of theorem \ref{thm:main theorem}.} The bulk of the proof lies in showing that the unfolds of Hammersley-Clifford spaces are Hammersley-Clifford. We will first prove that the folds of a Hammersley-Clifford space are Hammersley-Clifford. Let $X\subset \A^\V$ be Hammersley-Clifford and $X_a$ be its fold. Using proposition \ref{proposition:induced_map_cocycles} in the case where $G=\{id|_\G\}$ we obtain a surjective map $F:\M_X\longrightarrow \M_{X_a}$ such that $F(\Gi_X)=\Gi_{X_a}$. Since $X$ is Hammersley-Clifford, $\M_X=\Gi_X$. Hence
$$\M_{X_a}=F(\M_X)=F(\Gi_X)=\Gi_{X_a}$$
proving that $X_a$ is Hammersley-Clifford.

Now we will prove that unfolds of Hammersley-Clifford spaces are Hammersley-Clifford spaces as well. Let $X\subset \A^\V$ be an n.n.constraint space and $X_a $ be a fold of $X$ where $a$ is folded into $b$. Let the set of nearest neighbour constraints of $X$ be given by the set $\F_X$. Suppose $X_a$ is Hammersley-Clifford.

Let $M\in \M_X$ be a Markov cocycle. Since $X_a$ is Hammersley-Clifford $M|_{\Delta_{X_a}}\in \Gi_{X_a}$. Let $V$ be a corresponding nearest neighbour interaction. We shall now construct a nearest neighbour interaction $V^\prime$ for $M$. The idea is the following:

Since we have a nearest neighbour interaction for $M|_{\Delta_{X_a}}$ we will change asymptotic pairs in $X$ to asymptotic pairs in $X_a$ using the fewest possible distinct single site changes. These distinct single site changes will correspond to patterns on edges and vertices helping us build $V^\prime$. If we use the single site changes which involve blindly changing the $a$'s into $b$'s we will incur a large number of such changes; instead we will use a smaller number as described by the following lemma. 


\begin{lemma}[Construction of special configurations]\label{lemma:four special configurations}
Let $X$ be an n.n.constraint space and $X_a$ be a fold of $X$ where the symbol $a$ is folded into the symbol $b$. Let
$$\V_1=\left\{v\in \V\:|\: \text{there exists } w\sim v\text{ such that }[a,a]_{\{v,w\}}\in \B_{\{v,w\}}(X)\right\}$$
and
$$\V_2=\left\{v\in \V\setminus \V_1\:|\: [a]_{\{v\}}\in \B_{\{v\}}(X)\right\}.$$
For all $v\in \V_1\cup\V_2$ there exists $x^v\in X$ such that
\begin{enumerate}
\item\label{enumerate:configuration1}
If $v\in \V_1$ then $x^v_v=a$ and $x^v|_{D_2(v)\setminus \{v\}}=b$.
\item\label{enumerate:configuration2}
If $v\in \V_2$ then $x^v_{v}=a$ and $x^v|_{\partial D_1(v)}=b$.
\end{enumerate}
Moreover $\theta^v_b(x^v)\in X_a$ and if $w_1, w_2, w_3,\ldots w_r\sim v$ and $c_1, c_2,\ldots,c_r\in\A$ such that $[a,c_i]_{\{v,w_i\}}\in \B_{\{v,w_i\}}(X)$ then $\theta^{w_1, w_2, \ldots, w_r}_{c_1, c_2,\ldots, c_r}(x^v)\in X$.
\end{lemma}
\begin{proof}
Let $v\in \V_1$. By equation \ref{equation:foldingdefn2} $[a,b]_{\{v,w\}}\in \B_{\{v,w\}}(X)$ for all $w\sim v$. Again by equation \ref{equation:foldingdefn2} it follows that $[b,b]_{\{w, w_1\}}\in \B_{\{w, w_1\}}(X)$ for all $w, w_1\in \V$ such that $w\sim v$ and $w_1\sim w$. Then none of the patterns from $\F_X$, the nearest neighbour constraint set for $X$ appear in $\alpha^v\in\A^{D_2(v)}$ given by
\begin{equation*}
\alpha^v_u=\begin{cases}
a &\text{ if }u=v\\
b &\text{ if }u \in D_2(v)\setminus\{v\}.
\end{cases}•
\end{equation*}
For $v\in \V_2$ there exists $x^1\in X$ such that $x^1_v=a$. For all $w, w_1\in \V$ such that $w\sim v$ and $w_1\sim w$ equation \ref{equation:foldingdefn2} implies that $[x^1_w,b]_{\{w,w_1\}}\in \B_{\{w,w_1\}}(X)$. Then none of the patterns from $\F_X$ appear in $\alpha^v\in \A^{D_2(v)}$ given by
\begin{equation*}
\alpha^v_u=\begin{cases}
x^1_u&\text{ if } u\in D_1(v)\\
b&\text{ if } u\in D_2(v)\setminus D_1(v).
\end{cases}•
\end{equation*}•

Fix $v\in \V_1\cup \V_2$. By equation \ref{equation:foldingdefn3} there exists $x\in X$ such that $x|_{\partial D_1(v)}=b$. Moreover since $a$ folds into $b$ we can assume that $x\in X_a$. Consider $x^v\in \A^\V$ given by
\begin{eqnarray*}
x^v_u=\begin{cases}
\alpha^v_u \text{ if }u\in D_2(v)\\
x_u\text{ if } u \in D_1(v)^c.
\end{cases}•
\end{eqnarray*}•
The configurations $x^v$ satisfy the conclusions (\ref{enumerate:configuration1}) and (\ref{enumerate:configuration2}) of this lemma. Since each edge in $\G$ either lies completely in $D_2(v)$ or in $D_1(v)^c$, no subpattern of $x^v$ belongs to $\F_X$. Therefore $x^v\in X$.

Let $v\in \V_1\cup \V_2$. Since $x\in X_a$, $a$ appears in $x^v$ only at $v$ . Moreover since $a$ folds into $b$ by equation \ref{equation:foldingdefn1}, $\theta^v_b(x^v)\in X_a$. Let $w_1, w_2, w_3,\ldots w_r\sim v$ and $c_1, c_2,\ldots,c_r\in\A$ such that $[a,c_i]_{\{v,w_i\}}\in \B_{\{v,w_i\}}(X)$ for all $1\leq i \leq r$. Because the graph is bipartite $w_i\nsim w_j$ for all $1\leq i, j \leq r$. By equation \ref{equation:foldingdefn2} for all $w^\prime\sim w_i$ and $1\leq i \leq r$, $[c_i,b]_{\{w_i,w^\p\}}\in \B_{\{w_i, w^\p\}}(X)$. By proposition \ref{prop:changing_remain_nnconstraint} $\theta^{w_1, w_2, \ldots, w_r}_{c_1, c_2, \ldots, c_r}(x^v)\in X$.
\end{proof}

We will now construct an interaction via the following technical lemma.

\begin{lemma}[Construction of $V^\prime$]\label{lemma:construction_of_V^prime}
Let $X$ be an n.n.constraint space and $X_a$ be a fold of $X$ where the symbol $a$ is folded into the symbol $b$. Consider sets $\V_1, \V_2\subset \V$ and for all $v\in \V_1\cup \V_2$, configurations $x^v\in X$ satisfying the conclusions of lemma \ref{lemma:four special configurations}. Let $M\in \M_X$ be a Markov cocycle on $X$ such that $M|_{\Delta_{X_a}}$ is a Gibbs cocycle with interaction $V$. Then there exists a unique nearest neighbour interaction $V^\prime$ on $X$ which satisfies:

\noindent If $v\sim w\in \V$ and $[c,d]_{\{v,w\}}\in \B_{\{v,w\}}(X_a)$ then
\begin{eqnarray}
V^\prime([c,d]_{\{v,w\}})&=& V([c,d]_{\{v,w\}})\text{ and}\label{equation:listinteract1}\\
V^\prime([c])_{\{v\}}&=&V([c]_{\{v\}}).\label{equation}\label{equation:listinteract2}
\end{eqnarray}
For $v\in \V_1\cup \V_2$ and $w\sim v$
\begin{eqnarray}
V^\prime([x^v]_{\{v,w\}})=0.\label{equation:listinteract3}
\end{eqnarray}
such that the following pairs are $V^\prime$-good:
\begin{enumerate}
\item
$(\tilde{x},\tilde{y}) \in \Delta_{X_a}$.
\label{item:from_X_a}
\item
$(\theta^v_b(x^v), x^v)$ for $v\in \V_1\cup \V_2$.
\label{item:changing_b_at_v}
\item
$ \left(\theta^w_c(x^v),x^v\right)$ for $v\in \V_1\cup \V_2$, $w\sim v$ and $c\in \A\setminus\{a\}$ satisfying $[a,c]_{\{v,w\}}\in \B_{\{v,w\}}(X)$.
\label{item:changing_at_boundary_no_a}
\item
$ (\theta^w_a(x^v),x^v)$ for all $v\in \V_1\cap P_1$, $w\sim v$ satisfying $[a,a]_{\{v,w\}}\in \B_{\{v,w\}}(X)$.
\label{item:changing_at_boundary_a}
\end{enumerate}
\end{lemma}

In the following proof the reader is encouraged to refer to the statement of lemma \ref{lemma:four special configurations} for information about configurations $x^v$.
\begin{proof}[Proof of lemma \ref{lemma:construction_of_V^prime}]
We will begin by proving uniqueness of the interaction assuming its existence. Consider a nearest neighbour interaction $V^\prime$ on $X$ which satisfies the conclusion of this lemma. We will prove the uniqueness by expressing $V^\prime$ in terms of the cocycle $M$ and $V$.

Since $V^\prime$ satisfies equations \ref{equation:listinteract1}, \ref{equation:listinteract2} and \ref{equation:listinteract3} we have to prove that the following can be expressed in terms of $M$ and $V$:
\begin{enumerate}[(a)]
\item For all $v\in \V_1\cup\V_2$, the value $V^\prime([a]_v)$,\label{item:the_single_a_at centre}
\item For all $v\in \V_1\cup\V_2$, $w\sim v$ and $c\in \A\setminus \{x^v_w,a\}$ such that $[a,c]_{\{v,w\}}\in \B_{\{v,w\}}(X)$, the value $V^\prime([a,c]_{\{v,w\}})$ and \label{item:a_at_centre_not_a_at_boundary}
\item For all $v\in \V_1\cap P_1$, $w\sim v$ such that $[a,a]_{\{v,w\}}\in\B_{\{v,w\}}(X)$, the value $V^\prime([a,a]_{\{v,w\}})$.\label{item:a_at_both}
\end{enumerate}

\noindent\emph{Proof for part (\ref{item:the_single_a_at centre}):} Let $v\in \V_1\cup\V_2$. Since the pair $(\theta^v_b(x^v),x^v)$ ((\ref{item:changing_b_at_v}) in the statement of the lemma) is $V^\prime$-good by rearranging the expression for $M(\theta^v_b(x^v),x^v)$ we get that
\begin{eqnarray}
V^\prime([a]_v)&=&V^\prime([x^v]_v)\nonumber\\
&=&M(\theta^v_b(x^v), x^v)+ V^\prime([\theta^v_b(x^v)]_v)+\sum_{w: w\sim v} V^\prime\left([\theta^v_b(x^v)]_{\{v,w\}}\right)\nonumber\\
&&-(\sum_{w: w\sim v} V^\prime\left([x^v]_{\{v,w\}}\right))\label{equation:listsimilargood1}.
\end{eqnarray}
Now we will express the right hand side of this expression in terms of $M$ and $V$. Since $\theta^v_b(x^v)\in X_a$ $V^\prime([\theta^v_b(x^v)]_{\{v,w\}})=V([\theta^v_b(x^v)]_{\{v,w\}})$ and $V^\prime([\theta^v_b(x^v)]_v)=V([\theta^v_b(x^v)]_v)$. By equation \ref{equation:listinteract3}, $V^\prime([x^v]_{\{v,w\}})=0$.

Putting all this together we get
\begin{eqnarray}
V^\prime([a]_v)&=&M(\theta^v_b(x^v), x^v)+ V([\theta^v_b(x^v)]_v)+\sum_{w: w\sim v} V([\theta^v_b(x^v)]_{\{v,w\}}).\label{equation:listinteract4}
\end{eqnarray}

\noindent\emph{Proof for part (\ref{item:a_at_centre_not_a_at_boundary}): }Consider $v\in \V_1\cup \V_2$, $w\sim v$ and $c\in \A\setminus\{a, x^v_w\}$ such that $[a,c]_{\{v,w\}}\in \B_{\{v,w\}}(X)$. Since the pair $(\theta^w_c(x^v),x^v)$ ((\ref{item:changing_at_boundary_no_a}) in the statement of the lemma) is $V^\prime$-good by rearranging the expression for $M(x^v, \theta^w_c(x^v))$ we get
\begin{eqnarray}
V^\prime([a,c]_{\{v,w\}})&=&V^\prime([\theta^w_c(x^v)]_{\{v,w\}})\nonumber\\
&=&M(x^v, \theta^w_c(x^v))+\sum_{w^\prime: w^\prime\sim w}V^\prime([x^v]_{\{w^\prime,w\}}) +V^\prime([x^v]_w)\nonumber\\
&&-\left(\sum_{w^\prime: w^\prime\sim w, w^\prime\neq v}V^\prime([\theta^w_c(x^v)]_{\{w^\prime,w\}})\right)-V^\prime([\theta^w_c(x^v)]_w)\label{equation:listsimilargood2}.
\end{eqnarray}•
We will now express the right hand side of this expression in terms of $M$ and $V$.

By equation \ref{equation:listinteract3}, $V^\prime([x^v]_{\{v,w\}})=0$. We know that $(\theta^w_c(x^v))_{w},\  x^v_w\neq a$ and if $w^\prime\sim w$, $w^\prime\neq v$ then $w^\prime\in \partial D_1(v)$ and so $(\theta^w_c(x^v))_{w^\prime}=x^v_{w^\prime}=b$. Therefore by equations \ref{equation:listinteract1} and \ref{equation:listinteract2} 
$$V^\prime([x^v]_{\{w^\prime,w\}})=V([x^v]_{\{w^\prime,w\}}),\ V^\prime([\theta^w_c(x^v)]_{\{w^\prime, w\}})=V([\theta^w_c(x^v)]_{\{w^\prime, w\}})$$
and
$$V^\prime([x^v]_w)=V([x^v]_w),\ V^\prime([\theta^w_c(x^v)]_w)=V([\theta^w_c(x^v)]_{w}).$$

Putting all this together we get
\begin{eqnarray}
V^\prime([a,c]_{\{v,w\}})&=&M(x^v, \theta^w_c(x^v))+\displaystyle{\sum_{w^\prime: w^\prime\sim w, w^\prime\neq v}\left( V([x^v]_{\{w^\prime,w\}})-V([\theta^w_c(x^v)]_{\{w^\prime,w\}}) \right) }\nonumber\\
&&+V([x^v]_w)-V([\theta^w_c(x^v)]_w).\label{equation:listinteract5}
\end{eqnarray}•

\noindent\emph{Proof for part (\ref{item:a_at_both}):} Consider $v\in \V_1\cap P_1$ and $w\sim v$ such that $[a,a]_{\{v,w\}}\in \B_{\{v,w\}}(X)$. Since the pair $(\theta^w_a(x^v),x^v)$ ((\ref{item:changing_at_boundary_a}) in the statement of the lemma) is $V^\prime$-good by rearranging the expression for $M(x^v, \theta^w_a(x^v))$ we get that
\begin{eqnarray}
V^\prime([a,a]_{\{v,w\}})&=&V^\prime([\theta^w_a(x^v)]_{\{v,w\}})\nonumber\\
&=&M(x^v, \theta^w_a(x^v))+\sum_{w^\prime: w^\prime\sim w}V^\prime([x^v]_{\{w^\prime,w\}}) +V^\prime([x^v]_w)\nonumber\\
&&-\left(\sum_{w^\prime: w^\prime\sim w, w^\prime\neq v}V^\prime([\theta^w_a(x^v)]_{\{w^\prime,w\}})\right)-V^\prime([\theta^w_a(x^v)]_w).\label{equation:listsimilargood3}
\end{eqnarray}•
We will now express the right hand side of this expression in terms of $M$ and $V$. By equation \ref{equation:listinteract3}, $V^\prime([x^v]_{\{v,w\}})=0$. Since $v\in \V_1$, for $w^\prime\sim w$ such that $w^\prime\neq v$ we know that $x^v_w=x^v_{w^\prime}=b\neq a$. Therefore by equations \ref{equation:listinteract1} and \ref{equation:listinteract2} $$V^\prime([x^v]_{\{w^\prime,w\}})=V([x^v]_{\{w^\prime,w\}})$$
and
$$V^\prime([x^v]_w)=V([x^v]_w).$$
Since $[a,a]\in\B_{\{v,w\}}(X)$ therefore $v,w\in \V_1$ and $x^v_{w^\prime}=x^w_{w^\prime}=b$ for all $w^\prime\sim w$, $w^\prime\neq v$. Then by equation \ref{equation:listinteract3}
\begin{eqnarray*}
V^\prime([\theta^w_a(x^v)]_{\{w^\prime,w\}})= V^\prime([b,a]_{\{w^\prime,w\}})=V^\prime([x^w]_{\{w^\prime,w\}})=0.
\end{eqnarray*}
By equation \ref{equation:listinteract4} we get that
$$V^\prime([\theta^w_a(x^v)]_{w})=V^\prime([a]_{w})=M(\theta^w_b(x^w), x^w)+ V([\theta^w_b(x^w)]_w)+\sum_{w^\prime: w^\prime\sim w} V([\theta^w_b(x^w)]_{\{w,w^\prime\}}).$$
Putting all this together, we get
\begin{eqnarray}
V^\prime([a,a]_{\{v,w\}})&=&M(x^v, \theta^w_a(x^v))+\displaystyle{\sum_{w^\prime: w^\prime\sim w, w^\prime\neq v}V([x^v]_{\{w^\prime,w\}}) }+V([x^v]_w)-M(\theta^w_b(x^w), x^w)\nonumber\\
&&- V([\theta^w_b(x^w)]_w)-(\sum_{w^\prime: w^\prime\sim w} V([\theta^w_b(x^w)]_{\{w,w^\prime\}})).\label{equation:listinteract6}
\end{eqnarray}

This completes proof for uniqueness. It follows from the proofs that given an interaction $V^\prime$ which satisfies equations \ref{equation:listinteract1}, \ref{equation:listinteract2} and \ref{equation:listinteract3}, the equations \ref{equation:listinteract4}, \ref{equation:listinteract5} and \ref{equation:listinteract6} are satisfied if and only if the pairs listed in (\ref{item:from_X_a}), (\ref{item:changing_b_at_v}), (\ref{item:changing_at_boundary_no_a}) and (\ref{item:changing_at_boundary_a}) are $V^\prime$-good.\\



Consider a nearest neighbour interaction $V^\prime$ on $X$ given by the following:
\begin{enumerate}[(i)]
\item If $v\sim w\in \V$ and $[c,d]_{\{v,w\}}\in\B_{\{v,w\}}(X_a)$ then $V^\prime([c,d]_{v,w})$ is given by equation \ref{equation:listinteract1}
\item and $V^\prime([c]_v)$ is given by equation \ref{equation:listinteract2}.
\item If $v\in \V_1\cup \V_2$ and $w\sim v$, then $V^\prime([x^v]_{\{v,w\}})$ is given by equation \ref{equation:listinteract3}.
\item If $v\in \V_1\cup \V_2$, the value $V^\prime([a]_v)$ is given by equation \ref{equation:listinteract4}.
\item If $v\in \V_1\cup \V_2$, $w\sim v$ and $c\in \A\setminus \{x^v_w,a\}$ such that $[a,c]_{\{v,w\}}\in \B_{\{v,w\}}(X)$, the value $V^\prime([a,c]_{\{v,w\}})$ is given by equation \ref{equation:listinteract5}.
\item If $v\in \V_1\cap P_1$, $w\sim v$ such that $[a,a]_{\{v,w\}}\in \B_{\{v,w\}}(X)$, the value $V^\prime([a,a]_{\{v,w\}})$ is given by equation \ref{equation:listinteract6}.
\end{enumerate}•
By the preceding paragraph the proof is complete.
\end{proof}

Now we will reap the benefits of the previous lemma. The following lemma explains why the weak conclusions of lemma \ref{lemma:construction_of_V^prime} are sufficient and completes the proof of theorem \ref{thm:main theorem}.

\begin{lemma}\label{lemma:from_particular_pairs_to_all_pairs}
Let $X$ be an n.n.constraint space and $X_a$ be a fold of $X$ where the symbol $a$ is folded into the symbol $b$. Let $P_1, P_2$ be the partite classes of $\V$ and consider $\V_1, \V_2\subset \V$ and $x^v\in X$ for all $v\in \V_1\cup \V_2$ satisfying the conclusion of lemma \ref{lemma:four special configurations}. Let $M\in \M_X$ be a Markov cocycle on $X$ such that $M|_{\Delta_{X_a}}$ is a Gibbs cocycle with some nearest neighbour interaction $V$ and $V^\prime$ be an interaction on $X$ as obtained in lemma \ref{lemma:construction_of_V^prime}. Then $M\in \Gi_X$ is Gibbs with nearest neighbour interaction $V^\prime$.
\end{lemma}
\begin{proof}
We will use the $V^\prime$-good pairs guaranteed by lemma \ref{lemma:construction_of_V^prime} as steps in proving the following pairs are $V^\prime$-good:
\begin{enumerate}[(a)]
\item Let $x\in X$ and $v\in \V_1\cup \V_2$ such that $x_v=a$ and $x_w\neq a$ for all $w\sim v$. Then $(x, \theta^v_b(x))$ is $V^\prime$-good.
\label{item:nearby_not_a}
\item Let $x\in X$ and $v\in \V_1\cap P_1$ and $w\sim v$ such that $x_v=x_w=a$. Then $(x, \theta^v_b(x))$ is $V^\prime$-good. \label{item:nearby_is_a}
\item All asymptotic pairs $(x,y)\in \Delta_X$ are $V^\prime$-good.
\label{item:no_constraint}
\end{enumerate}
Given an asymptotic pair, statements (\ref{item:nearby_not_a}) and (\ref{item:nearby_is_a}) allow replacement of the $a$'s by $b$'s giving us a pair in $\Delta_{X_a}$. From conclusion (\ref{item:from_X_a}) in lemma \ref{lemma:construction_of_V^prime} we know that all pairs in $\Delta_{X_a}$ are $V^\prime$-good. Since the relation $V^\prime$-good is an equivalence relation this proves statement (\ref{item:no_constraint}) thereby completing the proof.

Consider any $v\in \V_1\cup \V_2$ and $x\in X$ such that $x_v=a$. Let
\begin{equation*}
\partial\{v\}=\{w_1, w_2, \ldots w_n\}.
\end{equation*}
Since for all $1\leq r\leq n$, $[a,x_{w_r}]_{\{v,w_r\}}\in \B_{\{v,w_r\}}(X)$, lemma \ref{lemma:four special configurations} implies that
$$\theta^{w_r,w_{r+1} \ldots, w_n}_{x_{w_r},x_{w_{r+1}},\ldots,x_{w_n}}(x^v)\in X. $$
Let $x^1=\theta^{w_1, w_2, \ldots, w_n}_{x_{w_1},x_{w_2},\ldots,x_{w_n}}(x^v)$. The pair $(x,\theta^v_b(x))$ is Markov-similar to $(x^1, \theta^v_b(x^1))$ with $A=\{v\}$. Note
$$\theta^{w_1, w_2, \ldots, w_{r}}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_{r}}}(x^1)=\theta^{w_{r+1} \ldots, w_n}_{x_{w_{r+1}},\ldots,x_{w_n}}(x^v)\in X$$
and that $x^1$ and $x^v$ differ only on $\partial\{v\}$. \\

In the following we will remove $a$'s in configurations from those vertices which are isolated from other $a$'s.

\noindent\emph{Proof of statement (\ref{item:nearby_not_a}):} Consider the sequence
\begin{eqnarray*}
x^1,\theta^{w_1}_{x^v_{w_1}}(x^1),\theta^{w_1,w_2}_{x^v_{w_1},x^v_{w_2}}(x^1), \ldots, \theta^{w_1, w_2, \ldots, w_n}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_n}}(x^1)=x^v,\theta^v_b(x^v),\theta^v_b(x^1).
\end{eqnarray*}
Here single site changes have been made on $\partial \{v\}$ taking us from $x^1$ to $x^v$. Then the symbol at $v$ has been changed to obtain $\theta^v_b(x^v)$. In the last step $\theta^v_b(x^v)$ has been changed on $\partial \{v\}$ to obtain $\theta^v_b(x^1)$.

Note that each
$$(\theta^{w_1, w_2, \ldots, w_r}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_r}}(x^1),\theta^{w_1, w_2, \ldots, w_{r+1}}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_{r+1}}}(x^1))$$
is Markov-similar to $(\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(x^v),x^v)$ for all $0\leq r\leq n-1$ with $A=\{w_{r+1}\}$. By conclusion (\ref{item:changing_at_boundary_no_a}) in lemma \ref{lemma:construction_of_V^prime}, $(\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(x^v),x^v)$ is $V^\prime$-good for all $0\leq r\leq n-1$. Thus by corollary \ref{corollary:chain_of_V-goodness}, we get that $(x^1,x^v)$ is $V^\prime$-good. By conclusion (\ref{item:changing_b_at_v}) in lemma \ref{lemma:construction_of_V^prime} and symmetry of the relation $V^\prime$-good we get that $(x^v,\theta^v_b(x^v))$ is $V^\prime$-good. Since $\theta^v_b(x^v),\theta^v_b(x^1)\in X_a$, conclusion (\ref{item:from_X_a}) in lemma \ref{lemma:construction_of_V^prime} implies that $(\theta^v_b(x^v),\theta^v_b(x^1))$ is $V^\prime$-good. Stringing these together by corollary \ref{corollary:chain_of_V-goodness} we arrive at $(x^1, \theta^v_b(x^1))$ being $V^\prime$-good. But $(x^1, \theta^v_b(x^1))$ is Markov-similar to $(x,\theta^v_b(x))$. Therefore by proposition \ref{prop:V-goodness_equivalence_markov_similar} we get that $(x,\theta^v_b(x))$ is $V^\prime$-good.
\bigskip

In the next step we remove the $a$'s which are not isolated.

\noindent\emph{Proof of statement (\ref{item:nearby_is_a}):} We construct a sequence from $x$ to $\theta^v_b(x)$ in three parts. In the first part single site changes will be made on $\partial \{v\}$ taking us from $x^1$ to $x^v$. In the second part the symbol at $v$ will be changed to obtain $\theta^v_b(x^v)$. In the last part single site changes will be made on $\partial \{v\}$ to obtain $\theta^v_b(x^1)$ from $\theta^v_b(x^v)$.

Consider the sequence
\begin{gather*}
(x^1,\theta^{w_1}_{x^v_{w_1}}(x^1),\theta^{w_1,w_2}_{x^v_{w_1},x^v_{w_2}}(x^1), \ldots, \theta^{w_1, w_2, \ldots, w_n}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_n}}(x^1)=x^v),\\
(x^v,\theta^v_b(x^v)),\\
(\theta^v_b(x^v),\theta^{w_1}_{x^1_{w_1}}(\theta^v_b(x^v)),\theta^{w_1,w_2}_{x^1_{w_1},x^1_{w_2}}(\theta^v_b(x^v)), \ldots, \theta^{w_1, w_2, \ldots, w_n}_{x^{1}_{w_1},x^{1}_{w_2},\ldots,x^{1}_{w_n}}(\theta^v_b(x^v))=\theta^v_b(x^1)).
\end{gather*}

In the first part of the sequence notice that
$$(\theta^{w_1, w_2, \ldots, w_r}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_r}}(x^1),\theta^{w_1, w_2, \ldots, w_{r+1}}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_{r+1}}}(x^1))$$
is Markov-similar to $(\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(x^v),x^v)$ for all $0\leq r\leq n-1$ with $A=\{ w_{r+1}\}$. If for some $0\leq r\leq n-1$, $x^1_{w_{r+1}}\neq a$ then by conclusion (\ref{item:changing_at_boundary_no_a}) in lemma \ref{lemma:construction_of_V^prime} we get that $(\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(x^v),x^v)$ is $V^\prime$-good. If for some $0\leq r\leq n-1$, $x^1_{w_{r+1}}= a$ then by conclusion (\ref{item:changing_at_boundary_a}) in lemma \ref{lemma:construction_of_V^prime} we get that $(\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(x^v),x^v)$ is $V^\prime$-good. Proposition \ref{prop:V-goodness_equivalence_markov_similar} implies that
$$(\theta^{w_1, w_2, \ldots, w_r}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_r}}(x^1),\theta^{w_1, w_2, \ldots, w_{r+1}}_{x^{v}_{w_1},x^{v}_{w_2},\ldots,x^{v}_{w_{r+1}}}(x^1))$$
is $V^\prime$-good for all $0\leq r\leq n-1$. By corollary \ref{corollary:chain_of_V-goodness}, we get that $(x^1,x^v)$ is $V^\prime$-good and we are done with the first part of the sequence.

For the second part of the sequence by conclusion (\ref{item:changing_b_at_v}) in lemma \ref{lemma:construction_of_V^prime} and symmetry of the relation $V^\prime$-good we get that $(x^v,\theta^v_b(x^v))$ is $V^\prime$-good.

For the third part of the sequence the asymptotic pair
$$(\theta^{w_1, w_2, \ldots, w_r}_{x^{1}_{w_1},x^{1}_{w_2},\ldots,x^{1}_{w_r}}(\theta^v_b(x^v)),\theta^{w_1, w_2, \ldots, w_{r+1}}_{x^{1}_{w_1},x^{1}_{w_2},\ldots,x^{1}_{w_{r+1}}}(\theta^v_b(x^v)))$$
is Markov-similar to $(\theta^v_b(x^v),\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(\theta^v_b(x^v)))$ for all $0\leq r\leq n-1$ with $A=\{ w_{r+1}\}$.

If for some $0\leq r\leq n-1$, $x^1_{w_{r+1}}\neq a$ then $(\theta^v_b(x^v),\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(\theta^v_b(x^v))\in X_a$ and by conclusion (\ref{item:from_X_a}) in lemma \ref{lemma:construction_of_V^prime} we get that $(\theta^v_b(x^v),\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(\theta^v_b(x^v)))$ is $V^\prime$-good. Since $v\in \V_1$, $x^v|_{D_2(v)\setminus\{v\}}=b$. Thus if for some $0\leq r\leq n-1$, $x^1_{w_{r+1}}=a$ then
$$(\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(\theta^v_b(x^v)),\theta^v_b(x^v))=(\theta^{w_{r+1}}_{a}(\theta^v_b(x^v)),\theta^{w_{r+1}}_b(\theta^{w_{r+1}}_{a}(\theta^v_b(x^v)))$$
and $(\theta^{w_{r+1}}_{a}(\theta^v_b(x^v)))_{w^\prime}=b\neq a$ for all $w^\prime\sim w_{r+1}$. By statement (\ref{item:nearby_not_a}) in the proof of this lemma we get that $(\theta^{w_{r+1}}_{a}(\theta^v_b(x^v)),\theta^{w_{r+1}}_b(\theta^{w_{r+1}}_{a}(\theta^v_b(x^v)))$ is $V^\prime$-good. By symmetry of the relation $V^\prime$-good we get that $(\theta^v_b(x^v),\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(\theta^v_b(x^v)))$ is $V^\prime$-good in this case as well.

Thus for all $0\leq r \leq n-1$ we find that $(\theta^v_b(x^v),\theta^{w_{r+1}}_{x^1_{w_{r+1}}}(\theta^v_b(x^v)))$ is $V^\prime$-good. Using Corollary \ref{corollary:chain_of_V-goodness} we find that $(\theta^v_b(x^v), \theta^v_b(x^1))$ is $V^\prime$-good.

So we have proven that $(x^1, x^v), (x^v, \theta^v_b(x^v)), (\theta^v_b(x^v), \theta^v_b(x^1))$ are $V^\prime$-good. Stringing them by corollary \ref{corollary:chain_of_V-goodness} we get that $(x^1,\theta^v_b(x^1))$ is $V^\prime$-good. But $(x^1, \theta^v_b(x^1))$ is Markov-similar to $(x,\theta^v_b(x))$. Therefore by proposition \ref{prop:V-goodness_equivalence_markov_similar} we get that $(x,\theta^v_b(x))$ is $V^\prime$-good.\\

The previous two statements give us the freedom to change the $a$'s into $b$'s. Now we will use them to prove the last statement.

\noindent\emph{Proof of statement (\ref{item:no_constraint}):} Consider an asymptotic pair $(x,y)\in \Delta_X$. Let
$$F=\{v\in \V\:|\:x_v\neq y_v\}$$
and $x^1, y^1\in \A^\V$ be obtained by replacing the $a$'s outside $F\cup \partial F$ by $b$'s, that is
$$x^1_u=\begin{cases}
x_u\text{ if }u \in F\cup\partial F \text{ or }x_u\neq a\\
b\ \ \text{ otherwise}
\end{cases}•$$
and
$$y^1_u=\begin{cases}
y_u\text{ if }u \in F\cup\partial F \text{ or }y_u\neq a\\
b\ \ \text{ otherwise}.
\end{cases}•$$
By equation \ref{equation:foldingdefn1} $x^1, y^1\in X$. Since $x=y$ on $F^c$, it follows that $(x,y)$ and $(x^1, y^1)$ are Markov-similar but there are only finitely many vertices where $x^1$ and $y^1$ equal $a$. Let
\begin{eqnarray*}
\{v_1, v_2,\ldots, v_r\}&=&\{v\in P_1\:|\: x^1_v=a\}\\
\{w_1, w_2,\ldots, w_{r^\prime}\}&=&\{w\in P_1\:|\: y^1_w=a\}\\
\{v_{r+1}, v_{r+2} \ldots, v_{r+k}\}&=&\{v\in P_2\:|\: x^1_v=a\}\\
\{w_{r^\prime+1}, w_{r^\p+2} \ldots, w_{r^\p+k^\p}\}&=&\{w\in P_2\:|\: y^1_w=a\}
\end{eqnarray*}
index the vertices with $a$ in $x^1$ and $y^1$. By lemma \ref{lemma:four special configurations} the configurations $\theta^{v_1, v_2 \ldots, v_{i}}_{b,b, \ldots, b}(x^1)$ and $\theta^{w_1, w_2 \ldots, w_{i^\prime}}_{b,b, \ldots, b}(y^1)$ are elements of $X$ for all $1\leq i \leq r+k$ and $1\leq i^\prime \leq r^\prime+k^\prime$. Therefore we can consider the following sequence(\ref{sequence:sequence_in_final_1} to \ref{sequence:sequence_in_final_5}) in $X$:

\noindent We begin by replacing the $a$'s in $x^1$ from the partite class $P_1$ by $b$'s.
\begin{gather}
(x^1, \theta^{v_1}_b(x^1),\theta^{v_1, v_2}_{b,b}(x^1),\ldots,\theta^{v_1, v_2,\ldots, v_r}_{b,b,\ldots,b}(x^1)).\label{sequence:sequence_in_final_1}
\end{gather}
In the resulting configuration $\theta^{v_1, v_2,\ldots, v_r}_{b,b,\ldots,b}(x^1)$ adjacent vertices cannot both have the symbol $a$; the $a$'s left in the configuration $x^1$ are changed to $b$'s.
\begin{gather}
(\theta^{v_1, v_2,\ldots, v_r}_{b,b,\ldots,b}(x^1),\theta^{v_1, v_2,\ldots, v_{r+1}}_{b,b,\ldots,b}(x^1),\ldots,\theta^{v_1, v_2,\ldots, v_{r+k}}_{b,b,\ldots,b}(x^1)).\label{sequence:sequence_in_final_2}
\end{gather}
After removing the $a$'s from $x^1$ and $y^1$ the configurations obtained are elements of $X_a$. 
\begin{gather}
(\theta^{v_1, v_2,\ldots, v_{r+k}}_{b,b,\ldots,b}(x^1),\theta^{w_1, w_2 \ldots, w_{r^\prime+k^\prime}}_{b,b, \ldots, b}(y^1)).\label{sequence:sequence_in_final_3}
\end{gather}
Tactics from sequences \ref{sequence:sequence_in_final_1} and \ref{sequence:sequence_in_final_2} are employed in reverse to obtain $y^1$ starting with $\theta^{w_1, w_2 \ldots, w_{r^\prime+k^\prime}}_{b,b, \ldots, b}(y^1)$.
\begin{gather}
(\theta^{w_1, w_2 \ldots, w_{r^\prime+k^\prime}}_{b,b, \ldots, b}(y^1),\theta^{w_1, w_2 \ldots, w_{r^\prime+k^\prime-1}}_{b,b, \ldots, b}(y^1), \ldots, \theta^{w_1, w_2 \ldots, w_{r^\prime}}_{b,b, \ldots, b}(y^1)),\label{sequence:sequence_in_final_4}\\
(\theta^{w_1, w_2 \ldots, w_{r^\prime}}_{b,b, \ldots, b}(y^1),\theta^{w_1, w_2 \ldots, w_{r^\prime-1}}_{b,b, \ldots, b}(y^1),\ldots, \theta^{w_1}_b(y^1),y^1)\label{sequence:sequence_in_final_5}.
\end{gather}

For all $1\leq i \leq r$, the vertex $v_i\in P_1$ and the symbol $x^1_{v_i}=a$. Thus by statement (\ref{item:nearby_not_a}) and (\ref{item:nearby_is_a}) in this proof we get that
$$(\theta^{v_1, v_2,\ldots, v_i}_{b,b,\ldots,b}(x^1),(\theta^{v_1, v_2,\ldots, v_{i+1}}_{b,b,\ldots,b}(x^1))$$
is $V^\prime$-good. Thus all adjacent pairs in the sequence \ref{sequence:sequence_in_final_1} are $V^\prime$-good

Notice that $(\theta^{v_1, v_2, \ldots, v_r}_{b,b,\ldots, b}(x^1))_v\neq a$ for all $v\in P_1$ and hence $(\theta^{v_1, v_2,\ldots, v_{r+i}}_{b,b,\ldots,b}(x^1))_v\neq a$ for all $1\leq i \leq k$ and $v\in P_1$. Now consider an adjacent pair in the sequence \ref{sequence:sequence_in_final_2},
$$(\theta^{v_1, v_2,\ldots, v_{r+i}}_{b,b,\ldots,b}(x^1),\theta^{v_1, v_2,\ldots, v_{r+i+1}}_{b,b,\ldots,b}(x^1))$$
for some $0\leq i \leq k-1$. Since $v_{r+i+1}\in P_2$ , $(\theta^{v_1, v_2,\ldots, v_{r+i}}_{b,b,\ldots,b}(x^1))_w\neq a$ for all $w\sim v_{r+i+1}$. But $(\theta^{v_1, v_2,\ldots, v_{r+i}}_{b,b,\ldots,b}(x^1))_{v_{r+i+1}}=a$, therefore by statement (\ref{item:nearby_not_a}) we get that
$$(\theta^{v_1, v_2,\ldots, v_{r+i}}_{b,b,\ldots,b}(x^1),\theta^{v_1, v_2,\ldots, v_{r+i+1}}_{b,b,\ldots,b}(x^1))$$
is $V^\prime$-good.

Notice that $(\theta^{v_1, v_2, \ldots, v_{r+k}}_{b,b,\ldots, b}(x^1)),(\theta^{w_1, w_2, \ldots, w_{r^\p+k^\p}}_{b,b,\ldots, b}(y^1))\in X_a$. Thus by conclusion (\ref{item:from_X_a}) in lemma \ref{lemma:construction_of_V^prime}, we get that the pair \ref{sequence:sequence_in_final_3} is $V^\prime$-good.

The proof that the adjacent pairs listed in sequences \ref{sequence:sequence_in_final_4} and \ref{sequence:sequence_in_final_5} are $V^\prime$-good is identical to the proof for the sequences \ref{sequence:sequence_in_final_2} and \ref{sequence:sequence_in_final_1} with an additional use of the symmetry of the relation $V^\prime$-good.

Thus all adjacent pairs in sequences \ref{sequence:sequence_in_final_1}-\ref{sequence:sequence_in_final_5} are $V^\prime$-good. By corollary \ref{corollary:chain_of_V-goodness} we get that $(x^1,y^1)$ is $V^\prime$-good. But $(x^1,y^1)$ is Markov-similar to $(x,y)$. By proposition \ref{prop:V-goodness_equivalence_markov_similar} we have that $(x,y)$ is $V^\prime$-good. This completes the proof.
\end{proof}

If $\G$ is finite then theorem \ref{thm:G-invariant main theorem} follows immediately from theorem \ref{thm:main theorem}: if $V^\prime$ is a nearest neighbour interaction for a $G$-invariant Markov cocycle $M$ then 
\begin{equation*}
\frac{\sum_{g\in G} gV^\prime}{|G|}
\end{equation*}
is a $G$-invariant nearest neighbour interaction for $M$. We will prove the following result which along with proposition \ref{proposition:induced_map_cocycles} immediately implies theorem \ref{thm:G-invariant main theorem}.

\begin{thm}\label{thm:extension of a Gibbs cocycle}
Let $\G=(\V, \E1)$ be a bipartite graph and $\A$ a finite alphabet. Let $G\subset Aut(\G)$ be a subgroup. Let $X$ be a $G$-invariant n.n.constraint space and $X_a$ be a fold of $X$. Suppose $M\in \M^G_{X}$ is a $G$-invariant Markov cocycle. Then $M\in \Gi^{G}_{X}$ if and only if $M|_{\Delta_{X_a}}\in \Gi^G_{X_a}$.
\end{thm}

\begin{proof} By proposition \ref{proposition:induced_map_cocycles}, $M\in \Gi^{G}_{X}$ implies $M|_{\Delta_{X_a}}\in \Gi^G_{X_a}$. We will prove the converse. Let $M\in \M^G_X$ such that $M|_{\Delta_{X_a}}\in \Gi^G_{X_a}$. Let $V$ be a $G$-invariant nearest neighbour interaction for $M|_{\Delta_{X_a}}$.

Mimicking the proof of lemma \ref{lemma:four special configurations} we will now obtain special configurations $x^v$ in a $G$-invariant way.

\begin{lemma}\label{lemma:G_invariant_four_special_configurations}
Let $G\subset Aut(\G)$ be a subgroup, $X$ be a $G$-invariant n.n.constraint space and $X_a$ be a fold of $X$ where the symbol $a$ is folded into the symbol $b$. Let
$$\V_1=\{v\in \V\:|\:\text{ there exists }w\sim v\text{ such that }[a,a]_{\{v,w\}}\in \B_{\{v,w\}}(X)\}$$
and
$$\V_2=\{v\in \V\setminus \V_1\:|\:[a]_{v}\in \B_{v}(X)\}.$$
Then $\V_1$ and $\V_2$ are invariant under the action of $G$. Moreover for all $v\in \V_1\cup \V_2$ there exists $x^v\in X$ satisfying the conclusions of lemma \ref{lemma:four special configurations} such that $(gx^v)|_{gD_2(v)}=x^{gv}|_{gD_2(v)}$ for all $g\in G$.
\end{lemma}

\begin{proof}
Since $X$ is $G$-invariant it follows that the sets $\V_1$ and $\V_2$ are $G$-invariant.

Consider some $v\in \V_1$ and $g\in G$. Then by lemma \ref{lemma:four special configurations} there exists $x^v, x^{gv}\in X$ such that $x^v_v=x^{gv}_{gv}=a$ and $x^v|_{D_2(v)\setminus \{v\}}=x^{gv}|_{D_2(gv)\setminus \{gv\}}=b$. Thus we find that $(gx^v)|_{gD_2(v)}=x^{gv}|_{gD_2(v)}$.

Let $v\in \V_2$. Then for all $w\sim v$, $g\in G$ and $c\in\A\setminus\{a\}$ the pattern $[a,c]_{\{v,w\}}\in \B_{\{v,w\}}(X)$ if and only if $[a,c]_{\{gv,gw\}}\in \B_{\{gv,gw\}}(X)$. Thus for all $w\sim v$ we can choose $c_{v,w}\in \A\setminus\{a\}$ such that $[a,c_{v,w}]_{\{v,w\}}\in \B_{\{v,w\}}(X)$ and $c_{v,w}= c_{gv,gw}$ for all $g\in G$. Note that since $v\in \V_2$ we know that $c_{v,w}\neq a$.

By equation \ref{equation:foldingdefn3} there exists $x^{1,v}\in X$ such that $x^{1,v}|_{\partial D_1(v)}=b$. Since $a$ can be folded into the symbol $b$ we can assume that $x^{1,v}\in X_a$. Consider $x^v\in \A^\V$ defined by
\begin{equation*}
x^v_u=\begin{cases}
a\ \ \ \text{ if }u=v\\
c_{v,u}\text{ if } u\sim v\\
x^{1,v}_u\text{ if } u\in D_1(v)^c.
\end{cases}•
\end{equation*}•
Note that $a$ appears in $x^{v}$ only at the vertex $v$. Any edge $(u_1, u_2)$ in $\G$ lies either completely in $D_2(v)$ or in $D_1(v)^c$. If the edge lies in $D_1(v)^c$ then $[x^v]_{\{u_1, u_2\}}= x^{1,v}_{\{u_1, u_2\}}\in \B_{\{u_1, u_2\}}(X)$. If the edge is of the form $(v,w)$ then $[x^v]_{\{v, w\}}= [a,c_{v,w}]_{\{v,w\}}\in \B_{\{v, w\}}(X)$. If the edge is of the form $(w, w^\prime)$ where $w\in \partial \{v\}$ and $w^\prime\in \partial D_1(v)$ then $[x^v]_{\{w, w^\prime\}}= [c_{v,w},b]_{\{w,w^\p\}}$. Since $(v,w)$ and $(w, w^\prime)$ are edges in the graph $\G$ and $[a,c_{v,w}]\in \B_{\{v,w\}}(X)$ by equation \ref{equation:foldingdefn2} we know that $[c_{v,w},b]_{\{w,w^\p\}}\in \B_{\{w,w^\p\}}(X)$.

Thus we have proved for every edge $(u_1,u_2)$ in $\G$ that $[x^v]_{\{u_1,u_2\}}\in \B_{\{u_1,u_2\}}(X)$. Since $X$ is an n.n.constraint space we get that $x^v\in X$.

Moreover for all $v\in \V_2$ and $g\in G$
\begin{equation*}
(gx^v)_{u}=\begin{cases}
a& \text{ if }u=gv\\
c_{v,g^{-1}u}&\text{ if } u\sim gv\\
b&\text{ if } u\in \partial D_1(gv)
\end{cases}•
\end{equation*}•
and
\begin{equation*}
(x^{gv})_{u}=\begin{cases}
a&\text{ if }u=gv\\
c_{gv,u}=c_{v,g^{-1}u}&\text{ if } u\sim gv\\
b&\text{ if } u\in \partial D_1(gv),
\end{cases}•
\end{equation*}•
that is, $(gx^v)|_{gD_2(v)}=x^{gv}|_{gD_2(v)}$.

Thus the configurations $x^v$ satisfy the conclusions (\ref{enumerate:configuration1}) and (\ref{enumerate:configuration2}) of lemma \ref{lemma:four special configurations} and $(gx^v)|_{gD_2(v)}=x^{gv}|_{gD_2(v)}$ for all $g\in G$ and $v\in \V_1\cup\V_2$. The rest follows exactly as in the proof of lemma \ref{lemma:four special configurations}.
\end{proof}
Consider sets $\V_1, \V_2\subset \V$ and for all $v\in \V$ configurations $x^v\in X$ as obtained by lemma \ref{lemma:G_invariant_four_special_configurations}. Then by lemma \ref{lemma:construction_of_V^prime} there exists a unique nearest neighbour interaction $V^\prime$ on $X$ such that the pairs (\ref{item:from_X_a}), (\ref{item:changing_b_at_v}), (\ref{item:changing_at_boundary_no_a}) and (\ref{item:changing_at_boundary_a}) listed in lemma \ref{lemma:construction_of_V^prime} are $V^\prime$-good. By lemma \ref{lemma:from_particular_pairs_to_all_pairs} we get that $V^\prime$ is a nearest neighbour interaction for $M$. We will prove that the interaction $V^\prime$ is $G$-invariant. For this we will invoke the uniqueness of the interaction satisfying the conclusions of lemma \ref{lemma:construction_of_V^prime}.

Let $g\in G$. $gV^\prime$ is a nearest neighbour interaction corresponding to $gM=M$. Thus the pairs listed in (\ref{item:from_X_a}), (\ref{item:changing_b_at_v}), (\ref{item:changing_at_boundary_no_a}) and (\ref{item:changing_at_boundary_a}) in lemma \ref{lemma:construction_of_V^prime} are $gV^\prime$-good. Since $V$ is $G$-invariant, $gV^\prime|_{\B_{X_a}}=gV=V$. Hence $gV^\prime$ satisfies equations \ref{equation:listinteract1} and \ref{equation:listinteract2}.

If $v\in \V_1\cup \V_2$ then we know from lemma \ref{lemma:G_invariant_four_special_configurations} that $(gx^v)|_{gD_1(v)}=x^{gv}|_{gD_1(v)}$. Thus if $w\sim v$ since $V^\prime$ satisfies equation \ref{equation:listinteract3} we get that
\begin{eqnarray*}
gV^\prime([x^v]_{\{v,w\}})=V^\prime([x^v_{v}, x^v_w]_{\{g^{-1}v,g^{-1}w\}})=V^\prime([x^{g^{-1}v}_{g^{-1}v}, x^{g^{-1}v}_{g^{-1}w}]_{\{g^{-1}v,g^{-1}w\}})=0.
\end{eqnarray*}
Thus the interaction $gV^\prime$ satisfies equation \ref{equation:listinteract3}. We have seen that the interaction $gV^\prime$ is a nearest neighbour interaction which satisfies equations \ref{equation:listinteract1}, \ref{equation:listinteract2} and \ref{equation:listinteract3} such that the pairs listed in (\ref{item:from_X_a}), (\ref{item:changing_b_at_v}), (\ref{item:changing_at_boundary_no_a}) and (\ref{item:changing_at_boundary_a}) in lemma \ref{lemma:construction_of_V^prime} are $gV^\prime$-good. By lemma \ref{lemma:construction_of_V^prime} we know that such an interaction is unique. Thus $gV^\prime=V^\prime$ and $M\in \Gi^G_X$.


\end{proof}

This leads us to the following corollary:

\begin{corollary}\label{corollary:folds_quotient_isomorphic}
Let $G=(\V, \E1)$ be a bipartite graph and $\A$ a finite alphabet. Let $G\subset Aut(\G)$ be a subgroup. Let $X$ be a $G$-invariant n.n.constraint space and $X_a$ be a fold of $X$. Then $\M^G_X/\Gi^G_X$ is isomorphic to $\M^G_{X_a}/\Gi^G_{X_a}$.
\end{corollary}

Clearly this corollary subsumes theorem \ref{thm:G-invariant main theorem}. Thereby to understand the difference between Markov and Gibbs cocycles it is sufficient to study the cocycles over configuration spaces which cannot be folded any further.

Also this corollary is most relevant when the dimension of the quotient space $\M^G_{X}/\Gi^G_{X}$ is finite. This holds in the following two situations:
\begin{enumerate}
\item
The underlying graph $\G$ is finite.
\item
The underlying graph $\G$ is $\Z^d$ for some dimension $d$, $G$ is the group of translations on $\Z^d$ and the space $X$ has the pivot property(defined in section 3 of \cite{chandgotiameyerovitch}).
\end{enumerate}•

\begin{proof}
By proposition \ref{proposition:induced_map_cocycles} the map $F:\M^G_X\longrightarrow \M^G_{X_a}$ given by
$$F(M)= M|_{\Delta_{X_a}}\text{ for all }M\in \M^G_{X_a}$$
is surjective. By theorem \ref{thm:extension of a Gibbs cocycle} we know that for a Markov cocycle $M\in \M^G_{X}$, $M\in \Gi^{G}_{X}$ if and only if $M|_{\Delta_{X_a}}\in \Gi^G_{X_a}$. Thus $F^{-1}(\Gi^G_{X_a})=\Gi^G_{X}$.

Via the second isomorphism theorem for vector spaces the map
$$\tilde{F}:\M^G_X/F^{-1}(\Gi^G_{X_a})\longrightarrow \M^G_{X_a}/\Gi^G_{X_a}$$
given by
$$\tilde{F}(M\!\!\!\mod F^{-1}(\Gi^G_{X_a})):=F(M)\!\!\!\mod\Gi^G_{X_a} $$
is an isomorphism. Since $F^{-1}(\Gi^G_{X_a})=\Gi^G_{X}$ the proof is complete.
\end{proof}



\section{Further Directions}\label{section:conclude}
\begin{enumerate}
\item
By theorems \ref{thm:main theorem} and \ref{thm:G-invariant main theorem} we have generalised the Hammersley-Clifford Theorem, but only when the graph $\G$ is bipartite. Can this be generalised further beyond the realms of the bipartite? Note that $\G$ being bipartite is used at many critical parts of the proof e.g. the construction of the elements $x^v$ in lemma \ref{lemma:four special configurations}, construction of the interaction in lemma \ref{lemma:construction_of_V^prime} etc.

\item

Suppose a finite graph $\H$ can be folded into a single vertex(with or without a loop) or an edge. We have proved that for any bipartite graph $\G$ the space $Hom(\G, \H)$ is Hammersley-Clifford. Also we have shown that being Hammersley-Clifford is invariant under foldings and unfoldings. Following \cite{brightwell2000gibbs} we will call a graph $\H$ \emph{stiff} if it cannot be folded anymore. Fixing a particular domain graph say $\Z^2$, is it possible to classify all stiff graphs $\H$ for which $Hom(\Z^2,\H)$ is Hammersley-Clifford? What if we want $Hom(\G, \H)$ to be Hammersley-Clifford for all bipartite graphs $\G$?

\item

Suppose $\G$ is a finite bipartite graph. Then the space of cocycles $Hom(\G, \H)$ is finite dimensional for all finite graphs $\H$. Is there an efficient algorithm to determine the dimension of the space of cocycles $\M_{Hom(\G, \H)}$ and $\Gi_{Hom(\G, \H)}$?

In another direction, is there a graph $\H$ for which the space of $\sigma$-invariant Markov cocycles $\M^\sigma_{Hom(\Z^d, \H)}$ is infinite dimensional? Is there an algorithm to determine the dimension of $\M^\sigma_{Hom(\Z^d, \H)}$ and $\Gi^\sigma_{Hom(\Z^d, \H)}$? We know from \cite{chandgotiameyerovitch} that if $Hom(\Z^d, \H)$ has the pivot property then the dimension of  $\M^\sigma_{Hom(\Z^d, \H)}$ is finite, however we do not know the corresponding dimension beyond a few specific cases. (Section 5 of \cite{chandgotiameyerovitch})
\end{enumerate}•

\bibliographystyle{plain}
\bibliography{MRF_3CB}
\end{document}





gebihammersley.bbl
\begin{thebibliography}{10}

\bibitem{brightwell2000gibbs}
Graham~R Brightwell and Peter Winkler.
\newblock Gibbs measures and dismantlable graphs.
\newblock {\em Journal of Combinatorial Theory, Series B}, 78(1):141--166,
  2000.

\bibitem{Chandgotia}
Nishant Chandgotia.
\newblock {M}arkov random fields and measures with nearest neighbour
  potentials.
\newblock {\em MSc Thesis}, 2011.

\bibitem{Markovfieldchain}
Nishant Chandgotia, Guangyue Han, Brian Marcus, Tom Meyerovitch, and Ronnie
  Pavlov.
\newblock One dimensional {M}arkov random fields, {M}arkov chains and
  topological {M}arkov fields.
\newblock {\em AMS Proceedings(To Appear)}, 2011.

\bibitem{chandgotiameyerovitch}
Nishant Chandgotia and Tom Meyerovitch.
\newblock Markov random fields, {M}arkov cocycles and the 3-colored chessboard.
\newblock {\em arXiv preprint arXiv:1305.0808}, 2013.

\bibitem{Preston}
C.J.Preston.
\newblock {\em Gibbs states on countable sets}.
\newblock Number~68 in Cambridge Tracts in Mathematics. Cambridge University
  Press, 1974.

\bibitem{dob}
R.L. Dobruschin.
\newblock Description of a random field by means of conditional probabilities
  and conditions for its regularity.
\newblock {\em Theory Prob. Appl.}, 13:197--224, 1968.

\bibitem{Georgii}
H.~Georgii.
\newblock {\em Gibbs measures and phase transitions}.
\newblock de Gruyter Studies in Mathematics, Walter de Gruyter {\&} Co.,
  Berlin, 1988.

\bibitem{sturmfel}
Dan Gieger, Christopher Meek, and Bernd Sturmfels.
\newblock On the toric algebra of graphical models.
\newblock {\em Ann. Statist.}, 34(3):1461--1492, 2006.

\bibitem{HammersleyClifford71}
J.~M. Hammersley and P.~Clifford.
\newblock {Markov field on finite graphs and lattices}.
\newblock 1971.

\bibitem{laur}
S.~Lauritzen.
\newblock {\em Graphical Models}.
\newblock Clarendon Press, Oxford, 1996.

\bibitem{LM}
D~Lind and B.~Marcus.
\newblock {\em An introduction to symbolic dynamics and coding}.
\newblock Cambridge University Press, 1995, reprinted 1999.

\bibitem{mouss}
J.~Moussouris.
\newblock Gibbs and {M}arkov random systems with constraints.
\newblock {\em Journal of Statistical Physics}, 10:11--33, 1974.

\bibitem{nowakowskiwinkler}
Richard Nowakowski and Peter Winkler.
\newblock Vertex-to-vertex pursuit in a graph.
\newblock {\em Discerte math.}, 43(2-3):235--239, 1983.

\bibitem{petersen_schmidt1997}
Karl Petersen and Klaus Schmidt.
\newblock Symmetric {G}ibbs measures.
\newblock {\em Trans. Amer. Math. Soc.}, 349(7):2775--2811, 1997.

\end{thebibliography}
