***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Quentin Dubroff (Rutgers)

Thursday Feb 10, 3:00 in Fine Hall 224.

Title: Linear cover time is exponentially unlikely

Proving a 2009 conjecture of Itai Benjamini, we show: For any C,
there is a > 0 such that for any simple random walk on an n-vertex graph G,
the probability that the first Cn steps of the walk hit every vertex of G is
at most exp[-an]. A first ingredient of the proof is a similar statement for
Markov chains in which all transition probabilities are less than a suitable
function of C. Joint with Jeff Kahn.

		----------------------------------

Next week:  Ohad Klein

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)