论文标题
布尔维度和昏暗性：平面覆盖图，零
Boolean dimension and dim-boundedness: Planar cover graph with a zero
论文作者
论文摘要
1989年，Nešet松和Pudlák提出了以下具有挑战性的问题：平面posets是否有限制布尔维度？我们表明，每个带有平面盖图和独特元素的孔位都具有布尔尺寸，最多为$ 13 $。结果，我们能够证明有一个可及性标签方案，其标签由$ \ Mathcal {o}（\ log n）$ bits组成，用于带有单个源的平面挖掘物。最著名的一般平面挖掘方案使用$ \ Mathcal {o}（\ log^2 n）$ bits [Thorup jacm 2004]的标签，并且仍然存在使用$ \ MATHCAL {O}（O}（\ log N）$ bits的标签的方案。布尔维度结果与第二个结果证明，表明具有平面盖图的POSET的维度和独特的最小元素受其标准示例编号的线性函数的界定。但是，维度理论的主要挑战之一是确定维度是否根据具有平面覆盖图的所有POSET的标准示例编号有限。
In 1989, Nešetřil and Pudlák posed the following challenging question: Do planar posets have bounded Boolean dimension? We show that every poset with a planar cover graph and a unique minimal element has Boolean dimension at most $13$. As a consequence, we are able to show that there is a reachability labeling scheme with labels consisting of $\mathcal{O}(\log n)$ bits for planar digraphs with a single source. The best known scheme for general planar digraphs uses labels with $\mathcal{O}(\log^2 n)$ bits [Thorup JACM 2004], and it remains open to determine whether a scheme using labels with $\mathcal{O}(\log n)$ bits exists. The Boolean dimension result is proved in tandem with a second result showing that the dimension of a poset with a planar cover graph and a unique minimal element is bounded by a linear function of its standard example number. However, one of the major challenges in dimension theory is to determine whether dimension is bounded in terms of standard example number for all posets with planar cover graphs.
