Seminars & Colloquia Calendar
Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph
Phil Wood, Wisconsin
Location: Hill 705
Date & time: Monday, 22 October 2018 at 2:00PM - 3:00PM
A non-backtracking random walk on a graph is a directed walk with the constraint that the last edge crossed may not be immediately crossed again in the opposite direction. This talk will give a precise description of the eigenvalues of the adjacency matrix for the non-backtracking walk when the underlying graph is an Erdos-Renyi random graph on n vertices, where each edge is present independently with probability p. We allow p to be constant or decreasing with n, so long as p*sqrt(n) tends to infinity. The key ideas in the proof are partial derandomization, applying the Tao-Vu Replacement Principle in a novel context, and showing that partial derandomization may be interpreted as a perturbation, allowing one to apply the Bauer-Fike Theorem.
Joint work with Ke Wang at HKUST (Hong Kong University of Science and Technology).