Jan. 25, 3:30pm, Wean 8220

Philip Matchett Wood, University of Wisconsin-Madison

Limiting eigenvalue distribution for the non-backtracking matrix of an Erdos-Renyi random graph

Philip Matchett Wood, University of Wisconsin-Madison

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

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.