Boolean Dimension and Tree-Width
Boolean Dimension and Tree-Width
复制标题
布尔维度和树宽度
DOI：
10.1007/s00493-020-4000-9
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
P. Micek
中科院分区：
文献类型：
--
作者：
S. Felsner;T. Mészáros;P. Micek
维数是度量偏序集复杂性的一个重要指标。小尺寸允许简洁的编码。事实上，如果Phas维数d，那么知道是否x ≤yinPit足以检查是否x ≤yin见证实现器的每个d线性扩展。在编码方面，Nešetzanil和Pudlák定义了一个更具表现力的维度版本。一个偏序集P最多有布尔维数，如果可以通过观察x和y在P的元素上的相对位置来决定x ≤ yinP（不一定是线性扩张）。证明了覆盖图具有有界树宽的偏序集具有有界布尔维数。这与以下事实形成对比：存在树宽为3且任意大维度的覆盖图的偏序集。这个结果可能是一个长期的开放问题的解决方案的一步：做平面偏序集有界布尔维数？
Dimension is a key measure of complexity of partially ordered sets. Small dimension allows succinct encoding. Indeed ifPhas dimension d, then to know whetherx≤yinPit is enough to check whetherx≤yin each of the d linear extensions of a witnessing realizer. Focusing on the encoding aspect, Nešetřil and Pudlák defined a more expressive version of dimension. A posetPhas Boolean dimension at mostdif it is possible to decide whetherx≤yinPby looking at the relative position ofxandyin onlydlinear orders on the elements ofP(not necessarilly linear extensions). We prove that posets with cover graphs of bounded tree-width have bounded Boolean dimension. This stands in contrast with the fact that there are posets with cover graphs of tree-width three and arbitrarily large dimension. This result might be a step towards a resolution of the long-standing open problem: Do planar posets have bounded Boolean dimension?
登录
查看更多内容
关于偏集布尔维数的注记
DOI：
--
发表时间：
1989
期刊：
影响因子：
--
作者：
J. Nesetril;P. Pudlák
通讯作者：
P. Pudlák
影响因子：
0.4
作者：
G. Brightwell;P. G. Franciosa
通讯作者：
P. G. Franciosa
比较 Dushnik-Miller 维数、布尔维数和局部维数
影响因子：
0.4
作者：
F. Barrera;Thomas Prag;Heather C. Smith;Libby Taylor;W. T. Trotter
通讯作者：
W. T. Trotter
关于本地呈现的姿势
DOI：
10.1016/0304-3975(90)90125-2
发表时间：
1990
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
G. Gambosi;J. Nesetril;M. Talamo
通讯作者：
M. Talamo
未成年人和维度
DOI：
--
发表时间：
2014
期刊：
J. Comb. Theory B
影响因子：
--
作者：
Bartosz Walczak
通讯作者：
Bartosz Walczak