##### Department of Mathematics,

University of California San Diego

****************************

### Food For Thought Seminar

## Mark Kempton

#### UCSD

## Non-backtracking random walks on graphs

##### Abstract:

Random walks on graphs are well-studied, and numerous results exist relating properties of a random walk on a graph to the spectra of various matrices associated with the graph. Particularly, the eigenvalues of the adjacency matrix of a graph give us information about the rate of convergence of a random walk to its stationary distribution. Less well-understood are non-backtracking random walks, which are random walks with the extra condition that we cannot return to the immediately previous state. These are much harder to analyze in general. A paper of Alon, Benjamini, Lubetzky, and Sodin from 2007 proves that for regular graphs, in most cases a non-backtracking random walk will converge to its stationary distribution more quickly than an ordinary random walk. We will discuss some known results on random walks ways to approach the generalization of these results to non-backtracking random walks.

Sponsor: Graduate Student Association

### March 5, 2015

### 10:00 AM

### AP&M 6218

****************************