\documentclass[11pt]{article}
\usepackage[letterpaper, left=1in, top=1in, bottom=1in, right=1in]{geometry}
\usepackage{verbatim}
\setlength{\parindent}{0in}
\pagestyle{empty}
\begin{document}
\vspace{\fill}
\begin{center}\LARGE
\textsc{Combinatorics}
\par
\textsc{Seminar}
\end{center}
\vspace{\fill}
\begin{center}\LARGE
\textit{The bandwidth conjecture of Bollob\'as and Koml\'os}
\end{center}
\vspace{\fill}
\begin{center}\Large
Mathias Schacht\par
Humboldt University Berlin
\end{center}
\vspace{\fill}
\textbf{Abstract:} The study of sufficient degree conditions, on a given graph~$G$,
which imply that~$G$ contains a particular spanning subgraph~$H$
is one of the central areas in graph theory. A well known
example of such a result is Dirac's theorem. It asserts that any
graph~$G$ on~$n$ vertices with minimum degree at least~$n/2$
contains a spanning, so called Hamiltonian, cycle.


In my talk we discuss related results for graphs~$H$ of bounded maximum degree and small bandwidth.
In particular we show that: \textsl{For all integers~$k$ and~$\Delta$ and $\gamma>0$ there exist a
constant $\beta>0$ such that for sufficiently large $n$ the following holds. If $G$ is an
$n$-vertex graph with minimum degree $\delta(G)\geq((k-1)/k+\gamma)n$, then it
contains a spanning copy of every $k$-chromatic $n$-vertex graph~$H$ with maximum
degree $\Delta(H)\leq\Delta$ and bandwidth ${\rm bw}(H)$ at  most $\beta n$, where
${\rm bw}(H)=\min_{\sigma}\max_{uv\in E(H)}|\sigma(u)-\sigma(v)|$ with the minimum
ranging over all bijections from $V(H)$ to $[n]$.}  This settles a conjecture of Bollob\'as and Koml\'os.
It is known that the minimum degree condition on~$G$ is asymptotically best possible.


The proof is based on Szemer\'edi's regularity lemma and the so called Blow-up lemma. This is joint work with Julia B\"ottcher and Anusch Taraz from TU-M\"unchen.\vspace{\fill}
\begin{center}\Large
Friday, September 28, 2007, 4:00 pm\par
Mathematics and Science Center: W201
\end{center}
\vspace{\fill}
\begin{center}\Large

\end{center}
\vspace{\fill}
\begin{center}\LARGE
\textsc{Mathematics and Computer Science}\par
\textsc{Emory University}
\end{center}
\end{document}