Separation Dimension of Bounded Degree Graphs
Separation Dimension of Bounded Degree Graphs
复制标题
有界度图的分离维数
DOI：
--
复制
发表时间：
2014
影响因子：
0.8
通讯作者：
D. Rajendraprasad
中科院分区：
文献类型：
--
作者：
N. Alon;Manu Basavaraju;L. Chandran;Rogers Mathew;D. Rajendraprasad
图G$的分离维数是使G$的顶点可以嵌入到$mathbb{R}^k$中的最小自然数k$，使得G$中任意一对不相交的边可以被垂直于其中一个轴的超平面分离。等价地，它是$G$的顶点的全序族$mathcal{F}$的最小可能基数，使得对于$G$的任何两条不相交的边，在$mathcal{F}$中至少存在一个全序，其中一条边中的所有顶点都先于另一条边中的顶点。一般情况下，一个图在$n$个顶点上的最大分离维数是$Theta（log n）$。在这篇文章中，我们专注于有界度图，并证明了具有最大度$d$的图的分离维数至多为$2^{9{log^{星星}}！d} d$。我们还证明了上述界是近紧的，通过显示，对于每$d$，几乎所有的$d$-正则图的分离维数至少$ceil{d/2}$。
The separation dimension of a graph $G$ is the smallest natural number $k$ for which the vertices of $G$ can be embedded in $mathbb{R}^k$ such that any pair of disjoint edges in $G$ can be separated by a hyperplane normal to one of the axes. Equivalently, it is the smallest possible cardinality of a family $mathcal{F}$ of total orders of the vertices of $G$ such that for any two disjoint edges of $G$, there exists at least one total order in $mathcal{F}$ in which all the vertices in one edge precede those in the other. In general, the maximum separation dimension of a graph on $n$ vertices is $Theta(log n)$. In this article, we focus on bounded degree graphs and show that the separation dimension of a graph with maximum degree $d$ is at most $2^{9{log^{star}}!d} d$. We also demonstrate that the above bound is nearly tight by showing that, for every $d$, almost all $d$-regular graphs have separation dimension at least $ceil{d/2}$.