ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a finite, simple, undirected, connected graph of order nn. 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 dd when it has a strategy guaranteeing that the set MiM_i of possible mouse positions has graph radius at most dd at some finite time.

Logarithmic localization conjecture. The cat can localize the mouse up to distance O(log⁡n)O(\log n) on GG.

The conjecture extends the paper's constant-distance localization results for bounded-degree trees and square grids. The O(log⁡n)O(\log n) scale is motivated by the fact that O(log⁡n)O(\log n) bits suffice to identify one of nn 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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.