论文标题
随机最近的邻居图：翻译不变的情况
Random nearest neighbor graphs: the translation invariant case
论文作者
论文摘要
如果$（ω（e））$是一个随机变量（权重）的家族，分配给了$ \ mathbb {z}^d $的边缘，则最近的邻居图是由所有边缘$ \ langle x，y \ rangle $引起的指向图，y \ rangle $ y y $ y $ nimim $ nound $ nound noungy noungy $ nound noungy $也就是说，如果将权重视为边缘长度，则每个顶点指向其最接近的邻居。当权重I.I.D.时，Nanda-Newman引入了最近的邻居图。并且不断分发并证明了该图的无向版本的所有组件都是有限的。我们研究了翻译不变的情况，不同的权重，并证明最近的邻居图不包含双限定的定向路径。与I.I.D.相反情况，我们表明，在这种固定情况下，这些图可以包含一个尺寸的一个或两个无限组件（但不多），而[1，\ infty] $ in Dimension $ \ geq 3 $中的任何$ k \ in [1，\ infty] $中的任何$ k \。后一种结构使用一般过程将特定类别的有向图作为具有不同权重的最近的邻居图，从而表征了所有翻译不变的最近邻居图。我们还讨论了从第一组渗透的地球图和对Chaika-Krishnan合并步行模型的影响的关系。
If $(ω(e))$ is a family of random variables (weights) assigned to the edges of $\mathbb{Z}^d$, the nearest neighbor graph is the directed graph induced by all edges $\langle x,y \rangle$ such that $ω(\{x,y\})$ is minimal among all neighbors $y$ of $x$. That is, each vertex points to its closest neighbor, if the weights are viewed as edge-lengths. Nanda-Newman introduced nearest neighbor graphs when the weights are i.i.d. and continuously distributed and proved that a.s., all components of the undirected version of the graph are finite. We study the case of translation invariant, distinct weights, and prove that nearest neighbor graphs do not contain doubly-infinite directed paths. In contrast to the i.i.d. case, we show that in this stationary case, the graphs can contain either one or two infinite components (but not more) in dimension two, and $k$ infinite components for any $k \in [1,\infty]$ in dimension $\geq 3$. The latter constructions use a general procedure to exhibit a certain class of directed graphs as nearest neighbor graphs with distinct weights, and thereby characterize all translation invariant nearest neighbor graphs. We also discuss relations to geodesic graphs from first-passage percolation and implications for the coalescing walk model of Chaika-Krishnan.
