The logarithmic localization conjecture for invisible agents on graphs
Statement
Let be a finite, simple, undirected, connected graph of order . A mouse moves along the graph, and a cat probes vertices, receiving relative-distance information that determines the possible mouse positions. The cat can localize the mouse up to distance when it has a strategy guaranteeing that the set of possible mouse positions has graph radius at most at some finite time.
Logarithmic localization conjecture. The cat can localize the mouse up to distance on .
The conjecture extends the paper's constant-distance localization results for bounded-degree trees and square grids. The scale is motivated by the fact that bits suffice to identify one of vertices, while the mouse may move a comparable distance during the time needed to obtain that information.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.