ON THE TRACE OF RANDOM WALKS ON RANDOM GRAPHS USING POISSON (Λ)-GALTON-WATSON TREE

Given a base graph and a starting vertex, we select a vertex uniformly at random from its neighbors and move to this neighbor, then independently select a vertex uniformly at random from that vertex's neighbors 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 edges traversed by this walk is called the trace of the walk, and we consider it as a sub graph of the base graph. In this talk, we shall discuss graph-theoretic properties of the trace of a random walk on a random graph. 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. Finally, we will present results concerning the appearance of small sub graphs in the trace. The speed of random walks and dimension of harmonic measure on a Poisson (Lambda)-Galton-Watson tree. Analogous consequences are specified for graphs with arranged degree sequence, where cutoff is shown both for the simple and for the non-backtracking random walk.