Approximately locating an invisible agent in a graph with relative distance queries

In a pursuit evasion game on a finite, simple, undirected, and connected graph $G$, a first player visits vertices $m_1,m_2,\dots$ of $G$, where $m_{i+1}$ is in the closed neighborhood of $m_i$ for every $i$, and a second player probes arbitrary vertices $c_1,c_2,\dots$ of $G$, and learns whether or not the distance between $c_{i+1}$ and $m_{i+1}$ is at most the distance between $c_i$ and $m_i$. Up to what distance $d$ can the second player determine the position of the first? For trees of bounded maximum degree and grids, we show that $d$ is bounded by a constant. We conjecture that $d=O(logn)$ for every graph $G$ of order $n$, and show that $d=0$ if $m_{i+1}$ may differ from $m_i$ only if $i$ is a multiple of some sufficiently large integer.     

All double generalized Petersen graphs are Hamiltonian

The double generalized Petersen graph $DP(n,t)$, $n\ge 3$ and $t\in {\mathbb{Z}}_n?\left\{0\right\}$, $2\le 2t<n$, has vertex-set $\{x_i,y_i,u_i,v_i\mid i\in {\mathbb{Z}}_n\}$, edge-set $\{\{x_i,x_{i+1}\},\{y_i,y_{i+1}\},\{u_i,v_{i+t}\},\{v_i,u_{i+t}\},\{x_i,u_i\},\{y_i,v_i\}\mid i\in {\mathbb{Z}}_n\}$. These graphs were first defined by Zhou and Feng as examples of vertex-transitive non-Cayley graphs. Then, Kutnar and Petecki considered the structural properties, Hamiltonicity properties, vertex-coloring and edge-coloring of $DP(n,t)$, and conjectured that all $DP(n,t)$ are Hamiltonian. In this paper, we prove this conjecture.     

Pruned discrete random samples

Let $X_i,i\in \mathbb{N}$, be independent and identically distributed random variables with values in ${\mathbb{N}}_0$. We transform (‘prune’) the sequence $\{X_1,\dots ,X_n\},n\in \mathbb{N}$, of discrete random samples into a sequence $\{0,1,2,\dots ,Y_n\},n\in \mathbb{N}$, of contiguous random sets by replacing $X_{n+1}$ with $Y_n+1$ if $X_{n+1}>Y_n$. We consider the asymptotic behaviour of $Y_n$ as $n\to \infty$. Applications include path growth in digital search trees and the number of tables in Pitmanʼs Chinese restaurant process if the latter is conditioned on its limit value.     

Minimal solutions of the isometry equation

For a finite vector space $W$ over ${\mathbb{F}}_q$, there are described all the pairs of multisets $\{V_1,\dots ,V_{q+1}\}$ and $\{U_1,\dots ,U_{q+1}\}$ of subspaces in $W$ such that for all $w\in W$ the equality $\left|\{i\mid w\in V_i\}\right|=\left|\{i\mid w\in U_i\}\right|$ holds.