Conjecture on limiting pheromone weights and geodesics

Let G=(V,E)\mathcal G=(V,E) be any finite graph with two distinct marked vertices NN and FF. For each edge eEe\in E, let We(n)W_e(n) be its pheromone weight after nn ants, and let a geodesic mean a shortest path from NN to FF in G\mathcal G. The loop-erased and uniform-geodesic ant processes are the two return rules described in the model.

Limiting-weight conjecture. Almost surely, as n+n\to+\infty, for every eEe\in E,

We(n)nχe,\frac{W_e(n)}{n}\to\chi_e,

where (χe)eE(\chi_e)_{e\in E} is a random vector satisfying: for the loop-erased ant process, χe0\chi_e\ne0 almost surely if and only if ee belongs to at least one geodesic from NN to FF; for the uniform-geodesic ant process, χe0\chi_e\ne0 almost surely only if ee belongs to at least one geodesic from NN to FF. Consequently, if the geodesic γ\gamma is unique, then almost surely χe=1eγ\chi_e=\boldsymbol 1_{e\in\gamma} for every eEe\in E in both models.

This gives a precise formulation of geodesic selection through the limiting normalized pheromone weights. The source indicates proofs for particular graph classes, but does not state a resolution of the conjecture for arbitrary finite graphs.

Sources & referencesView supporting material

Primary source

Daniel Kious, Cécile Mailler and Bruno Schapira, “Finding geodesics on graphs using reinforcement learning”, arXiv:2010.04820 (2020).

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.