% Begin of the document
% Comments begins with ``%''
\documentclass[12pt,a4paper]{article}

% This example ``paper.tex'' can be translated in Postsrcipt format as follows:
% 1. Translate in "paper.dvi" by "latex paper.tex"
% 2. Generate references  using "bibtex paper.tex"
%    (only if references have been changed)
% 3. Execute "latex paper.tex" once more
% 4. Generate ps-file "paper.ps" by "dvips paper.dvi" 

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

% Increase tex widht and heigh by 4cm
\addtolength{\textwidth}{4cm}
\addtolength{\oddsidemargin}{-2cm}
\addtolength{\textheight}{4cm}
\addtolength{\topmargin}{-2cm}


% Following packages are included:
\usepackage{graphics} % commands related to graphics 
\usepackage{amssymb} % mathematical symbols
%\usepackage{ngerman} % german language support
\usepackage[latin1]{inputenc} 

% allocate space for picutres :o)
\renewcommand{\textfraction}{0.0}
\renewcommand{\topfraction}{1.0}
\renewcommand{\bottomfraction}{1.0}

% defintion of so-called ``theorem environments'' (see example bellow) 
\newtheorem{theorem}{Theorem} % 'theorem' introduces a theorem. The first
                              %  theorem will be called ``Theorem 1''.
                              %  The number of any subsequent theorem will be
                              %  increased automatically
                       
\newtheorem{lemma}{Lemma}[section] % numbering of lemmas with regard to 
                                   % to the section of appearance
              
\newtheorem{definition}[lemma]{Definition} % nubering of definitions 
                                           % in the same way as lemmas.

% ... proof envirnoment.
\newenvironment{proof}{\noindent\textbf{Proof}}{\mbox{}\hfill
    \makebox[0pt][l]{$\sqcup$}$\sqcap$\par\vspace{1ex}}

% User defined shortcuts....
%
\newcommand{\Po}{\mathrm{Po}}
\newcommand{\Bi}{\mathrm{Bi}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\G}{{\cal G}}
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}

% Headline
%\pagestyle{headings}

