Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2506.21929 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918072610193408 |
|---|---|
| author | Abrams, Aaron Landau, Henry Landau, Zeph Pommersheim, James Zaslow, Eric |
| author_facet | Abrams, Aaron Landau, Henry Landau, Zeph Pommersheim, James Zaslow, Eric |
| contents | 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) \mbox{ 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) \mbox{ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_21929 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Evasive Random Walks and the Clairvoyant Demon Abrams, Aaron Landau, Henry Landau, Zeph Pommersheim, James Zaslow, Eric Combinatorics 05C81 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) \mbox{ 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) \mbox{ 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. |
| title | Evasive Random Walks and the Clairvoyant Demon |
| topic | Combinatorics 05C81 |
| url | https://arxiv.org/abs/2506.21929 |