Seminars & Colloquia Calendar

Download as iCal file

Discrete Math

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

Abstract:

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).

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.