  We define a random graph obtained via connecting each point of $\mathbb{Z}^d$
independently to a fixed number $1 \leq k \leq 2d$ of its nearest neighbors via
a directed edge. We call this graph the directed $k$-neighbor graph. Two
natural associated undirected graphs are the undirected and the bidirectional
$k$-neighbor graph, where we connect two vertices by an undirected edge
whenever there is a directed edge in the directed $k$-neighbor graph between
them in at least one, respectively precisely two, directions. In these graphs
we study the question of percolation, i.e., the existence of an infinite
self-avoiding path. Using different kinds of proof techniques for different
classes of cases, we show that for $k=1$ even the undirected $k$-neighbor graph
never percolates, but the directed one percolates whenever $k \geq d+1$, $k
\geq 3$ and $d \geq 5$, or $k \geq 4$ and $d=4$. We also show that the
undirected $2$-neighbor graph percolates for $d=2$, the undirected $3$-neighbor
graph percolates for $d=3$, and we provide some positive and negative
percolation results regarding the bidirectional graph as well. A heuristic
argument for high dimensions indicates that this class of models is a natural
discrete analogue of the $k$-nearest-neighbor graphs studied in continuum
percolation, and our results support this interpretation.
