# Combinatorics Seminar

When: Sunday, May 1, 10am

Where: Schreiber 309

Speaker: Peleg Michaeli, Tel Aviv University

Title: On the trace of random walks on random graphs

## Abstract:

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.

redesigned by barak soreq