\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{Cleaning d-regular graphs with brushes}
\end{center}
\vspace{\fill}
\begin{center}\Large
Pawel Pralat\par
Dalhousie University, Canada
\end{center}
\vspace{\fill}
\textbf{Abstract:} A model for cleaning a graph with brushes was recently introduced. We consider the minimum number of brushes needed to clean d-regular graphs in this model, focusing on the asymptotic number for random d-regular graphs. We use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method to find the (asymptotic) number of brushes needed to clean a random d-regular graph using this algorithm (for fixed d). We further show that for any d-regular graph on n vertices at most n(d+1)/4 brushes suffice, and prove that for fixed large d, the minimum number of brushes needed to clean a random d-regular graph on n vertices is asymptotically almost surely n(d+o(d))/4.

\

(Joint work with Noga Alon and Nick Wormald.)\vspace{\fill}
\begin{center}\Large
Friday, May 2, 2008, 3: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}