\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{ngerman}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{13}
\newcommand{\ABGABEDATUM}{bis zum 30. Januar 2017, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\eps}{\varepsilon}
\newcommand{\E}{\mathbf{E}}
\DeclareMathOperator{\NN}{NN}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\VD}{VD}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Randomisierte Algorithmen}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Paul Seiferth, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm
\noindent


\begin{description}

\AUFGABE{Graphen und Eigenwerte}{10 Punkte}

Sei $G = (V, E)$ ein $d$-regul\"arer ungerichteter
Graph mit $n$ Knoten. Sei $A$ die Random-Walk Matrix von
$G$.

\begin{enumerate}
  \item Angenommen, $G$ ist zusammenh\"angend.    
    Zeigen Sie: $-1$ ist Eigenwert von $A$ 
    genau dann, wenn $G$ bipartit ist.
    Was k\"onnen Sie \"uber die Vielfachheit von $-1$ sagen?
  \item Zeigen Sie: Die Vielfachheit des Eigenwerts $1$ ist
    genau die Anzahl der Zusammenhangskomponenten von $G$.
\end{enumerate}

\AUFGABE{Expandervermischungslemma}{10 Punkte}

Sei $G = (V, E)$ ein zusammenh\"angender $d$-regul\"arer ungerichteter
Graph. 
Sei $S, T \subseteq V$. Zeigen Sie, dass
\[
  \left\vert |E(S,T)| - \frac{d}{n}|S||T| \right\vert \leq d\lambda(G)  
     \sqrt{|S||T|}
\]
ist.
Interpretieren Sie das Ergebnis.

\emph{Hinweis}: Sei $A$ die Random-Walk Matrix f\"ur $G$. Seien
$\lambda_1 = 1$,  
$\lambda(G) = |\lambda_2| \geq |\lambda_3| \geq \dots \geq |\lambda_n|$
die Eigenwerte von $A$. Sei $\vec{z}_1, \dots, \vec{z}_n$ eine zugeh\"orige
orthonormal-Basis von Eigenvektoren. Zeigen Sie zun\"achst, dass
$A = \sum_{i=1}^n \lambda_i \vec{z}_i \vec{z}_i^T$ ist. Seien
dann $\vec{s}$ und $\vec{t}$ die charakteristischen
Vektoren  von $S$ und $T$. 
Zeigen Sie, dass $|E(S, T)| = d \cdot \vec{s}^T A\, \vec{t}$ ist.
Benutzen Sie die
Darstellung von $A$ und Ihr Wissen \"uber das Spektrum von $A$, um
das Ergebnis zu erhalten.
Die 
\emph{Cauchy-Schwarz-Ungleichung} k\"onnte n\"utzlich sein:
\[
\sum_{i=1}^n |a_ib_i| \leq 
\sqrt{\sum_{i = 1}^n a_i^2} \cdot \sqrt{\sum_{i=1}^n b_i^2 }.
\]

\AUFGABE{Satz von Courant-Fisher}{10 Punkte}

Beweisen Sie den Satz von Courant-Fisher. Sei $A \in \R^{n \times n}$ eine
reelle und symmetrische Matrix. Seien $\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_n$
die Eigenwerte von $A$ (mit Wiederholungen), und sei $v_1, v_2, \dots, v_n$ eine
zugh\"orige Orthonormalbasis von Eigenvektoren.
Dann gilt f\"ur $k = 1, \dots, n$:
\[
  \lambda_k = \max_{\substack{w \in \R^n\\ \| w \| = 1, w \perp v_1, \dots, v_{k-1}}} w^T A w
\]
\end{description}
\end{document}

