Talks.cam

Mixing of a random walk on a randomly twisted hypercube - Zsuzsa Baran (Cambridge)
2025-05-20 13:00 - 14:00 UTC | MR12
We consider `randomly twisted hypercubes', i.e.\ random graphs $G^{(n)}$ for $n\ge0$ that can be defined recursively as follows. Let $G^{(0)}$ be a graph consisting of a single vertex, and for $n\ge1$ let $G^{(n)}$ be obtained by considering two independent copies $G^{(n-1,1)}$ and $G^{(n-1,2)}$ of $G^{(n-1)}$ and adding the edges corresponding to a uniform random matching between their vertices.
We study a lazy or simple random walk on these and in both cases establish that their mixing times are of order $n$ and they do not exhibit cutoff. In this talk I hope to have enough time to discuss this model and the results and also present most of the ideas of the proofs.
Joint work with An{\dj}ela \v{S}arkovi\'c; based on a joint work with Jonathan Hermon, An{\dj}ela \v{S}arkovi\'c, Allan Sly and Perla Sousi.
