Skip to main content

Mark Kempton (Harvard University)

Wednesday, December 07
11:00 AM
135 TMCB

Title: Variations on Random Walk on Graphs

Abstract: Random walks on graphs are the basis of many algorithms involved in communication and computing theory, and have become a central area of research in graph theory. Many variants of random walks have been studied on graphs. I will give an overview of the theory of random walks on graphs, and describe some of these variants. In particular, there is a growing literature studying non-backtracking random walks on graphs. These are random walks that do not return to the immediately previous vertex in a graph. I will discuss some of my results on non-backtracking random walks on graphs, and give a variant on a classical result from probability.