Kemeny's constant and random walks (Spring 2019)

For this project, we introduce the idea of Kemeny's constant for a graph. A graph is a structure which consists of objects (vertices) and connections between objects (edges). Graphs can be used to model many mathematical and real world structures and so understanding their nature is important. One method used to explore graphs is through random walks which start at some vertex and pick a random connection at that vertex to move to another vertex, and then repeats. The nature of random walks on a graph is closely tied to the structure of the graph. One important aspect of a random walk is how long we would expect to take to get from a given starting state to a given terminal state. If we average all possible starting and terminal states we get what is known as Kemeny’s constant . It is known that this constant can be studied through the use of the characteristic polynomial of the normalized Laplacian matrix, making this of interest to the field of spectral graph theory.

People

• Jane Breen (PostDoc)

• Steve Butler (Faculty)

• Nicklas Day (Undergrad)

• Colt DeArmond (Undergrad)

• Kate Lorenzen (Grad)

• Haoyang Qian (Undergrad)

• Jacob Riesen (Undergrad)

Pre-requisites

• Linear Algebra (Math 317)

• Experience with graph theory (Math 314) is desirable, but not necessary.

Results

Computing Kemeny's constant for barbell-type graphs, Electronic Journal of Linear Algebra 35 (2019), 583-598.