Monotonicity conjecture for simple random walk on growing graphs

Let \bmathbbGt\bmathbb{G}_t and \bmathbbGt\bmathbb{G}'_t be graphs non-decreasing in tt, of uniformly bounded degrees, with \bmathbbGt\bmathbbGt\bmathbb{G}_t\subseteq\bmathbb{G}'_t for every tt. Let \bmathbbYt\bmathbb{Y}_t and \bmathbbYt\bmathbb{Y}'_t be simple random walks on these graph evolutions, both starting from y0y_0. Monotonicity conjecture. If \bmathbbYt\bmathbb{Y}_t is transient, meaning that its sample path almost surely returns to Y0=y0Y_0=y_0 only finitely often, then \bmathbbYt\bmathbb{Y}'_t is also transient. The conjecture is a time-dependent analogue of Rayleigh monotonicity, which gives the claim when the graphs are fixed. Its validity for general growing graphs remains open; the paper notes that bounded degrees are essential to the formulation.

Sources & referencesView supporting material

Primary source

Amir Dembo, Ruojun Huang and Vladas Sidoravicius, “Walking within growing domains: recurrence versus transience”, arXiv:1312.4610 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.