[Discrete-math-seminar] Tomorrow's Colloquium

[Michael Pelsmajer]

Tomorrow's AM colloquium is by a visitor in discrete mathematics, who
is a candidate for a visiting position next year.  (Let me know if you
would like to meet him.)

-----------------------------------------------
Cleaning Regular Graphs with Brushes and Brooms
3 March, 2009   E1 103  4:40 pm

Pawel Pralat
Department of Mathematics and Statistics
Dalhousie University

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/4(d+o(d)).
-----------------------------------------------

Best,
Michael J. Pelsmajer             http://www.iit.edu/~pelsmaje
Applied Mathematics, E1 Room 206       pelsmajer at iit.edu
Illinois Institute of Technology         (312)567-5344
Chicago, IL 60616