%% LyX 1.5.4 created this file. For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[oneside,english]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{nicefrac}
\usepackage{graphicx}
\usepackage{amssymb}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\numberwithin{equation}{section} %% Comment out for sequentially-numbered
\numberwithin{figure}{section} %% Comment out for sequentially-numbered
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\theoremstyle{plain}
\newtheorem{lem}[thm]{Lemma}
\theoremstyle{plain}
\newtheorem{algorithm}[thm]{Algorithm}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% User specified LaTeX commands.
\input{preamble.tex}
\lecture{19}{April 15, 2009}{Madhu Sudan}{Alex Arkhipov}
\usepackage{babel}
\makeatother
\begin{document}
\section{Review of Last Class}
Last class we gave a formulation of Probabilistically Checkable Proofs
as a coloring of a graph that satisfies certain constraints.
\begin{defn}
The \textit{graph $k$-coloring problem} is as follows:
\begin{quote}
Given a graph $G=\left(E,V\right)$, does there exist a coloring $\chi:V\rightarrow\left\{ 1,2,\dots,k\right\} $
such that for each $(u,v)\in E$, $\chi(u)\neq\chi(v)$?
\end{quote}
\end{defn}
In generalized graph coloring, each edge restricts the coloring of
its endpoints by an arbitary relation, described by an admissibility
function $\Pi$.
\begin{defn}
The generalized \textit{$k$-coloring problem} is as follows:
\begin{quote}
Given a graph $G=\left(E,V,\Pi\right)$, which includes map $\Pi:E\times\left\{ 1,2,\dots,k\right\} \times\left\{ 1,2,\dots,k\right\} \rightarrow\left\{ 0,1\right\} $,
does there exist a coloring $\chi:V\rightarrow\left\{ 1,2,\dots,k\right\} $
such that for each $e=(u,v)\in E$, $\Pi\left(e,\chi\left(u\right),\chi\left(v\right)\right)=1$?
\end{quote}
\end{defn}
In a coloring $\chi$, we say an edge $e=(u,v)$ is \textit{invalid
}if it does not satisfy the constraint $\Pi\left(e,\chi\left(u\right),\chi\left(v\right)\right)=1$.
The unsatisfiability UNSAT$(G,\chi)$ is fraction of invalid edges
in $G$, and the unsatisfiability UNSAT$(G)$ of a graph is the minimum
UNSAT$(G,\chi)$ over all colorings $\chi$.
Recall the Lemma that we wished to prove that would allow us to reduce
the number of colors:
\begin{lem}
\label{lem:colorreduction}There exists a $k$ and $\delta>0$, so
that for any $K$, there is a reduction function $f$ from $K$-coloring
instances to $k$-coloring instances so that for any $G$ and $\tilde{G}=f\left(G\right)$,
\begin{itemize}
\item If $\mbox{UNSAT}(G)=0$, then $\mbox{UNSAT}(\tilde{G})=0$.
\item $\mbox{UNSAT}(\tilde{G})\geq\delta\mbox{UNSAT}(G)$
\end{itemize}
\end{lem}
We'll first see look at a naive attempt to perform this reduction,
and see how it can lead to unsatisfiability falling by more than a
constant factor $\delta$.
\subsection{Attempt at reduction from $K$-coloring to $3$-coloring}
To illustrate the obstacle to showing Lemma \ref{lem:colorreduction},
we'll sketch a linear time reduction for standard $K$-coloring to
standard $k$-coloring, with $k=3$. We'll convert $K$-coloring instance
$G$ to a $3$-coloring instance $\tilde{G}$ by replacing each edge
of $G$ with a gadget of $\tilde{G}$ that encodes the same restriction.
However, we'll find that if $\mbox{UNSAT}\left(G\right)=\varepsilon$,
then $\mbox{UNSAT}\left(\tilde{G}\right)\leq\frac{\varepsilon}{K}$,
and thus cannot satisfy $\mbox{UNSAT}(\tilde{G})\geq\delta\mbox{UNSAT}(G)$
for any constant $\delta$.
\subsubsection{Construction of $\tilde{G}$}
Make three special nodes $\left\{ r,g,b\right\} $ and connect them
with edges, so that they must be different colors which we'll label
red, green, and blue, which we will also call the three possible colors
of the nodes. We may restrict the possible colors of a node in $\tilde{G}$
by connecting it to each of $\left\{ r,g,b\right\} $ we want to exclude.
For each node $u\in G$, make $K+1$ nodes $u_{0},\dots u_{K}$ in
$\tilde{G}$. Restrict them to be each red or green (by connecting
each by an edge to the blue node), and furthermore restrict $u_{0}$
to be red and $u_{K}$ to be green. Then, in any coloring of $\tilde{G}$,
there is some first node $u_{j}$ that marks a switch from red to
green; i.e. the first $i\in\left\{ 1,\dots,K\right\} $ so that $u_{j-1}$
is red and $u_{j}$ is green. (We may assume that $u_{i}$ is red
for $i