% From yumat@llaic3.u-clermont1.fr Wed Sep 26 11:20:11 2001
\documentclass[12pt]{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\addtolength{\oddsidemargin}{-10mm}
\addtolength{\evensidemargin}{-10mm}
\addtolength{\textwidth}{25mm}
\addtolength{\textheight}{40mm}
\addtolength{\topmargin}{-25mm}
\tolerance=5000
\newcommand{\Prob}{{\mathrm {Prob}}}
\newcommand{\Ao}{A^{\mathrm {odd}}}
\newcommand{\Ae}{A^{\mathrm {even}}}
\newcommand{\Ra}{\cal R}
\newcommand{\eqlabel}[1]{\label{#1}}
\newcommand{\langlemy}{\langle}
\newcommand{\ranglemy}{\rangle}
\newcommand{\tuple}[1]{\langlemy #1 \ranglemy}
\newcounter{thnumber}
\newtheorem{thmpoint}{Theorem}
\renewcommand{\thethmpoint}{\arabic{thmpoint}.}
\newenvironment{thm}{\begin{thmpoint}\refstepcounter{thnumber}
} {\end{thmpoint}}
\newcounter{colnumber}
\newtheorem{colpoint}{Corollary}
\renewcommand{\thecolpoint}{\arabic{thmpoint}.\arabic{colpoint}.}
\newenvironment{col}{\begin{colpoint}
\refstepcounter{colnumber}
} {\end{colpoint}}
\author{Yuri Matiyasevich
\\Steklov Institute of Mathematics at Saint-Petersburg
\\27 Fontanka, Saint-Petersburg, 191011, Russia\\
URL: {\tt http://logic.pdmi.ras.ru/$\tilde{\phantom{x}}$yumat}}
\title{Some Probabilistic Restatements of\\ the Four Color Conjecture}
\begin{document}
\maketitle
The famous Four Color Conjecure (4CC for short)
has, as many outstanding mathematical problems have,
numerous equivalent reformulations (see, for example,
\cite{Colin93}, \cite{Fritsch94}, \cite{HoffmanMS92},%
\cite{Kainen93}, \cite{Kaufman90}, \cite{Kaufman93},%
\cite{Kaufman94}, \cite{KaufmanS93}, \cite{Matiyasevich97},%
\cite{Saaty72}, \cite{Thomas98} and further references in these
papers). Sometimes such reformulations are given in terms very
remote from maps, graphs and colorings. In this paper several new
restatements of the 4CC will be given, formally as assertions
about correlations of some random events. Of course now that we
have proofs of the Four Color Theorem given by K.~Appel,
W.~Haken and J.~Koch \cite{AppelH77,AppelHK77,AppelH89} and, more
recently, by N.~Robertson, D.~Sanders, P.~Seymour and R.~Thomas
\cite{RobertsonSST} these restatements become corollaries of the
Four Color Theorem.
Clearly, it is sufficient to prove the 4CC for an arbitrary
maximal planar graph $G$ with $3n$ edges where $n>0$. Such a
graph, being drawn on a sphere, defines its triangulation.
%
Let us cut the sphere along the edges of the graph $G$
into triangular facets.
This results in a graph $H$ consisting of $2n$ copies of the full
graph $K_3$ which will be called the \emph{cut graph} of graph $G$.
By a coloring
of this
graph $H$ we shall always mean a coloring of its edges
in three colors $0$, $1$, and $2$.
Clearly, there are $6^{2n}$ such colorings.
We are to introduce two notions of likelyhood of the colorings of the
graph $H$; the 4CC will be equivalent to different statements
about correlations between these two
notions.
First, the graph $H$ inherites from the graph $G$ an additional
structure, namely, a cyclic order of edges in every connected
component. We shall say that such a component is colored
\emph{positively} if
colors $0$, $1$ and $2$ follow in ``clock-wise order",
and \emph{negatively} otherwise.
Further, we shall say that a coloring of $H$ is \emph{even} or
\emph{odd}
depending on whether the number of positively
(or, equivalently, negatively) colored components is even or odd.
At last, we shall say that two colorings of the graph $H$ have the same
\emph{parity} if both of them are either even or odd.
Second, every coloring of the graph $H$ \emph{induces} assignement
of colors to the edges of the graph $G$ in the following way: to
get the color of some edge $e$ of the graph $G$ we add modulo 3
the colors of the two edges of the graph $H$ into which the edge
$e$ was split during the generation of graph $H$ from graph $G$.
We shall say that two colorings of graph $H$ are
\emph{equivalent} if they induce the same assignments of colors to
the edges of graph $G$.
Now, let two colorings of the graph $H$ be selected at random
independently one from another, that is, the probality of the
elementary event of selecting any particulat pair of colorings
$\tuple{\mu_1,\mu_2}$ is equal to $6^{-4n}$. Let $A$ be the random
event ``the colorings $\mu_1$ and $\mu_2$ have the same parity",
and let $B$ be the random event ``the colorings $\mu_1$ and
$\mu_2$ are equivalent".
It turns out that the 4CC is equivalent to the existence of
correlation between the events $A$ and $B$.
\begin{thm}For every maximal planar graph $G$ with $3n$ edges
\begin{eqnarray}
\Prob\{A \& B\}-\Prob\{A\}\Prob\{B\}&=&{\tfrac{1}{8}}(\tfrac{3}{4})^n\chi_G(4)
\end{eqnarray}
where $\chi_G(4)$ is the number of colorings of vertices of graph $G$
in 4 colors.
\end{thm}
\begin{col}The Four Color Conjecture is equivalent to the assertion
that for every maximal planar graph $G$ the events $A$ and $B$ are
(positively) correlated.
\end{col}
The event $A$ can be split into two event, $\Ae$, ``both colorings
$\mu_1$ and $\mu_2$ are even", and $\Ao$, ``both colorings
$\mu_1$ and $\mu_2$ are odd". Clearly, both events, $\Ae$ and $\Ao$,
have the same probability equal to 0.25.
It follows from Theorem 1 that at least
one of these two events should positively correlate with the
event $B$. In fact, both of
them correlate positevely, but to a different degree.
\begin{thm}For every maximal planar graph $G$ with $3n$ edges
\begin{eqnarray}
\Prob\{\Ae \& B\}-\Prob\{\Ao\& B\}&=&(-\tfrac{1}{16})^n\chi_G(4).
\end{eqnarray}
\end{thm}
\setcounter{colpoint}{0}
\begin{col}For every maximal planar graph $G$ with $3n$ edges
\begin{eqnarray}
\Prob\{\Ae \& B\}-\Prob\{\Ae\}\Prob\{B\}&=&\tfrac{1}{16}
\left((\tfrac{3}{4})^n+(-\tfrac{1}{4})^n\right)\chi_G(4),\\
\Prob\{\Ao \& B\}-\Prob\{\Ao\}\Prob\{B\}&=&
\tfrac{1}{16}\left((\tfrac{3}{4})^n-(-\tfrac{1}{4})^n\right)\chi_G(4).
\end{eqnarray}
\end{col}
\begin{col}The Four Color Conjecture is equivalent to the assertion
that for every maximal planar graph $G$ the events $\Ae$ and $B$ are
(positively) correlated.
\end{col}
\begin{col}The Four Color Conjecture is equivalent to the assertion
that for every maximal planar graph $G$ the events $\Ao$ and $B$ are
(positively) correlated.
\end{col}
\begin{col}The Four Color Conjecture is equivalent to the assertion
that for every maximal planar graph $G$ with $3n$ edges
the probability for two random
edge colorings of its cut graph $H$ to be equivalent under the condition
that both colorings are even is different from similar probability
under the
condition that both colorings are odd (greater in the case of an even $n$
and smaller in the case of an odd $n$).
\end{col}
\begin{thebibliography}{19}
\bibitem{AppelH77}
K.~Appel, W.~Haken. Every planar map is four colorable.\ Part I.\
Discharging. {\it Illinois J. of Mathematics}, {\bf
21}(3):429--490 (1977).
\bibitem{AppelHK77}
K.~Appel, W.~Haken, J.~Koch. Every planar map is four colorable.\
Part II.\ Reducibility. {\it Illinois J.\ of Mathematics}, {\bf
21}(3):491--567 (1977).
\bibitem{AppelH89}
K.~Appel, W.~Haken. Every planar map is four colorable. {\it AMS
Contemporary Mathematics}, 98, 1989.
\bibitem{Colin93}
Yves Colin de Verdiere. On a new graph invariant and a criterion
for
planarity.
{\it Contemp. Math}., 147,
Amer. Math. Soc., Providence, RI, 1993.
\bibitem{HoffmanMS92}
Todd Hoffman, John Mitchem, Edward Schmeichel. On edge-coloring
graphs. {\it Ars Combinatoria} 33 (1992),
119--128.
\bibitem{Kainen93}
Paul C. Kainen. Is the four color theorem true? {\it
Geombinatorics} 3 (1993),
no. 2, 41--56.
\bibitem{Kaufman90}
L. Kaufmann, Map coloring and the vector cross product, {\it J.
Combin. Theory}, Ser. B 48 (1990).
\bibitem{Kaufman93}
Louis H. Kauffman. Combinatorial recoupling theory and
$3$-manifold
invariants.
In: {\it Low-dimensional topology and
quantum field theory (Cambridge, 1992)}, 1--17
({\it NATO Adv. Sci. Inst}. Ser. B Phys., 315),
Plenum, New York, 1993.
\bibitem{Kaufman94}
Louis H. Kauffman. Spin networks, topology and discrete physics.
{\it Adv. Ser. Math. Phys}., 17,
World Sci. Publishing, River Edge, NJ, 1994,
234--274
\bibitem{KaufmanS93}
Louis H. Kauffman, H. Saleur. An algebraic approach to the planar
coloring
problem.
{\it Communications in Mathematical Physics\/} 152 (1993), no. 3,
565--590.
\bibitem{MatiyasevichWWWpol}
Yuri Matiyasevich. A Polynomial related to Colourings of
Triangulation of Sphere. URL: {\tt
http://logic.pdmi.ras.ru/\linebreak[0]%
$\tilde{\phantom{x}}$yumat/\linebreak[0]%
journal/\linebreak[0]%
triangular/\linebreak[0]%
triang.htm}, mirrored at
{\tt http://www.informatik.\linebreak[0]%
uni-stuttgart.de/\linebreak[0]%
ifi/\linebreak[0]%
%
ti/\linebreak[0]%
%
personen/\linebreak[0]%
Matiyasevich/\linebreak[0]%
journal/\linebreak[0]%
triangular/\linebreak[0]%
triang.htm}.
\bibitem{Matiyasevich97}
Yuri Matiyasevich. The Four Colour Theorem as a possible corollary
of binomial summation. URL: {\tt
http://logic.pdmi.ras.ru/\linebreak[0]%
$\tilde{\phantom{x}}$yumat/%
\linebreak[0]%
journal/\linebreak[0]%
jcontord.htm\#4cc}, mirrored at
{\tt http://www.informatik.\linebreak[0]%
uni-stuttgart.de/\linebreak[0]%
ifi/\linebreak[0]%
%
ti/\linebreak[0]%
%
personen/\linebreak[0]%
Matiyasevich/\linebreak[0]%
journal/\linebreak[0]%
jcontord.htm\#4cc}.
\bibitem{May65}
K.~O.~May. The origin of the four-color conjecture. {\it Isis},
{\bf 56}, 346--348 (1965).
\bibitem{PetkovsekWZ96}
M.~Petkov\v sek, H.~Wilf, and D.~Zeilberger. {\it A=B}, AK Peters,
Wellesley, Mass., USA (1996). {\tt ISBN 1-56881-063-6}.
{\tt http://www.cis.\linebreak[0]%
upenn.edu/\linebreak[0]%
$\tilde{\phantom{m}}$wilf/\linebreak[0]%
AeqB.html}.
\bibitem{RobertsonSST}
Neil Robertson, Daniel Sanders, Paul Seymour, and Robin Thomas.
The Four-colour Theorem. {\it J. of Combinatorial Theory}, Ser. B
{\bf 70}:1, 2-44 (1997).
\bibitem{RobertsonST94}
Neil Robertson, Paul Seymour, and Robin Thomas, Quickly excluding
a planar graph, {\it J. Combin. Theory}, Ser. B 62 (1994),
323--348.
\bibitem{Thomas98}
Thomas R., An update on the Four-Colour Theorem. {\it Notices of
the AMS}, {\bf 45}:7, 848--859 (1998),
(available at URLs: http://www.ams.org/\linebreak[0]%
noticies/\linebreak[0]%
199807/\linebreak[0]%
thomas.\{ps,pdf\})
\bibitem{Saaty72}
T.~L.~Saaty. Thirteen colorful variations on Guthrie's four-color
conjecture. {\it American Mathematical Monthly}, {\bf 79}(1):2--43
(1972).
\end{thebibliography}
\end{document}