最近邻图的严格无方向模型 (A strict undirected model for the $k$-nearest neighbour graph)

Let $G=G_{n,k}$ denote the graph formed by placing points in a square of area $n$ according to a Poisson process of density 1 and joining each pair of points which are both $k$ nearest neighbours of each other. Then $G_{n,k}$ can be used as a model for wireless networks, and has some advantages in terms of applications over the two previous $k$-nearest neighbour models studied by Balister, Bollob\'{a}s, Sarkar and Walters, who proved good bounds on the connectivity models thresholds for both. However their proofs do not extend straightforwardly to this new model, since it is now possible for edges in different components of $G$ to cross. We get around these problems by proving that near the connectivity threshold, edges will not cross with high probability, and then prove that $G$ will be connected with high probability if $k>0.9684\log n$, which improves a bound for one of the models studied by Balister, Bollob\'{a}s, Sarkar and Walters too.

翻译：让 $G = G ⁇ n, k} 表示根据密度 1 的 Poisson 进程在一平方块中放置点数, 并加入每对点, 这两点都是相邻的美元。然后, $G ⁇ n, k} 可以用作无线网络的模型, 在应用上比Balister、 Bollob\ {a}s、 Sarkar 和 Walters 所研究的前两个美元近邻模型具有一定的优势, 这几个模型在连通模式阈值上被证明是良好的。但是, 它们的证明并没有直接延伸到这一新模型, 因为现在有可能使美元的不同组成部分的边缘交叉。我们通过证明接近连接阈值, 边缘不会与高概率交叉, 然后证明如果 $>0. 9684\ log n 美元, 美元将会与高概率相关, 从而改善 Balister、 Bollob\ { { a} 、 Sarkar 和 Walters 所研究的模型的绑定值。