\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<j$ and
$z_{\lceil \frac{n}{2} \rceil} = 0$.  Then with respect to
equation~(\ref{eq-quad-term}), ${{\bf z}^T A' {\bf z}}$ and
${{\bf z}^T A {\bf z}}$ differ only in the terms for
edges that go from some vertex
$i < \lceil \frac{n}{2} \rceil$ to some vertex
$j > \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}

