2025/06/27 by Aaron Abrams, H. G. Landau, Abrams, Aaron +7 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #05C81 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2506.21929
openalex publication_date 2025/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A pair of random walks (R,S) on the vertices of a graph G is \it successful if two tokens can be scheduled (moving only one token at a time) to travel along R and S without colliding. We consider questions related to P. Winkler's \it clairvoyant demon problem, which asks whether for random walks R and S on G, Pr[ (R,S) is successful ] >0. We introduce the notion of an \it evasive walk on G: a walk S so that for a random walk R on G, Pr[ (R,S) is successful ]>0. We characterize graphs G having evasive walks, giving explicit constructions on such G. On a cycle, we show that with high probability the tokens must collide quickly. Finally we consider two variants of the problem for which, under certain assumptions on the graph G, we provide algorithms that schedule (R,S) successfully with positive probability.