
\documentclass[11pt]{report}

\usepackage{../../StyleFiles/ksmac}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{../../StyleFiles/cprog}
\usepackage{../../StyleFiles/fullpage-old}
\usepackage{epsfig}
\usepackage{graphics}

\newcommand{\real}{\mathbb{R}}


\def\lectnumb{2}
%---------------------------------------------------------------------------

\shortrep

\lhead[{\bfseries 15-859N\quad HW \lectnumb}]{{\bfseries 15-859N\quad HW \lectnumb}}
\chead[]{}
\rhead[{\bfseries\thepage}]{{\bfseries\thepage}}
\lfoot[]{}
\cfoot[]{}
\rfoot[]{}

\pagestyle{fancy}

\parskip 1ex
\parindent 0mm

\renewcommand{\arraystretch}{1.5}
\def\titledquestion#1#2{\section{Problem: {#1} ({#2} pts.)}}

%----------------------------------------------------------------------


%-----------Danny's Macros-------------

\newcommand{\problem}[1]{\section{#1}\vspace{-1em}}
\newcounter{partnumber}
\newenvironment{parts}{\begin{list}{
%     \arabic{problemnumber}\alph{partnumber}:}{
     (\alph{partnumber})}{
     \usecounter{partnumber} \setlength{\rightmargin}{\leftmargin}}
     \setlength{\itemsep}{.0 in}}{
     \end{list} \vspace*{.0 in}}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcommand{\comment}[1]{}
%---------------------------------------

\begin{document}


\framebox{
\begin{minipage}[t]{\textwidth}
\vspace{1ex}

\begin{center}
{\LARGE\bf  15-859N --- Spectral Graph Theory \\ and Scientific Computing  ---  Fall 2005}\newline
{\large\bf Miller

\vspace{2ex}

Assignment 2 \vspace{1ex}
Due date: Thursday, October 20, 2005.\\
}
\end{center}

\end{minipage}
}%% end framebox

\begin{problem}{Fundamental Eigenvalue for the Tree}

Let $T_n$ denote the balanced tree where each internal node has degree three. Using path embedding
and Rayleigh quotients show that $\lambda_2 = \Theta(1/n)$.

\end{problem}

\begin{problem}{Cockroach Graph}

In class we defined a graph which we called the cockroach graph where the body has length $k$
and each antenna had length $c \cdot k$ for some constant $c$.
There is a natural involution which flip him over, say, $\phi$. Show that that the fundamental vector
for him is odd with respect to $\phi$.

Hint:
Let

\[
\lambda_{even} =  \min_{x^Tj=0,~ x \mbox{ \small even}} ~~\frac{x^T A x}{x^T x}
\]

\[
\lambda_{odd} =  \min_{x^Tj=0,~ x \mbox{ \small odd}} ~~\frac{x^T A x}{x^T x}
\]

and show that $\lambda_{odd} < \lambda_{even}$ by giving smaller upper bound $\lambda_{odd}$ and a
larger lower bound for $\lambda_{even}$.

\end{problem}

\begin{problem}{An Odd Butterfly}

Correction: The original formulation of a butterfly graph did not give what we wanted.
I would like to send this result off to be publish. So, the plan is to make a paper
with all the members of the class who solve this problem. One of the online journals.



In this problem we will define a planar butterfly graph. First make a half of a planar butterfly graph
by taking $k \geq 1$ complete balanced binary
trees each  with $n$ leaves and a $kn$ by $n$ square meshes.
We attach the leaves of the $k$ tree in order along the $kn$ length side of the mesh.

To make the full butterfly we take two half ones and add $k$ new edges to connected the consecutive
roots of the trees together.

The graph has a natural involution, say, $\phi$, that flips over the
butterfly by interchanging the two meshes. The graph has an even
number of nodes, say $2m$.

Show that for sufficiently large $k$ the fundamental vector is even.

Hint: In this case we must show that $\lambda_{odd}$ is bounded from below. We shall use path
embedding arguments.  Rather than embedding the complete graph we will embed the complete bipartite
graph, $K_{m,m}$ where $2m$ is the number of nodes of the butterfly graph.


\end{problem}


\begin{problem}{Isoperimetric number for the mesh}

Show that the Isoperimetric number $q=q(M_n)$ for the $\sqrt{n}$ by  $\sqrt{n}$
mesh is $\Theta(1/\sqrt{n})$.

The upper bound on $q$ is easy. Show a lower bound by using path
embedding arguments.  In particular, compute the isoperimetric number
of the complete graph and use it via path embedding to show a lower
bound of the mesh.

\end{problem}


\end{document}
