\documentclass[12pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}
\usepackage{amssymb,amsmath}
%\usepackage[pdftex]{color,graphicx}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\begin{document}
\input{preamble.tex}
\newenvironment{example}[1]{\paragraph{Example~\thetheorem: #1}\stepcounter{theorem}}{} % reuse the 'theorem' counter

\lecture{6}{November 23, 2009}{Ronitt Rubinfeld}{Ghila Castelnuovo and Ran Roth}

\section{Lecture Outline}
\begin{itemize}
	\item  Testing properties of dense graphs: Triangle-freeness.
\end{itemize}

\section{The Goal}

The goal of today's lecture is to find a property tester for dense graphs for the "Triangle free" property.
We will work with a graph $G = (V, E)$ given in the adjacenty matrix model.
$A$ is $n \times n$ matrix representing $G$.

\begin{definition}
$$
G \text{ is \emph{triangle free }} if  \nexists x, y, z \in V \text{such that } A(x,y) = A(y,z) = A(x,z) = 1.
$$
\end{definition}

Our goal is to find a tester which runs in sublinear time, which always accepts triangle-free graphs, and rejects with high probability graphs that are $\epsilon$-far from having the triangle-freeness property.

Before we begin, some definitions:\\
Let $A,B\subset V$ such that $A\cap B = \emptyset$, $|A|,|B|\geq 2$.
\begin{definition}
The \em{number of edges} between $A$ and $B$ 
$$
e(A,B)\equiv |\{(u,v): u \in A, b\in B\}| . 
$$\\
\end{definition}
\begin{definition}
The \em{density} between $A$ and $B$
$$
d(A,B)=\frac{d(A,B)}{|A||B|}.
$$
\end{definition}

\section{Thought experiment}
%\begin{figure}[!h]
%\includegraphics[height=60mm, width=60mm]{tripartite_eta.jpg}
%\end{figure}
Let $G$ be a random tripartite graph for which:
$$
\text{For every two nodes }u \in V_i, v \in V_j  \Pr[A(u,v)=1] =\eta \\
$$
\subsection{How many triangles do we have in G?}
Let 
$
\sigma(u,v,w)=
\begin{cases}
1  &\text{if } (u,v,w) \text{ form a triangle}\\
0  &\text{otherwise} 
\end{cases} 
$\\
then,
$$
 \forall u \in V_1,v \in V_2, w\in V_3, Pr[\sigma(u,v,w) = 1] = \eta^3 
$$
Thus
$$
 \mathrm{E}[\sigma(u,v,w)] = \eta^3. 
$$
From the linearity of the expectency we get
$$
 \mathrm{E}[\text{number of triangles in G}] = \eta^3|A||B||C|
$$
\section{The Komlos-Simonovits Lemma.}
\begin{definition}
Let $G=(V,E)$ be a graph, and let $A,B \subset V$.
We say that $(A,B)$ are $\gamma$-regular if 
$$
\forall A' \subset A, \forall B' \subset B \text{ such that } |A'| \geq \gamma|A| \text{ and } |B|\geq\gamma|B| 
$$
$$
 \abs{d(A',B') - d(A,B)} < \gamma.
$$
\end{definition}
Notice that the regularity property is very similar to the randomness property. Intuitivily, it expresses an important property of random graphs: Given two sets of vertices $A,B$ in a random graph, the expected fraction of edges between subsets of $A,B$ is identical to the expected fraction of edges between $A,B$. This ensures a uniformity in the distribution of the edges.
\begin{lemma}
\label{lemma:ks}
Komlos-Simonovits' Lemma.\\
$$
\forall \eta>0, \exists \gamma=\gamma^\triangle(\eta)=\frac{\eta}{2}, \exists \delta= \delta^\triangle(\eta)=(1-\eta)\frac{\eta^3}{8}
$$ 
such that if $A,B,C$ are disjoint subsets of $V$ and each pair of them is $\gamma$- regular with density $\geq \eta$,\\
then $G$ contains at least $\gamma|A||B||C|$ distinct triangles, each one of them with one vertex from each one of A,B,C.
\end{lemma}
Notice that this number is very similar to the number of triangles in three partite random graph. For example, if $\eta\leq\frac{1}{2}$ then $\delta (1-\eta)\frac{\eta^3}{8} \geq\frac{\eta^3}{16}$, so there is only a constant difference between the number of triangles in this graph and the expected number of triangles in the three partite random graph.
Before we prove the lemma we need to prove the following claim.
\begin{definition}
$$
A^* = \{\text{nodes in A with at least }(\eta-\gamma)|B|\text{ neighbors in B and at least }(\eta-\gamma)|C|\text{ neighbors in C}\}.
%$$
%Formally: 
%$$
%A^* = \{u\in A : (|\{v \in B :A(u,v)=1\}| \geq (\eta-\gamma)|B|) \wedge 
% (|\{w \in C :A(u,w)=1\}| \geq (\eta-\gamma)|C|)\} 
$$
\end{definition}
\begin{claim}
\label{claim:Astar}
$|A^*| \geq (1-2\gamma)|A|.$
\end{claim}
\begin{proof}
Define \\
\begin{equation}
A' =\{ \text{bad nodes in A with respect to B} \}
\end{equation}
Formally, 
\begin{equation}
A' = \{u\in A : |\{v \in B : A(u,v)=1\}| < (\eta-\gamma)|B|\}
\end{equation}
We show that,
$$
|A'|\leq \gamma|A|. 
$$
Indeed, suppose for contradiction that 
\begin{equation}
|A'| > \gamma|A|. 
\end{equation}
then
\begin{equation}
d(A',B) = \frac{e(A',B)}{|A'||B|} < \frac{\overbrace{(\eta - \gamma)|A'||B|}^\text{because of the definition of A'} }{|A'||B|} = \eta - \gamma.
\end{equation}
and from this we have:
\begin{equation}
 \abs{d(A,B) - d(A',B)}>\eta - (\eta - \gamma) = \gamma.
\end{equation}
We have:\\
$d(A,B)\geq \eta$ because $(A,B)$ has density $\geq \eta$.\\
$d(A',B)<\eta - \gamma$ because the definition of $A'$.\\
And this is a contradiction to the regularity assumption.
Therefore
\begin{equation}
\label{eq:atag}
|A'|\leq \gamma|A|.
\end{equation}
Similarly if 
\begin{equation}
A'' =\{ \text{bad nodes in A with respect to C} \}
\end{equation}
Then 
\begin{equation}
\label{eq:atagtag}
|A''|\leq \gamma|A|.
\end{equation}
Finally, from (\ref{eq:atagtag}) and (\ref{eq:atag}): 
\begin{equation}
A^* = A\backslash(A'\cup A'') \Rightarrow |A*| \geq |A| - 2\gamma|A| = (1-2\gamma)|A|.
\end{equation}
\end{proof}
\newline
Now we are ready to prove Komlos-Simonovits' Lemma:
\newline
\newline
\begin{proof}
\newline
Let 
$$
\gamma^\triangle(\eta) = \frac{\eta}{2} 
$$
and
$$
\delta^\triangle(\eta) = (1-\eta)\frac{\eta^3}{8} 
$$
\begin{definition}
For each $u \in A^* $, define:
$$
B_u =\{\text{neighbors of u in B}\}
%\text{ same as }
%B_u = \{v \in B : A(u,v) = 1\}. 
$$
and
$$
C_u =\{\text{neighbors of u in C}\}
%\text{ same as }
%C_u = \{w \in C : A(u,w) = 1\}.
$$
Note that 
$$
|B_u|\geq (\eta - \gamma) |B| \text{ and } |C_u|\geq (\eta - \gamma) |C|. \text{(by definition of $A^*$)}
$$

\end{definition}

\begin{observation}
Notice that the number of edges between $B_u$ and $C_u$ gives exactly the number of distinct triangles with u as one of their vertices.
\end{observation}
We know that
\begin{equation}
d(B,C)\geq \eta \qquad \text{ (because they have density $\eta$)}.
\end{equation}
\begin{equation}
|B_u|\geq (\eta - \gamma) |B| \overbrace{\geq} ^\text{because $\gamma=\frac{\eta}{2}$} \gamma |B|
\end{equation}
\begin{equation}
|C_u| \geq (\eta - \gamma) |C| \overbrace{\geq} ^\text{because $\gamma=\frac{\eta}{2}$} \gamma |C|
\end{equation}
From regularity we have 
\begin{equation}
d(B_u, C_u) \geq \abs{d(B,C) - \gamma} \geq \eta - \gamma. 
\end{equation}
And from this we get 
\begin{equation}
e(B_u, C_u) > (\eta - \gamma) |B_u||C_u| \geq (\eta - \gamma) ^ 3 |B| |C|.
\end{equation}
Therefore the total number of triangles is: 
\begin{equation}
\#\text{triangles}=|A^*| (\eta - \gamma) ^3 |B||C|.
\end{equation}
From the claim we have that 
\begin{equation}
|A^*| \geq (1-2\gamma) |A|. 
\end{equation}
So
\begin{equation}
\#\text{triangles} \geq (1-2\gamma) |A| (\eta - \gamma) ^3 |B||C| \geq (1-\eta) \frac{\eta^3}{8}|A||B||C|.
\end{equation} 
\end{proof}

\section{Szemer\'{e}di Regularity Lemma}
\begin{lemma}
$\forall m, \forall \epsilon'  > 0, \exists T$ such that the following holds:\newline
Given a graph $G=(V,E)$ for which $|V|>T$ and an equi-partition $A$ of $V$ into m subsets, there exists an equi-partition $B$ of $V$ into $k$ subsets such that:
\begin{itemize}
\item $B$ is a refinement of $A$
\item $m \leq k \leq T$
\item At most $\epsilon' {k \choose 2}$ subset pairs are not $\epsilon'$-regular.
\end{itemize}
\end{lemma}
\subsection{Notes}
\begin{itemize}
\item We don't prove the lemma here.
\item There is a technical issue with the factorization of n and k. In some versions, a "garbage can" subset is added in order to solve this problem. Here, for the sake of simplicity we assume $k|n$.
\item $T$ can be very large. In fact it can be as high as a tower function whose height depends on $\epsilon'$. However, it doesn't depend on $|V|$, so we consider it as a (unfortunately large) constant. Furthermore, a lower bound has been shown, i.e. for certain graphs T must be a tower function.
%\item Note that $\epsilon'$ plays two independent roles: The factor of pairs %that are not regular and the degree of their regularity. This is not necessary, %but helps reduce the number of parameters with which one has to deal. 
\end{itemize}
\section{Algorithm for testing triangle freeness}
\begin{definition}
Let $G=(V,E)$ be a graph given in the adjacency matrix model. We say that G is \em $\epsilon$-far from being triangle-free \em if more than $\epsilon n^2$ edges need to be removed from $G$ to make it triangle-free.
\end{definition}
\begin{theorem}
$\forall \epsilon, \exists \delta$ such that every graph $G=(V,E)$ that is $\epsilon$-far from being triangle free has at least $\delta {n \choose 3}$ distinct triangles.
\end{theorem}
\begin{proof}
Let $A$ be an arbitrary equipartition with $\frac{\epsilon}{5}$ subsets. By Szemeredi's regularity lemma, for $m=\frac{\epsilon}{5}$ and $\epsilon'=\frac{\epsilon}{10}$, there is a number $T=T(m,\epsilon')=T(\epsilon)$ and a partition $B$ into ${V_1,V_2,...V_k}$ such that at most $\epsilon' {k \choose 2}$ set-pairs are not  $\epsilon'-regular$ and:
\begin{equation}
\label{eq:kbounds}
\frac{5}{\epsilon} \leq k \leq T.\\ 
\end{equation}
Equation (\ref{eq:kbounds}) is equivalent to:
\begin{equation}
\label{eq:kbounds2}
\frac{\epsilon n}{5} \geq \frac{n}{k} \geq \frac{n}{T}\\
\end{equation}
Note that because $B$ is an equipartition
\begin{equation}
|V_1| = |V_2| = ... = |V_n| = \frac{n}{k}
\end{equation}
We define a procedure to obtain a new graph $G'$ from $G$ by removing less than $\epsilon n^2$ edges:
\begin{itemize}
\item Delete all internal edges in G, i.e. edges $(u,v)$ such that $u$ and $v$  belong to the same $V_i$.
There are at most $(\frac{n}{k})^2$ edges in each $V_i$, and $i=1...k$, so at most $\frac{n^2}{k}$ edges are removed. By equation (\ref{eq:kbounds2}) this is $\leq n\frac{\epsilon n}{5}=\frac{\epsilon}{5}n^2$
\item Delete edges between non-$\epsilon'$-regular pairs. 
There are $\leq \epsilon' {k \choose 2}$ such pairs, and between each pair there are at most $(\frac{n}{k})^2$ edges. So, at most $\epsilon' \frac{k(k-1)}{2} \frac{n^2}{k^2} \leq \frac{\epsilon'}{2} n^2 = \frac{\epsilon}{20}n^2 < \frac{\epsilon}{5}n^2$ edges are removed.
\item Delete edges between pairs $(V_i,V_j)$ whose density is less than $\frac{\epsilon}{5}$. The number of such edges is certainly less than $\frac{\epsilon}{5} n^2$
\end{itemize}
In all these stages together we removed $\frac{3}{5}\epsilon n^2 < \epsilon n^2$ edges. Since $G$ is $\epsilon$-far from being triangle-free, $G'$ surely has at least one triangle. Furthermore, because we removed the internal edges, each triangle has its vertices in three distinct partition subsets. Let $(x,y,z)$ be a triangle in $G'$, and let $(V_i,V_j,V_k)$ be the corresponding partition subsets. From the construction of G', we know that:
\begin{itemize}
\item $(V_i,V_j),(V_j,V_k),(V_i,V_k)$ are $\epsilon'$ regular
\item $(V_i,V_j),(V_j,V_k),(V_i,V_k)$ have a density of at least $\frac{\epsilon}{5}$
\end{itemize}
From the Komlos-Simonovits lemma we conclude that there are at least $\delta' |V_i||V_j||V_k|=\delta' \frac{n^3}{k^3}$ triangles in $G'$. From equation (\ref{eq:kbounds2}) we know that G' has at least $\delta' \frac{n^3}{T^3}$ triangles. If we define $\delta=\frac{6\delta'}{T}$ then $G$ has at least $\delta {n \choose 3}$ triangles. Since every triangle of $G'$ is also a triangle of $G$ (We only removed edges), then $G$ has at least $\delta {n \choose 3}$ triangles as required.

\end{proof}

\begin{corollary}

Let G be a graph in the adjacency matrix model. The following algorithm is an one-sided tester for triangle-freeness:
\begin{itemize}
	\item Repeat O($\frac{1}{\delta}$) times:
	\begin{itemize}
		\item If $(v1,v2,v3)$ is a triangle in G: Reject. 
	\end{itemize} % Select a three distinct vertices $v1,v2,v3$
	\item Accept
\end{itemize}

\end{corollary}

\begin{proof}
If $G$ is triangle-free then a triangle will never be found and we return true as required. If $G$ is $\epsilon$-far from being triangle-free, then by the theorem there are at least $\delta {n \choose 3}$ triangles. Therefore:\newline
$Pr[\text{no triangle was found}] \leq (1-\delta)^{O(\frac{1}{\delta})} \leq e^{-c} \leq \frac{1}{3}$\newline
Where c is a constant we choose such that the last inequality holds.
\end{proof}




\end{document}




