[Discrete-math-seminar] Tomorrow's Colloquium
Michael Pelsmajer
pelsmajer at iit.edu
Mon Mar 2 13:30:17 CST 2009
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
More information about the Discrete-math-seminar
mailing list