%---------------------------------------------------------------
% Begin of the main part of the document (the end of this part
% is marked by `\end{document}').
%
\begin{document}

\title{%
   {\large Proseminar Randomisierte Methoden}\\[1ex]
   A Simple Proof for the $k$--core Threshold}
\author{ Ulrich Voll}
\maketitle
\abstract{In dieser Arbeit wird XYZ vorgestellt. Dies hier
ist eine kurze Zusammenfassung des Inhalts.}

%Introducing the table of contents.
\newpage
\tableofcontents

\newpage
\section{Introduction}

% The references may be found in  `paper.bib'. See last lines before
% `\end{document}' and the file `apaper.bib'.
Pittel, Spencer and Wormald have shown in \cite{PittelSpencerWormald/96}
that the probability for a random  ...

... terminology and
give a short exposition of the subject of
phase transitions for random graphs in Section~\ref{ptarg}.
Section~\ref{poles} deals with the poles, note the discussion
of the south pole in Subsection~\ref{southpole}.
In Section~\ref{figures} we explain stuff concerning
pictures in the text. Section~\ref{DLP} demonstrates
the proof environments.

\section{Phase Transitions and Random graphs} \label{ptarg}

The Gibbs measure is the (appropriately defined) limit of the
Boltzmann distribution for a given finite size Hamiltonian,
when the volume goes to infinity. The system under consideration and thus
the Hamiltonian is assumed to be homogenous, i.e.\ to `look the same'
from every point in space, which is usually achieved by assuming
${\mathbb Z}^d$ symmetry.
Just think about ...

\section{The Poles} \label{poles}
\subsection{The North Pole}
Eine numerierte\footnote{Nach der Rechtschreibreform heißt es
übrigens jetzt "`nummerierte"' statt "`numerierte"'.} Gleichung
sieht folgendermassen aus:
\begin{equation}
A = \left( \begin{array}{ccc}
           1 & 2 & 3 \\
           7 & 5 & 3 \\
           1 & 2 & 8
           \end{array} \right)        \label{schoenegleichung}
\end{equation}
Aus der Gleichung (\ref{schoenegleichung}) sieht man, daß $A$
eine Matrix ist.

Weiter könnten wir uns überlegen, Werte $a_1,a_2,\ldots,a_n$
miteinander zu multiplizieren und durch $\sum_{i=1}^m b_i$ zu
teilen. Das sähe dann wohl so aus (nicht numeriert):
\[
\frac{a_1 \cdot a_2 \cdots a_n}{b_1+b_2+\cdots+b_m} = 42
\]
Auch mehrere Gleichungen untereinander sind manchmal nützlich:
% mit Numerierung; ohne Numerierung muesste man "eqnarray*" nehmen
\begin{eqnarray}
u & = & 24 + 37 \label{eq:abc}\\
u + v & = & 417 - u \label{eq:xyz}
\end{eqnarray}
Was folgt denn jetzt aus (\ref{schoenegleichung}),
(\ref{eq:abc}) und (\ref{eq:xyz})?

\subsection{The South Pole} \label{southpole}

\section{Figures in the Text} \label{figures}

%% Including graphics
\begin{figure}[ht]
\begin{center}
  % Include EPS file qkcore.eps ,rotate it by 270 grad and scale 
  % it by 0.6
  \scalebox{0.6}{\rotatebox{270}{\includegraphics{qkcore.eps}}}
  %
  % EPS files may be generated, for example, using `xfig'
  %
\end{center}
  \caption{The curves $c\mapsto q^{\mathrm{Caley}}_r(c)$ for $r=5,10,15$.
\label{qkcorerfigure}}
\end{figure}

Look at Figure~\ref{qkcorerfigure}! Sometimes we want an
empty figure, just to draw our own picture by hand (cf.\
Figure~\ref{emptypicture}). However, note that
there are tools for producing commutative diagrams in
the AMS Latex package.

\begin{figure}[!ht]
\begin{center}
\vspace{7cm}
\end{center}
  \caption{An empty figure for your own drawings.
\label{emptypicture}}
\end{figure}

\section{Some Definitions, Lemmas and Proofs} \label{DLP}
The branching--tree analogy as explained in \cite{PittelSpencerWormald/96}
inspired us to studying the random variable $Z$ that counts the appearance
of {\em Caley--trees} in a branching--tree. All balls and trees will be assumed to have a fixed radius~$r$
and all objects including the underlying probability spaces
may (and will) depend on $n$, $r$ and $c$, even if not explicitly stated.

\begin{definition}
A Caley tree is a balanced tree such that all non--leaves have degree~$3$.
It has $3 \cdot 2^{r-1}-2$ inner nodes including the root,
a total of $3 \cdot 2^{r}-2$ nodes and $3 \cdot 2^{r}-3$ edges.
\end{definition}

Note the following constructive asymptotic characterisation of
Poisson--$c$--branching--trees:

\begin{itemize}
\item Start with  the complete $n$--ary tree of radius~$r$.
\item Perform independent edge percolation with probability $c/n$.
\item Delete  all nodes that are not connected to the root.
\end{itemize}

From this ${\mathbb E}[Z]$ can be calculated by
counting trees.


\begin{lemma}\label{ballconclemma}
Given $c>1$ for any $0<\varepsilon<0.029 <{e^{-2/3\,{\frac {{e^{5/3}}}{c}}}}$
in a GW branching tree with $Z_0\equiv 1$
and $Z_1\sim \Po_c$
$${\mathbb P}[Z_r \ge 1/2 \log(1/\varepsilon) (3 c)^r] \le r \varepsilon, $$
for all $r \in {\mathbb N}$.
\end{lemma}

\begin{proof} of Lemma~\ref{ballconclemma}.
Proofs are not easy.
\end{proof}

\begin{theorem}
Um den Seminarschein zu bekommen, muß man einen Vortrag halten und
eine Ausarbeitung schreiben. Die Ausarbeitung muß rechtzeitig
abgegeben werden.
\end{theorem}

%----------------------------------
% References
%----------------------------------
\bibliographystyle{alpha}  % try `plain' or 'abbrv' instead of 'alpha'
\bibliography{ausarbeitung} % references are in the file "paper.bib"
\end{document}
