Intersection Time of Random Walks

vertices, we study the expected time until the traces (the set of visited vertices) of the two random walks intersect and call this parameter the "intersection time". We obtain several results that link the intersection time to the hitting time, the spectral gap or other properties of the transition matrix. As a consequence, we are able to determine the intersection time up to constant factors for many natural graph families including cliques, expanders, hypercubes and grids.