Random walk on a connected graph is a classic problem in mathematics that can be studied by analyzing

properties of the graph Laplacian matrix L. Important questions include: What are the stationary solutions

(the null vectors of L)? Eigenvalues and eigenvectors of L? And solutions to the heat equation (the matrix

exponential exp(tL))?

In this project we will address the same questions, but replace the random walk model by a model

of interacting particles which are subject to nearest-neighbor interactions. In other words, as long as the

particles are not on adjacent vertices, the random walk rules apply; but if they are adjacent, then a set of

”exclusion” rules takes hold, such as: one particle may not jump to a vertex already occupied by another

particle. Also, particles of the same type are assumed to be indistinguishable.

To analyze this one-species exclusion model requires writing down a 2n-by-2n matrix, where n is the

number of vertices of the graph. How daunting! However, by adopting an orthonormal Fourier basis (that

is frequently used to study Boolean functions), one can show that the matrix is sparse (has lots of 0’s) and

possesses a special block structure. I have worked out all the details, and will teach you the essential results

during the first 2 weeks of the project.

Starting in Week 3, we will tackle the exclusion model involving two species (or ”colors”) of particles.

This leads to a 3n-by-3n matrix, and we will search for a ”nice” orthonormal Fourier basis which yields the

cleanest-looking block matrix. Once this matrix is found, we will proceed to find its eigenvalues, eigenvectors,

and stationary and dynamical solutions. Some of these questions can be answered on general connected

graphs, while others are best answered on d-dimensional lattice graphs or discrete tori (the 1-dimensional

graphs have attracted the most interest).

As we unravel the details of the model together, you will learn fascinating connections of this problem to

analysis, probability, abstract algebra, and combinatorics.

An essential part of this ”laboratory experience” is to train you how to write and communicate math

effectively, including typing math reports using TeX / Overleaf, and giving poster and oral presentations.

Please address all of the above in your application. When applicable, describe your previous experience working on an intellectually challenging project, how you overcame the challenges, and the lessons you learned from that project.

Applications open on 10/03/2023 and close on 02/28/2024

If you have questions, please contact Karyn Belanger (kgbelanger@colgate.edu).