论文标题
影响力范围猜想“几乎被证明”
Sphere of Influence Dimension Conjecture 'Almost Proved'
论文作者
论文摘要
在公制空间中的有限点上的界面图（SIG），每个距离围绕其半径的开放球等于该点与其最近的邻居之间的距离，被定义为这些球的相交图。令$ g $为订单$ n的图表，$没有孤立的顶点。 $ g，$ sig（g）表示的sig-dimension，$被定义为最小可能的$ d $，因此可以将$ g $实现为$ \ mathbb {r}^d，配备有sup-norm的$ \ mathbb {r}^d中的影响范围。 2000年，博耶[E. Boyer，L。Lister和B. Shader，使用Sup-Norm，数学和计算机建模32（2000）1071-1082]提出Sig Dimension conoindure，该图表$$ SIG（G）\ Leq \ Leq \ BigG \ Lceil \ lceil \ frac {2n} 3} \ big big big big big big big y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y y，通过证明$$ sig（g）\ leq \ bigg {\ lfloor} \ frac {2n} {3} {3} \ bigg {\ rfloor} +2。$$
The sphere-of-influence graph (SIG) on a finite set of points in a metric space, each with an open ball centred about it of radius equal to the distance between that point and its nearest neighbor, is defined to be the intersection graph of these balls. Let $G$ be a graph of order $n,$ having no isolated vertices. The SIG-dimension of $G,$ denoted by $SIG(G),$ is defined to be the least possible $d$ such that $G$ can be realized as a sphere of influence graph in $\mathbb{R}^d,$ equipped with sup-norm. In 2000, Boyer [E. Boyer, L. Lister and B. Shader, Sphere of influence graphs using the sup-norm, Mathematical and Computer Modelling 32 (2000) 1071-1082] put forward the SIG dimension conjecture, which states that $$SIG(G)\leq \bigg\lceil \frac{2n}{3}\bigg\rceil.$$ In this paper, we 'almost' establish this conjecture by proving that $$SIG(G)\leq \bigg{ \lfloor}\frac{2n}{3}\bigg{ \rfloor}+2.$$
