Combinatorics Seminar - Philip Matchett Wood

June 12, 2018
Thursday, June 21, 2018 - 10:20am to 11:15am
Cockins Hall 240
Combinatorics Seminar

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

SpeakerPhilip Matchett Wood (University of Wisconsin)

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

S M T W T F S
 
 
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 
10
 
11
 
12
 
13
 
14
 
15
 
16
 
17
 
18
 
19
 
20
 
21
 
22
 
23
 
24
 
25
 
26
 
27
 
28
 
29
 
30
 
31