When: Sunday, May 1, 10am
Where: Schreiber 309
Speaker: Peleg Michaeli, Tel Aviv University
Title: On the trace of random walks on random graphs
Given a base graph and a starting vertex, we select a vertex uniformly at random from its neighbours and move to this neighbour, then independently select a vertex uniformly at random from that vertex's neighbours and move to it, and so on. The sequence of vertices this process yields is a simple random walk on that graph. The set of vertices in this sequence is called the range of the walk, and the set of edges traversed by this walk is called the trace of the walk.
In this talk, we shall discuss graph-theoretic properties of the trace of a random walk on a random graph. We will show that the trace of a long-enough random walk on a dense-enough random graph typically behaves like a random graph with a similar density. In particular, we will show that if the random graph is dense enough to be typically connected, and the random walk is long enough to typically cover the graph, then its trace is typically Hamiltonian and highly connected.
For the special case where the base graph is the complete graph, we will present a hitting time result, according to which, with high probability, exactly one step after the last vertex has been visited, the trace becomes Hamiltonian.
If time permits, several other results on the trace may be presented.
This is joint work with Alan Frieze, Michael Krivelevich and Ron Peled.
