Skip to content

CSM

Seminar

Multiple random walks in random regular graphs

Cooper, C (Kings College London)
Wednesday 26 March 2008, 16:50-17:20

Seminar Room 1, Newton Institute

Abstract

It was shown that (whp), for $r\ge 3$ the cover time $C_G$ of a random $r$-regular graph $G_r$ is asymptotic to $\theta_r n \ln n$, where $\theta_r=({r-1})/({r-2})$. In this talk we study problems arising from multiple random walks on random regular graphs, and prove the following (whp) results. The time for $k$ independent walks to cover $G_r$ is asymptotic to $ C_G/k$.

For most starting positions, the expected number of steps before any of the walks meet is $\theta_r n/{k\choose 2}$. If the walks can communicate on meeting at a vertex, we show that (for most starting positions) the expected time for $k$ walks to broadcast a single piece of information is asymptotic to $((2 \ln k)/k)\theta_r n$, as $k,n$ tend to infinity.

We also establish properties of walks where particles interact when they meet at a vertex by coalescing or by exploding and destroying each other. As an example, the expected extinction time of $k$ explosive particles ($k$ even) tends to $(2\ln 2) \theta_r n $ as $k$ tends to infinity.

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