CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Algorithms, Combinatorics and Optimization Seminar
Philip Matchett Wood
University of Wisconsin-Madison
Title: Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph

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 transition matrix for the non-backtracking random walk when the underlying graph is an Erdos-Renyi random graph on n vertices, where edges present independently with probability p. We allow p to be constant or decreasing with n, so long as np/log 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).

Date: Thursday, January 25, 2018
Time: 3:30 pm
Location: Wean Hall 8220
Note: Before the talk, at 3:10 pm, there will be tea and cookies in Wean Hall 6220.