Friday, February 16, 2018
Time  Items 

All day 

2:00pm 
02/16/2018  2:30pm to 3:30pm A nonbacktracking random walk on a graph is a directed walk with the constraint that the last edge crossed may notbe immediately crossed again in the opposite direction. This talk will give a precise description of the eigenvalues of the transition matrix forthe nonbacktracking random walk when the underlying graph is an ErdosRenyi 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 TaoVu Replacement Principle in a novel context, and showing that partial derandomization may be interpreted as a perturbation, allowing one to apply the BauerFike Theorem. Joint work withKe Wang at HKUST (Hong Kong University of Science and Technology). Location: 