Activities This Week

In the `80 Diaconis and others have observed that some naturally occurring Markov chains exhibit a cutoff phenomenon: the distance from the stationary distribution drops from almost maximal to almost zero over a short period of time. It is conjectured that all transitive expander graphs exhibit this phenomenon, but so far very few examples are known. I will survey and explain some results on cutoff for walks on Ramanujan graphs and complexes, and their relation to expansion in groups.

In this lecture I will tell the story of a small, anonymous conjecture from an unpublished master’s thesis, that turned out to generalize (a slightly weaker version of) the famous Hanna Neumann conjecture (HNC), which challenged dozens of mathematicians for nearly 60 years. We will discuss the following 3 seemingly unrelated problems: 1. What is the maximal possible rank of the intersection of 2 finitely generated subgroups of a free group? 2. How complicated (in the sense of Euler characteristic) must a graph be in order to contain many copies of another graph? 3. If we substitute random permutations for the letters of some free words so that they generate a random permutation group, how many invariant subsets do we expect to get?

…and what if we replace permutations with random invertible matrices over a finite field? This last question gives rise to a q-analog of the HNC, closing a circle of ideas.