\documentclass[12pt]{article} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics \textbf{6} (1999), \#R17\hfill} \thispagestyle{empty} \usepackage{latexsym} \parindent 0in \parskip 1.5ex \hsize=6in \textheight 8in %\vsize=8.5in \def\qwert{2^{\tilde O(1/\ep^2)}} \def\bA{{\bf A}} \def\cond{{\rm Cond}} \def\hu{\hat{u}} \def\bC{{\bf C}} \def\bT{{\bf T}} \def\hDD{\hat{{\bf D}}} \def\bM{{\bf M}} \def\bD{{\bf D}} \def\norm{\hbox{Norm}} \def\half{{\textstyle{1\over2}}} \def\bR{{\bf R}} \def\recip#1{{1\over#1}} \def\dij{\hat{d}_{i,j}} \def\vol{{\rm Vol}} \def\for{\hbox{ for }} \def\hT{\hat{T}} \def\bA{{\bf A}} \def\bW{{\bf W}} \def\bhW{\hat{\bW}} \def\hc{\hat{c}} \def\ep{\epsilon} \def\ind{{\rm ind}} \def\hw{\hat{w}} \def\bs{\bar{\sigma}} \def\A{{\cal A}} \def\B{{\cal B}} \def\C{{\cal C}} \def\F{{\cal F}} \def\E{{\bf E}} \def\Ex{{\bf E}} \def\cS{{\cal S}} \def\cP{{\cal P}} \def\cQ{{\cal Q}} \def\ind{{\rm ind}} \def\bn{\bar{n}} \def\bv{\bar{\n}} \def\a{\alpha} \def\b{\beta} \def\d{\delta} \def\D{\Delta} \def\e{\epsilon} \def\f{\phi} \def\g{\gamma} \def\G{\Gamma} \def\k{\kappa} \def\la{\lambda} \def\K{\Kappa} \def\z{\zeta} \def\th{\theta} \def\TH{\Theta} \def\l{\lambda} \def\L{\Lambda} \def\m{\mu} \def\n{\nu} \def\p{\pi} \def\P{\Pi} \def\r{\rho} \def\R{\Rho} \def\s{\sigma} \def\S{\Sigma} \def\t{\tau} \def\om{\omega} \def\OM{\Omega} \def\bigmid{\rule[-3.5mm]{0.1mm}{9mm}} \def\N{{\cal N}} \def\Pr{\mbox{{\bf Pr}}} \def\CG{{\cal G}} \def\CA{{\cal A}} \def\whps{{\bf whp }} \def\whp{{\bf whp}} \def\Prob{{\bf Pr}} \def\he{\hat{\e}} \def\BD{{\bf D}} \def\bW{{\bf W}} \def\bB{{\bf B}} \def\hr{\hat{r}} \def\hR{\hat{R}} \newtheorem{lemma}{Lemma} \newtheorem{theorem}{Theorem} \newtheorem{corollary}{Corollary} \newcommand{\ratio}[2]{\mbox{${#1\over #2}$}} \newcommand{\bbD}[1]{\bar{{\bf D}}^{(#1)}} \newcommand{\gap}[1]{\mbox{\hspace{#1 in}}} \newcommand{\hbD}[1]{\hat{{\bf D}}^{(#1)}} \newcommand{\bTT}[1]{{\bf T}^{(#1)}} \newcommand{\limninf}{\mbox{$\lim_{n \rightarrow \infty}$}} \newcommand{\proofstart}{{\bf Proof\hspace{2em}}} \newcommand{\tset}{\mbox{$\cal T$}} \newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}} \newcommand{\bfm}[1]{\mbox{\boldmath $#1$}} \newcommand{\reals}{\mbox{\bfm{R}}} \newcommand{\expect}{\mbox{\bf E}} \newcommand{\Exp}{\mbox{\bf E}} \newcommand{\card}[1]{\mbox{$|#1|$}} \newcommand{\scaps}[1]{\mbox{\sc #1}} \newcommand{\rdup}[1]{{\mbox{$ \lceil #1 \rceil $}}} \newcommand{\rdown}[1]{{\mbox{$ \lfloor #1 \rfloor $}}} \newcommand{\rt}{\right} \newcommand{\lt}{\left} \newcommand{\re}{\mbox{\rm e}} \newcommand{\setm}{\setminus} \newenvironment{proof}{\noindent{\bf Proof\,}}{\hfill$\Box$} \newtheorem{remark}{Remark} \begin{document} \makeatletter \title{A simple algorithm for constructing Szemer\'edi's Regularity Partition} \author{Alan Frieze\\Department of Mathematical Sciences,\\ Carnegie Mellon University.\\{\small\texttt{alan@random.math.cmu.edu}}\thanks{Supported in part by NSF grant CCR-9530974.} \and Ravi Kannan\\Department of Computer Science,\\ Yale University.\\ {\small\texttt{kannan@cs.yale.edu}}\thanks{Supported in part by NSF grant CCR-9528973.}} \date{\ } \maketitle \begin{center} Submitted: November 25, 1998; Accepted: March 15, 1999. \end{center} \makeatother \begin{abstract} We give a simple constructive version of Szemer\'edi's Regularity Lemma, based on the computation of singular values of matrices.\\ Mathematical Reviews Subject Numbers: 05C85, 68R10. \end{abstract} \section{Introduction} ``Szemer\'edi's Regularity Lemma \cite{Szem} is one of the most powerful tools of (extremal) graph theory''. One can only agree with that opening sentence of the paper by Koml\'os and Simonovits \cite{KS}. It has many, many applications and we refer the reader to this excellent survey. The Regularity lemma is often used to prove the existence of certain objects and if in addition one wants to construct them, then one needs a constructive version of the lemma. This was provided by Alon, Duke, Lefmann, R\"odl and Yuster \cite{ADLRY}. Subsequently, Frieze and Kannan \cite{FK1, FK2} gave a different version and extended it to deal with hypergraphs, (see also Czygrinow and R\"odl \cite{CR}). In this note, we give another construction based on the construction of singular values of matrices. The proofs in \cite{ADLRY, FK1,FK2} are somewhat technical. The result of this paper follows quite easily from a simple lemma relating non-regularity and largeness of singular values. \subsection{Szemer\'edi's Lemma} Let $G=(V,E)$ be a graph with $n$ vertices and let $\bA$ be its adjacency matrix. For a disjoint pair of subsets $A,B\subseteq V$ let $e(A,B)$ denote the number of edges between $A$ and $B$. The {\em density} $d(A,B)$ is defined by $$d(A,B)={e(A,B)\over |A|\,|B|}.$$ A disjoint pair $A,B\subseteq V$ is said to be $\e-regular$ if for {\em every} $X\subseteq A$ with $|X|\geq \e|A|$ and $Y\subseteq B$ with $|Y|\geq \e|B|$, we have $$|d(X,Y)-d(A,B)\,|\leq \e.$$ \begin{theorem}({\bf Szemer\'edi's Regularity Lemma}) \label{szem} For every $\e>0$ and integer $m>0$ there are integers $P(\e,m),Q(\e,m)$ with the following property: for {\em every} graph $G=(V,E)$ with $n\geq P(\e,m)$ vertices there is a partition $\cP$ of $V$ into $k+1$ classes $V_0,V_1,\ldots,V_k$ such that \begin{itemize} \item $m\leq k\leq Q(\e,m)$. \item $|V_1|=|V_2|=\cdots=|V_k|$. \item All but at most $\e k^2$ of the pairs $(V_i,V_j)$ are $\e$-regular. \item $|V_0|\leq \e n$. \end{itemize} \end{theorem} A partition satisfying the second criterion is called {\em equitable}. $V_0$ is called the {\em exceptional} class. Following \cite{Szem}, for every equitable partition $\cP$ into $k+1$ classes we define a number called the {\em index} of $\cP$. $$\ind(\cP)=\frac{1}{k^2}\sum_{1\leq r,s\leq k}d(V_i,V_j)^2.$$ A crucial lemma proved in \cite{Szem} and stated in the following form in \cite{ADLRY} states: \begin{lemma}\label{key1} Fix $k$ and $\g$ and let $G=(V,E)$ be a graph with $n$ vertices. Let $\cP$ be an equitable partition of $V$ into classes $V_0,V_1,\ldots,V_k$. Assume $|V_1|>4^{2k}$ and $4^k>600\g^{-2}$. Given proofs that more than $\g k^2$ pairs $(V_r,V_s)$ are not $\g$-regular (where by proofs we mean subsets $X=X(r,s)\subseteq V_r,\,Y=Y(r,s)=\subseteq V_s$ that violate the $\g$-regularity of $(V_r,V_s)$) we can find in $O(n)$ time an equitable partition $\cP'$ (which is a refinement of $\cP$) into $1+k4^k$ classes, with an exceptional class of cardinality at most $$|V_0|+n/4^k$$ and such that $$\ind(\cP')\geq \ind(\cP)+\g^5/20.$$ \end{lemma} We first describe a procedure for finding a proof that a pair is not $\g$-regular; this will be the central part. Then we complete the algorithm with this procedure on hand using the above lemma. % \subsection{Singular Values} An $m\times n$ matrix $\bA$ has a {\em Singular Value Decomposition} into the sum of rank one matrices, see for example Golub and Van Loan \cite{GVL}. It has many important applications. The first singular value $\s_1$ is defined as $$\s_1(\bA)=\max_{|x|=|y|=1}|x^T\bA y|.$$ This value can be computed with high accuracy in polynomial time \cite{GVL}. It is the square root of the largest eigenvalue of $\bA^T\bA$. For the following lemma, \bW\ is a $p\times q$ matrix with rows indexed by $R$, columns indexed by $C$. We assume that $||\bW||_\infty=\max_{i\in R,j\in C}|\bW(i,j)|\leq 1$. For $S\subseteq R,U\subseteq C$ we let \begin{equation}\label{1} \bW(S,T)=\sum_{i\in S}\sum_{j\in T}\bW(i,j)=x_S^T\bW x_U \end{equation} where $x_S$ is the 0-1 indicator vector of $S$ i.e. $(x_S)_i=1$ iff $i\in S$. Let \bA\ be the adjacency matrix of $G$. Suppose we now have a partition of $V$ into $V_1,V_2,\ldots $ and we wish to check whether $(V_r,V_s)$ form a $\g$-regular pair for some $\g$. We let $R=V_r, C=V_s$ and let $\bA_{r,s}$ be the $R\times C$ submatrix of $\bA$ corresponding to these rows and columns. Let $$d=\frac{1}{|V_r|\,|V_s|}\sum_{i\in V_r}\sum_{j\in V_s}\bA(i,j)$$ be the average of the entries in $A_{r,s}$. Let $\bD$ be the $R\times C$ matrix with all entries equal to $d$. Let $\bW=\bW_{r,s}=\bA_{r,s}-\bD$. Re-phrasing the definition of a regular pair we see that \begin{equation}\label{2} (V_r,V_s)\mbox{ is an $\e$-regular pair iff }|\bW(S,T)|\leq \e|S|\,|T| \end{equation} for all $S\subseteq R,\,|S|\geq \e|R|,\,T\subseteq C,\,|T|\geq \e|C|$. The following lemma relates this all to $\s_1(\bW)$. \begin{lemma}\label{lem1} Let $\bW$ be an $R\times C$ matrix with $|R|=p,|C|=q$ and $||\bW||_\infty\leq 1$ and $\g$ be a positive real. {\bf (a)} If there exist $S\subseteq R,T\subseteq C$ such that $|S|\geq \g p,\,|T|\geq \g q$ and $|\bW(S,T)|\geq \g|S|\,|T|$ then $\s_1(\bW)\geq \g^3\sqrt{pq}$. {\bf (b)} If $\s_1(\bW)\geq \g\sqrt{pq}$ then there exist $S\subseteq R,T\subseteq C$ such that $|S|\geq \g' p,\,|T|\geq \g' q$ and $|\bW(S,T)|\geq \g'|S|\,|T|$ where $\g'=\frac{\g^3}{108}$. Furthermore $S,T$ can be constructed in polynomial time. \end{lemma} \proofstart\\ (a) From (\ref{1}) we see that $$|x_S^T\bW x_T|\geq \g|S|\,|T|\geq \g^3pq.$$ Now let $\xi_S=x_S/|x_S|$ and $\xi_T=x_T/|x_T|$. Then $$|\xi_S^T\bW\xi_T|\geq \g^3pq/(|\xi_S|\,|\xi_T|)\geq \g^3\sqrt{pq}$$ since $|x_S|\leq \sqrt{p}$ and $|x_T|\leq \sqrt{q}$. This proves (a). (b) W.l.o.g. we can choose $x,y$ such that $x^T\bW y\geq \g\sqrt{pq},|x|=1,|y|=1$. Let $\b>0$ ($\b$ will be later set to $3/\g$) and define $\hat{x}$ by $$\hat{x}_i=\left\{\begin{array}{ll} x_i:&\mbox{if }|x_i|\leq \frac{\b}{\sqrt{p}}\\0:&\mbox{otherwise}\end{array}\right.$$ and define $\hat{y}$ by a similar truncation at $\b/\sqrt{q}$. Since $|x|=1$ we see that $I=\{i:\;|x_i|\geq \b/\sqrt{p}\}$ has cardinality at most $p/\b^2$. Let $\bW_1$ be obtained from \bW\ by replacing elements in rows other than $I$ by zero. Then (using the standard inequality that for any vector $a$ and matrix $\bM$, we have $|a^T\bM| \leq |a| ||\bM||_F$, where $||\bM||_F^2$ is the sum of squares of the entries of $\bM$) $$|(x-\hat{x})^T\bW y|=|(x-\hat{x})^T\bW_1y| \leq |x-\hat{x}| ||\bW_1||_F|y|\leq ||\bW_1||_F\leq \frac{\sqrt{pq}}{\b}.$$ By a similar argument we obtain $|\hat{x}^T\bW(y-\hat{y})|\leq \sqrt{pq}/\b$. Thus $$\hat{x}^T\bW\hat{y}=x^T\bW y-(x-\hat{x})^T\bW y-\hat{x}^T\bW(y-\hat{y})\geq (\g-2/\b)\sqrt{pq}.$$ Let $\hat{\g}=\g-2/\b$. Then at least one of $(\hat{x}^+)^T\bW \hat{y}^+,(\hat{x}^+)^T\bW \hat{y}^-, (\hat{x}^-)^T\bW \hat{y}^+$, $(\hat{x}^-)^T\bW \hat{y}^-$ is at least $\hat{\g}\sqrt{pq}/4$. Here $\xi^+$ is obtained from $\xi\in\reals^p$ by putting $\xi^+_i=\max\{0,\xi_i\}$. $\xi^-=-((-\xi)^+)$. Suppose without loss of generality that $(\hat{x}^+)^T\bW \hat{y}^-\geq \hat{\g}\sqrt{pq}/4$. (The proof for the other cases is similar.) We define random subsets $S,T$ as follows: For each $i\in R$, put $i$ in $S$ with probability $\hat{x}_i^+\sqrt{p}/\b$.\\ For each $j\in C$, put $j$ in $T$ with probability $-\hat{y}_j^-\sqrt{q}/\b$. Then $$\E(\bW(S,T))=-(\hat{x}^+)^T\bW \hat{y}^-(\sqrt{pq}/\b^2)\leq -\hat{\g}pq/(4\b^2).$$ Thus there exist $S,T$ such that $\bW(S,T)\leq -\hat{\g}pq/(4\b^2)$. Furthermore, such $S,T$ can easily be constructed in $O(pq)$ time using the method of conditional expectations \cite{Rag} and \cite{S}. Indeed for any $r\in R$ we have $$\E(\bW(S,T))=\E(\bW(S,T)\mid r\in S)\Pr(r\in S)+\E(\bW(S,T)\mid r\not\in S)\Pr(r\not\in S)$$ and fixing $r\in S$ or $r\not\in S$ essentially reduces the size of $R$ by one. Putting $\b=3/\g$ we get $|\bW(S,T)|\geq \g^3pq/108$. We need only verify that $S,T$ are not too small in order to complete the proof of (b). But this follows immediately from $|S|\,|T|\geq |\bW(S,T)|$. \proofend We can combine Lemmas \ref{key1} and \ref{lem1} to make an algorithm for finding an $\e$-regular partition, much as in \cite{ADLRY}. \begin{enumerate} \item Arbitrarily divide the vertices of $G$ into an equitable partition $\cP_1$ with classes $V_0,V_1,\ldots$ $,V_b$ where $|V_i|=\rdown{n/b}$ and hence $|V_0|