\documentstyle[12pt]{article} %\documentstyle[12pt,clbiba]{article} %\pagestyle{myheadings} %\markright{{\bf DRAFT 7/8/93}} % Side margins: \oddsidemargin 14pt % Original 53pt \evensidemargin 14pt % Original 53pt \marginparwidth 30pt % Original 90pt \marginparsep 7pt % Original 11pt \marginparpush 5pt % Vertical Spacing: \topmargin 10pt % Original 27pt \headheight 12pt \headsep 10pt % Original 45pt % \topskip = 10pt \footheight 12pt \footskip 25pt % Dimension of Text: \textheight 585pt % Original 505pt \textwidth 431pt % Original 365pt \columnsep 10pt \columnseprule 0pt \raggedbottom % Footnotes: \footnotesep 12pt \skip\footins 10pt plus 2pt minus 4pt \parskip 0pt % Extra vertical space between paragraphs. \parindent 20pt % Width of paragraph indentation. \topsep 0pt % Extra vertical space, in addition to % \parskip, added above and below list and % paragraphing environments. \partopsep 0pt % Extra vertical space, in addition to % \parskip and \topsep, added when user % leaves blank line before environment. \itemsep 0pt % Original .4em % Extra vertical space, in addition to % \parskip, added between list items. \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{definition}[theorem]{Definition} \newtheorem{corollary}[theorem]{Corollary} \newenvironment{example}{\begin{verbatim}}{\end{verbatim}} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\abs}[1]{| #1 |} \newcommand{\qed}{\hfill$\Box$} \def\blackslug{\hbox{\hskip 1pt \vrule width 4pt height 8pt depth 1.5pt \hskip 1pt}} \def\QED{$\Box$} \def\proof{\par\penalty-1000\vskip .5 pt\noindent{\bf Proof\/: }} %\input{psfig} %\includeonly{} \begin{document} %\baselineskip 2.0em %\baselineskip 1.25em \begin{center} {\LARGE {\bf Lecture Notes on an Upper Bound for the Best Cut Quotient from a Vector}}\\ \vspace{.25 in} {\Large Stephen Guattery\\ \vspace{.125 in} Revised 7 May 1996} \end{center} \section{Notation} The following notation conventions are used in these notes: \begin{itemize} \item Capital letters represent matrices and bold lower-case letters represent vectors. For a matrix $A$, $a_{ij}$ denotes the element in row $i$ and column $j$; for the vector ${\bf x}$, $x_i$ denotes the $i^{{\rm th}}$ entry in the vector. \item Various special matrices are represented by the following conventions: The adjacency matrix is denoted $Adj$; the degree matrix is denoted $D$; the Laplacian $D-Adj$ is denoted $A$. The Laplacian is sometimes referred to as the difference Laplacian; the ``sum Laplacian'' will be the matrix $D + Adj = 2\,D - A$, which will be denoted as $B$. \item The notion of Laplacian can be extended to graphs with positive edge weights. In particular, let edge $(i,j)$ have weight $w_{ij}$. The adjacency matrix is modified so that entry $Adj_{ij} = w_{ij}$. The degree of a vertex is defined as the sum of the weights of the incident edges. The definitions for $D$, $A$, and $B$ are as above with respect to these changes. Following Fiedler, we will refer to $A$ in the weighted case as the {\bf generalized Laplacian}. We will refer to $B$ in the weighted case as the generalized sum Laplacian. The Laplacian can be considered as the generalized Laplacian where all edge weights are $1$. \item The vector that has all entries equal to one is denoted as $\vec{1}$. \item $\Delta$ represents the maximum degree of a graph. If the graph has weighted edges, the generalized definition of degree given above applies. \item Let $S$ denote the set of edges forming an edge separator that separates vertex sets $V_1$ and $V_2$. Then \[ q(S) = \frac{|S|}{\min (|V_1|,|V_2|)} \] is called the {\bf cut quotient} for $S$. If the graph has positive edge weights, the size of the cut is replaced by the total weight of the cut in the definition above. \item A vector ${\bf x}$ can be thought of as assigning values to the vertices of a graph $G$. Assume ${\bf x}$ has $k > 1$ distinct values $t_1 < t_2 < \ldots < t_k$, and consider any cut that separates the vertices with values less than or equal to $t_i$ ($i < k$) from those with greater values. Such a cut is called a {\bf threshold cut} based on ${\bf x}$. \end{itemize} \section{Background Notes} The proof below was formulated by Steve Guattery and Gary Miller. It is a different proof of a result from Spielman and Teng's paper {\em Spectral Partitioning Works: Planar Graphs and Finite Element Meshes}, which is currently available as a preprint. This proof is a generalization of Mohar's proof from {\em Isoperimetric Numbers of Graphs} (Journal of Combinatorial Theory, Series B v.47, pp 274--291 (1989)). In particular, the proof has been extended to apply to vectors other than the second eigenvector of the Laplacian at the cost of loosening the bound slightly for certain vectors. It also applies to graphs with positive edge weights. \section{The Proof} \begin{theorem} Let $G$ be a connected graph with positive edge weights on $n$ vertices with generalized Laplacian $A$. For any vector ${\bf x}$ such that ${\bf x}^T \vec{1} = 0$, let $q^*$ be the smallest cut quotient over the cut quotients of all threshold cuts based on ${\bf x}$. Then \[ q^* \leq \sqrt{ 2 \Delta \frac{{\bf x}^T A {\bf x}}{{\bf x}^T{\bf x}}}. \] \end{theorem} \begin{proof} Assume w.l.o.g. that the vertices of the graph are numbered such that the entries of ${\bf x}$ occur in non-increasing order: for $i < j$, $x_i \geq x_j$. Let $B$ be the generalized sum Laplacian as described above. We start with two facts about quadratic terms of generalized Laplacians and sum Laplacians. In the expressions below, let ${\bf z}$ be any real vector. First, the following fact is well known: \begin{equation} {\bf z}^T A {\bf z} = \sum_{(i,j) \in E(G)} w_{ij} \; (z_i - z_j)^2 \label{eq-quad-term} \end{equation} \newpage \noindent Second, \begin{eqnarray} \left({\bf z}^T A {\bf z}\right) \left( {\bf z}^T B {\bf z} \right) & = & \left(\sum_{(i,j) \in E(G)} w_{ij} \; (z_i - z_j)^2 \right) \left( \sum_{(i,j) \in E(G)} w_{ij} \;(z_i + z_j)^2 \right) \nonumber \\ & = & \left( \sum_{(i,j) \in E(G)} \left( \sqrt{w_{ij}} \; |z_i - z_j| \right)^2 \right) \left( \sum_{(i,j) \in E(G)} \left( \sqrt{w_{ij}} \; |z_i + z_j| \right)^2 \right) \nonumber \\ & \geq & \left( \sum_{(i,j) \in E(G)} w_{ij} \; |z_i^2 - z_j^2| \right)^2 , \label{eq-quad-prod} \end{eqnarray} where the third line follows from the Cauchy-Schwarz inequality. It is useful to give a high-level outline of the proof here before proceeding: we have just shown that the product $\left({\bf x}^T A {\bf x}\right) \left( {\bf x}^T B {\bf x} \right)$ provides a connection between ${\bf x}^T A {\bf x}$ (which is expressed in terms of a weighted sum of squares of differences across edges) and a weighted sum of differences of the squares of the values at the ends of edges. The second sum telescopes, and can be neatly divided up in terms of subintervals of the the interval from $x_i$ to $x_j$. This will allow us to break an edge up into a number of pieces corresponding to the number of thresholds (and hence cuts) that it crosses. We will rewrite the last sum in~(\ref{eq-quad-prod}) as a weighted sum of cut quotients to prove the theorem. However, two issues must be addressed: First, the weighted sum will involve cut quotients, which use the size of the smaller shore of the cut as a denominator. Second, any edge that crosses zero is a potential problem for the application of telescoping. In the argument below, we break the contribution of an edge into (positive) contributions for subintervals. For an edge $(i,j)$ crossing the zero point, the sum of the contributions could be bigger than the difference $w_{ij} \; |x_i^2 - x_j^2|$. This could violate the inequalities used to show the upper bound. Therefore it is useful to make two changes: We shift the values of ${\bf x}$ so that $x_{\lceil \frac{n}{2} \rceil} = 0$; and we modify $G$ by breaking any edge that crosses the zero point into two parts, one part from $x_i$ to a vertex with value zero, and one part from the zero vertex to $x_j$; each of these parts is assigned weight $w_{ij}$. The next section shows that these changes don't affect the preceding upper bound much. Let $G'$ be the graph modified as specified in the previous paragraph; $G'$ has Laplacian $A'$. Let ${\bf z}$ be any nonzero vector such that $z_i \geq z_j$ for all $i \lceil \frac{n}{2} \rceil$. Note that for each such edge we have \[ (z_i - z_j)^2 = z_i^2 + z_j^2 - 2 z_i z_j > z_i^2 + z_j^2 = (z_i - 0)^2 + (0 - z_j)^2, \] where the inequality holds because $z_i$ and $z_j$ have opposite signs by our restriction on the ordering of ${\bf z}$ (the edge weight has been factored out of each expression). Thus we have that \begin{equation} \frac{{\bf z}^T A' {\bf z}}{{\bf z}^T {\bf z}} \leq \frac{{\bf z}^T A {\bf z}}{{\bf z}^T {\bf z}} \label{eq-A-prime-1} \end{equation} for any such vector. Now consider the shifted version of ${\bf x}$: Let ${\bf y} = {\bf x} + \alpha \vec{1}$ where $\alpha = -x_{\lceil \frac{n}{2} \rceil}$. We have the following: \[ \frac{{\bf y}^T A {\bf y}}{{\bf y}^T {\bf y}} = \frac{({\bf x}+\alpha \vec{1})^T A ({\bf x}+\alpha \vec{1})} {({\bf x}+\alpha \vec{1})^T ({\bf x}+\alpha \vec{1})} = \frac{{\bf x}^T A {\bf x}}{{\bf x}^T {\bf x} + \alpha^2 n} \leq \frac{{\bf x}^T A {\bf x}}{{\bf x}^T {\bf x}}, \] where the second equality follows from the restriction ${\bf x}^T \vec{1} = 0$ from the theorem statement, and from the fact that $\vec{1}$ is the (simple) zero eigenvalue for any (generalized) Laplacian. Since ${\bf y}$ meets the restrictions on ${\bf z}$ in the preceding paragraph, we can combine this result with inequality~(\ref{eq-A-prime-1}) to get \begin{equation} {\bf y}^T A' {\bf y} \leq \frac{{\bf x}^T A {\bf x}}{{\bf x}^T {\bf x}} \cdot {\bf y}^T {\bf y}.\label{eq-A-prime-2} \end{equation} We can perform a similar analysis for $B'$, the sum Laplacian of $G'$: \[ \frac{{\bf y}^T B' {\bf y}}{{\bf y}^T {\bf y}} \leq \frac{{\bf y}^T B {\bf y}}{{\bf y}^T {\bf y}} = \frac{{\bf y}^T (2 D - A) {\bf y}} {{\bf y}^T {\bf y}} < \frac{{\bf y}^T (2 D) {\bf y}} {{\bf y}^T {\bf y}} \leq \frac{{\bf y}^T (2 \Delta I) {\bf y}} {{\bf y}^T {\bf y}} = 2 \Delta. \] The first inequality follows from the fact that $A'$ is positive semidefinite, and that ${\bf y}$ is not a multiple of the ``all ones'' vector, the only zero eigenvalue of $A'$. The second inequality replaces the degree matrix with $\Delta I$; this follows because the only vertex in $G'$ that could have degree greater than $\Delta$ is $\lceil \frac{n}{2} \rceil$; however, the corresponding entry of ${\bf y}$ is 0 and the inequality holds. We thus have that \begin{equation} {\bf y}^T B' {\bf y} \leq 2 \Delta \cdot {\bf y}^T {\bf y}.\label{eq-B-prime} \end{equation} Combining inequalities~(\ref{eq-quad-prod}),~(\ref{eq-A-prime-2}), and~(\ref{eq-B-prime}), we get \[ 2 \Delta \cdot \frac{{\bf x}^T A {\bf x}}{{\bf x}^T {\bf x}} \cdot \left( {\bf y}^T {\bf y} \right)^2 \geq ({\bf y}^T B' {\bf y}) \; ({\bf y}^T A' {\bf y}) \geq \left( \sum_{(i,j) \in E(G')} w_{ij} \; | y_i^2 - y_j^2 | \right)^2. \] Since only nonnegative values are involved, we can take the square root of the terms above. Further, since no edges cross the zero point, we can rewrite the summation to eliminate the absolute value signs. This gives the following: \begin{equation} \sqrt{2 \Delta \frac{{\bf x}^T A {\bf x}}{{\bf x}^T {\bf x}}} \cdot \left( {\bf y}^T {\bf y} \right) \geq \sum_{\begin{array}{c} (i,j) \in E(G')\\ i < j \leq \lceil \frac{n}{2} \rceil \end{array}} w_{ij} (y_i^2 - y_j^2) \: \: \: + \: \sum_{\begin{array}{c} (i,j) \in E(G')\\ \lceil \frac{n}{2} \rceil \leq i < j \end{array}} w_{ij} (y_j^2 - y_i^2) . \label{eq-final-ub} \end{equation} The rest of the proof essentially follows Mohar's proof; the main distinction is that Mohar only worked with the positive side of the vector he considered. We include both sides of the vector.\footnote{Note that when $x_{\lceil \frac{n}{2} \rceil}$ is the minimum or maximum value of ${\bf x}$, one of the sums on the right hand side of~(\ref{eq-final-ub}) will be zero.} We'll actually only show the proof for the positive part of the vector, however. The argument for the negative half is symmetric and left as an exercise. We need some notation before we can finish the proof. Note that the $y_i$'s may not be distinct. Assume that there are $k$ distinct values in the subvector consisting of entries $y_1$ through $y_{\lceil \frac{n}{2} \rceil}$, and denote them as $t_1 > t_2 > \ldots > t_{k-1} > t_k = 0$. Let $\delta V_i$ be the total weight of the edges $(k,l)$ in $G'$ such that $y_k \geq t_i$ and $y_l < t_i$; that is, $\delta V_i$ is the weight of the edges crossing the cut at threshold $t_i$. Let $V_i = \{j \in V(G') \: | \: y_j \geq t_i \}$ (for simplicity of notation below, let $V_0 = \emptyset$). Finally, let $q_i$ be the quotient cut that separates $V_i$ from the rest of the graph, and let $q^*$ be the minimum quotient cut produced by vector ${\bf y}$. The definition for cut quotient thus can be stated as follows: \begin{equation} q_i = \frac{\delta V_i}{|V_i|}. \label{eq-cut-quot-i} \end{equation} Note that, by the construction of $G'$ and ${\bf y}$, the values for the $q_i$'s and $q^*$ are unchanged if the definitions are applied to $G$ and ${\bf x}$. Consider the following calculation: \begin{eqnarray} \sum_{\begin{array}{c} (i,j) \in E(G')\\ i < j \leq \lceil \frac{n}{2} \rceil \end{array}} w_{ij} \; (y_i^2 - y_j^2) & = & \sum_{i=1}^{k-1} \delta V_i \; (t_i^2 - t_{i+1}^2) \label{eq-final-1}\\ & = & \sum_{i=1}^{k-1} q_i \; |V_i| \; (t_i^2 - t_{i+1}^2) \label{eq-final-2}\\ & \geq & q^* \; \sum_{i=1}^{k-1} |V_i| \; (t_i^2 - t_{i+1}^2) \label{eq-final-3}\\ & = & q^* \; \sum_{i=1}^{k-1} \left( |V_i| - |V_{i-1}| \right) t_i^2 \label{eq-final-4}\\ & = & q^* \; \sum_{i=1}^{\lceil \frac{n}{2} \rceil} y_i^2 .\label{eq-final-5} \end{eqnarray} The first step in deriving equation~(\ref{eq-final-1}) is the application of telescoping: Let $y_i = t_l$ and $y_j = t_m$. Then $y_i^2 - y_j^2 = \sum_{i = l}^{m-1} (t_i^2 - t_{i+1}^2)$. This sum is regrouped with respect to the differences $t_i^2 - t_{i+1}^2$; each such difference is weighted by a factor equal to the weight of the edges crossing that threshold. Equality~(\ref{eq-final-2}) follows by an application of~(\ref{eq-cut-quot-i}). The inequality~(\ref{eq-final-3}) then follows from the definition of $q*$. Equation~(\ref{eq-final-4}) is a reordering of the preceding sum based on noting that $t_i^2$ occurs in~(\ref{eq-final-3}) only in the expressions for $|V_i|$ and $|V_{i-1}|$; recall that $t_k = 0$. Finally, $|V_i| - |V_{i-1}|$ is the number of vertices with value $t_i$; equation~(\ref{eq-final-5}) reintroduces the corresponding values from ${\bf y}$, including any zero values with indices less than or equal to $\lceil \frac{n}{2} \rceil$. As noted before, the argument for the negative half of ${\bf y}$ is symmetric. Combining the two results (remember that $y_{\lceil \frac{n}{2} \rceil} = 0$ and that ${\bf y}^T {\bf y} = \sum_{i=1}^n y_i^2$) and applying~(\ref{eq-final-ub}) completes the proof.\\ \QED \end{proof} %\bibliography{/ump/icase/home30/smg/biblio/ref,/ump/icase/home30/smg/biblio/biblio} \bibliography{/usr0/glmiller/papers/biblio/ref} \bibliographystyle{alpha} \end{document}