论文标题
拓扑和色数的随机$ε$ - 距离图形图
Topology and chromatic number of random $ε$-distance graphs on spheres
论文作者
论文摘要
给定$ 0 <α\leqπ$，$ε> 0 $和$ n $，我们通过绘制$ n $ i.i.d.在$ d $二维领域上定义随机图。对于$ u $和$ v $之间的地理距离为$ε$ -Close至$α$，每当顶点的均匀随机点以及边缘$ u {\ sim} v $。该模型将距离图概括为球体上的距离图和随机Borsuk图。已知拓扑工具可以为Borsuk图的色差数提供紧密的界限。现在，我们研究了这些拓扑不变的之一，即Lóvasz的邻里复合物的连通性，以结合此随机图模型的色数。我们表明，通常情况下，这种界限的性能很差，但是，它仍然在尺寸上产生一些有用的界限$ d = 1 $和2。
Given $0<α\leqπ$, $ε>0$ and $n$, we define random graphs on the $d$-dimensional sphere by drawing $n$ i.i.d. uniform random points for the vertices, and edges $u {\sim} v$ whenever the geodesic distance between $u$ and $v$ is $ε$-close to $α$. This model generalizes distance graphs on spheres, and also random Borsuk graphs. Topological tools are known to give tight bounds for the chromatic number of Borsuk graphs. We now study the efficiency of one of these topological invariants, namely the connectivity of Lóvasz's neighborhood complex, to bound the chromatic number of this model of random graphs. We show that, in general, this bound performs badly, however, it still produces some useful bounds in dimensions $d=1$ and 2.
