Path formation conjecture for vertex-reinforced non-backtracking random walks

Let XX be a vertex-reinforced non-backtracking random walk on a connected finite undirected graph, with reinforcement function W(k)=(1+k)αW(k)=(1+k)^\alpha. Let C={i1,,i}C=\{i_1,\dots,i_\ell\} be a random path as in Proposition 0.1, and let LL denote its length. Path formation conjecture. If α>3\alpha>3, then almost surely there exist such a path CC and k01k_0\geq 1 such that, for every kk0k\geq k_0 and every {1,,L}\ell\in\{1,\dots,L\},

XkL+=i.X_{kL+\ell}=i_\ell.

The conjecture predicts eventual periodic traversal of a single random path; the preceding results establish this behavior in the complete-graph setting, while the general connected-graph case remains open.

Sources & referencesView supporting material

Primary source

Line C. Le Goff and Olivier Raimond, “Vertex reinforced non-backtracking random walks: an example of path formation”, arXiv:1506.01239 (2017).

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.