Small subgraphs in the trace of a random walk (Q510343)

Summary: We consider the combinatorial properties of the trace of a random walk on the complete graph and on the random graph \(G(n,p)\). In particular, we study the~appearance of a fixed subgraph in the trace. We prove that for a subgraph containing a cycle, the threshold for its appearance in the trace of a random walk of length \(m\) is essentially equal to the threshold for its appearance in the random graph drawn from \(G(n,m)\). In the case where the base graph is the complete graph, we show that a fixed forest appears in the trace typically much earlier than it appears in \(G(n,m)\).