\documentclass[10pt]{article}
\newtheorem{define}{Definition}
%\newcommand{\Z}{{\mathbb{Z}}}
%\usepackage{psfig}

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

% pseudocode package:
\usepackage[noend]{algorithm2e}
\incmargin{1em}
\restylealgo{unboxed}
\linesnumbered
\dontprintsemicolon
\SetArgSty{rm}
\SetTitleSty{textsc}{11pt}
\SetKwComment{Comment}{ // }{}

% custom commands:
\newcommand{\textbi}[1]{\textbf{\textit{#1}}}
\newcommand{\la}{\leftarrow}
\newcommand{\ra}{\rightarrow}
\newcommand{\NL}{\textrm{NL}}
\renewcommand{\L}{\textrm{L}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\Obj}{\textrm{Obj}}
\newcommand{\eps}{\varepsilon}
\newcommand{\La}{\Leftarrow}

\begin{document}
\input{preamble.tex}

%{lecture number}{lecture date}{Ronitt Rubinfeld}{Your name}
\lecture{14}{March 22, 2007}{Ronitt Rubinfeld}{Huy Ngoc Nguyen}

%%%% body goes in here %%%%
\section{First order properties testing:}
First order graph property is a property that can be expressed in the following form:

$\exists u_1, u_2,.... u_k \forall v_1, v_2,.... v_l \underbrace{R(u_1,....,u_k,v_1,.....,v_l)}_{ \textrm{may include } \wedge, \vee, \neg \textrm{ or other logical operations})}$ 


In this lecture, we will show a special case of the following theorem.
\begin{theorem} : Alon, Fischer, Krivilevich and Szegedy\\
	All first order properties of $\exists$, $\forall$ type are testable in adjacent matrix model with queries number independent of n.
\end{theorem}

In fact, recent results have given characterizations of
the graph properties testable in constant time in the adjacency
matrix representation, though we will not  cover those proofs
in lecture.  For example, such properties include all monotone
graph properties.


\subsection{$\Delta$-free testing}
In this lecture, we will consider a case of first order property testing, \\

$\Delta - free$ : $\forall u_1, u_2, u_3 R(u_1,u_2,u_3) = \neg(u_1 ~ u_2 \wedge u_2 ~ u_3 \wedge u_1 ~ u_3)$

\begin{define}
G is "$\eps$-far" from $\Delta$-free if we must add/delete at least $\eps n^2$ edges to make it $\Delta$-free.
\end{define}

\noindent We will present a 1-sided $\Delta$-free tester which has the following behavior:
\begin{enumerate}
\item If G is $\Delta$-free, it PASSES
\item If G is $\eps$-far from $\Delta$-free, it FAILS with constant probability.
\end{enumerate}

\subsection{Regularity}

\begin{define}
	For any pair of disjoint subsets $A,B$ in $V$ s.t $|A|, |B| > 1$.	Let $e(A,B) \la$ number of edges between A and B, {\bf density} $d(A,B) = \frac{e(A,B)}{|A||B|}$.	
\end{define}

\begin{define}
$A,B$ is {\bf "$\gamma$"-regular} if $\forall A' \subset A, B' \subset B$ s.t	
\begin{enumerate}
	\item $|A'| \geq \gamma|A| $
	\item $|B'| \geq \gamma|B| $
	\item $|d(A',B') - d(A,B)| < \gamma$
\end{enumerate}
\end{define}

\begin{lemma}{Szemeredi's Regularity Lemma - will be proved in the next lecture}

$\forall m$  and $\eps > 0$, $\exists$ $\mathcal{T} $(= $\mathcal{T}(m,\eps))$ s.t if $G = (V,E)$ with $|V| > \mathcal{T}$ and $\A$ is equipatition of $V$ into $m$ sets then there exists a equipartition $\mathcal{B}$, a refinement of $\A$ into $\mathcal{K}$ sets ( $m \leq \mathcal{K} < \mathcal{T}$ ) s.t at most $\eps{\left(\stackrel{\mathcal{K}}{2}\right)}$ set pairs that not $\eps$-regular.
\end{lemma}
Note that this is only a theoretical result as the value of $\mathcal{T}$ is normally very large (tower of 2's of length polynomial to $\frac{1}{\eps}$). 

\subsection{Number of triangles in a tripartite graph}

Consider a random tripartite graph $G$ (That is, a graph has a equipartition into 3 sets $V_1$, $V_2$ and $V_3$ s.t there are no internal edges in each subgraph $V_i$ and the probability for each pair of nodes $(u,v)$ from 2 different subgraphs to be an edge is $\eta$) . \noindent For any $(u,v,w)$ s.t $u \in V_1, v \in V_2, w \in V_3$ if we let
\begin{center}
$\sigma_{u,v,w} = \left\{
\begin{array}{l}
\textrm{1 if u,v,w is triangle}  \\
\textrm{0 ow}
\end{array}
\right.
$
\end{center}
\noindent $\Rightarrow E\left[\sigma_{u,v,w}\right] = Pr\left[\sigma_{u,v,w}=1\right] \geq \eta^3$\\
\noindent $\Rightarrow E\left[\Sigma{\sigma_{u,v,w}}\right] = \eta^3(\frac{n}{3})^3$ \\
Therefore, we can expect the number of triangles in a random tripartite graph is $(\eta\frac{n}{3})^3$. In case of regular graphs, the following lemma shows that there are also as many ($\Omega({\eta n}^3)$) triangles. \\

\begin{lemma}
$\forall \eta > 0, \exists \gamma = \gamma^{\Delta}(\eta) < \frac{1}{2}\eta$ $\&$ $\delta \equiv \delta^{\Delta}(\eta) \geq \frac{\eta^3}{16}$ st if $A,B,C$ are disjoint subset of $V$ s.t each pair $\gamma-regular$ with density at least $\eta$ then $G$ contains at least $\delta|A||B||C|$ triangles.
\end{lemma}

\begin{proof}
$A^* \la$  nodes in $A$ with 
\begin{enumerate}
\item at least $(\eta - \gamma)|B|$ neighbors in $B$ and
\item at least $(\eta - \gamma)|C|$ neighbors in $C$.
\end{enumerate}
\begin{claim}
	$|A^*| \geq |A|(1-2\gamma)$	
\end{claim}
\begin{proof} \\
	$|A'| \la$ nodes with less than $(\eta - \gamma)|B|$ nbrs in $B$, consider the pair $(A',B)$: 
\begin{eqnarray*}
	d(A',B) &=& \frac{e(A',B)}{|A||B|} \\
	&\leq& \frac{(\eta - \gamma)|B||A'|}{|A'||B|} \\
	&=& \eta - \gamma \\	
	&\leq& d(A,B) -  \gamma
\end{eqnarray*}
\noindent Therefore, by definition of $\gamma-regular$, 
\begin{center}
	$|A'| < \gamma|A|$
\end{center}
\noindent  Similarly, $A'' \la$ nodes in $A$ width less than $(\eta - \gamma)|C|$ nbrs in $C$, we can show that $|A''| < \gamma|A|$ . \\
  But $A^* = A \setminus (A' \cup A'')$
  $\Rightarrow A^* \geq |A| - 2\gamma|A| = (1-2\gamma)|A|$
\end{proof}

\noindent  For each $u \in A^*$, let $B_u \la$ nbrs of $u$ in $B$ and $C_u \la$ nbrs of $u$ in $C$. \\
  From the definition of $A^*$, $|B_u| \geq (\eta - \gamma)|B|$ and $|C_u| \geq (\eta - \gamma)|C|$. \\
  Since each edge $(y,z)$ between $B_u, C_u$ gives a distinct triangle $(u,y,z)$ 
\begin{eqnarray*}
	e(B_{u},C_{u}) &=& d(B_{u},C_{u})|B_{u}||C_{u}|\\
	               &\geq& (\eta - \gamma)(\eta - \gamma)|B|(\eta - \gamma)|C|\\
	               &\geq& (\eta - \gamma)^3|B||C|
\end{eqnarray*}

\begin{eqnarray*} 
	\textrm{Total number of triangles is} &\geq& (1 - 2\gamma)(\eta - \gamma)^3|A||B||C| \\
														 &\geq& (1 - \eta) \frac{\eta^3}{8}|A||B||C|
\end{eqnarray*}
\end{proof}

\subsection{$\Delta$-free tester}
\begin{theorem}
$\forall \eps$, $\exists \delta$ $(=$ $\delta(\eps))$ s.t $\forall$ $G$ s.t $|V| = n$ and $G$ is $\eps$-far from $\Delta$-free in adjacency matrix model, then $G$ has at least $\delta\left(\stackrel{n}{3}\right)$ distinct triangles.
\end{theorem}

\begin{corollary}
1 sided tester for $\Delta$-free
\begin{itemize}
\item[] Do $O(\delta^{-1}(\eps))$ times
\begin{itemize}
\item[1.] Pick $v_1$, $v_2$, $v_3$.
\item[2.] If $(v_1,v_2,v_3)$ is a triangle, FAIL.
\end{itemize}
\end{itemize}
\end{corollary}
\begin{proof}{Sketch proof for the theorem}

Start with an arbitrary $\frac{5}{3}$-equipartition, use regularity lemma to get equipartition $\left\{V_1,V_2,...,V_{\mathcal{K}}\right\} $ s.t 
\begin{center}
$\frac{5}{3} \leq \mathcal{K} \leq \mathcal{T}$
\end{center}
\noindent use $\eps'$ = $min(\frac{\eps}{5}$, $\delta^\Delta(\frac{\eps}{5}))$ \\
\noindent Let $G' \la G$
\begin{enumerate}
\item Delete all edges intenal to partitions. There are at most $n\frac{\eps n}{5} \leq \frac{\eps n^2}{5}$ such edges .
\item Delete all non-regular pair edges. There are at most $\eps' \left( \stackrel{\mathcal{K}}{2}\right) \left( \frac{n}{\mathcal{K}}\right)^2 \leq \frac{\eps n^2}{10}$ such edges. 
\item Delete edges between low density pair. There are at most $\frac{1}{5} \eps \left( \stackrel{n}{2} \right) \leq \frac{1}{10}\eps n^2$
\end{enumerate}
The total number of removed edges is at most $\frac{2\eps n^2}{5}$, at least $\Omega({\eps n^2})$ violating edges left in $G'$. There must be at least a triangle left in $G'$ whose edges are between pairwise-regular high densities sets. Therefore, there must be much more other triangles remaining (and will be dectected by the tester ).
\end{proof}
\end{document}