##### Department of Mathematics,

University of California San Diego

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

### Food For Thought Seminar

## Jacob Hughes

#### UCSD

## Random Walks on Colorings of Graphs

##### Abstract:

\indent Given a fixed graph $G$ on $n$ vertices, we can create a random coloring of $G$ in the following way: randomly pick an edge, then randomly pick a color, and then color both endpoints of that edge that color. We can continue this process on a graph that is already colored by simply overwriting any vertices that have already been assigned a color. This gives rise to a random walk on the $2^n$ colorings of $G$, and it is this random walk that we will investigate. The eigenvalues of the transition matrix are known and have a simple form. We discuss these and other quantities as well as several related problems.

### March 10, 2011

### 10:00 AM

### AP&M 7321

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