The Erdos-Renyi random graph is a network built by connecting pairs of nodes randomly, each pair linked with some fixed probability. Depending on that probability, the network goes through distinct phases: below a threshold, it breaks into many small disconnected pieces; above it, a single giant connected component emerges containing most of the nodes. This paper focuses on random walks on that giant component, meaning imaginary particles that hop from node to neighboring node at random, and studies how long it takes for two such particles to meet or merge across three different regimes of the connection probability, including the critical threshold where the giant component is just barely forming.
The central results show that the expected time for two independent random walkers to meet, starting from either typical or worst-case starting positions, grows proportionally to the number of nodes n in all three regimes studied. This is a clean and unified answer that holds even in the delicate critical and slightly supercritical regimes, where the network structure is highly irregular and existing tools are difficult to apply. The proofs combine careful estimates on the graph structure with comparison inequalities that relate meeting times on one graph to those on simpler reference graphs.
The paper then uses these meeting time results to draw conclusions about the voter model, a classical process where each node holds an opinion and repeatedly adopts the opinion of a randomly chosen neighbor. The key quantity is the coalescence time, meaning how long until all opinion lineages trace back to a single ancestor, which is mathematically linked to random walk meeting times. The authors show that both the coalescence time and the time for the entire network to reach consensus in the voter model also scale linearly with n across all three regimes, giving a remarkably uniform picture of these dynamics on a network that itself changes dramatically with the connection probability.