Mixing of a random walk on a randomly twisted hypercube

We consider `randomly twisted hypercubes’, i.e. random graphs $G^{$ for $nge0$ that can be defined recursively as follows. Let $G}{(0)}$ be a graph consisting of a single vertex, and for $nge1$ let $G^{$ be obtained by considering two independent copies $G}{(n-1,1)}$ and $G^{$ 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.

• Speaker: Zsuzsa Baran (Cambridge)
• Tuesday 20 May 2025, 14:00–15:00
• Venue: MR12.
• Series: Probability; organiser: Perla Sousi.