.png){kind=icon}
返回
Cliquewidth and dimension
.png){kind=icon}
PRE
AI
DOI：10.1112/plms.70116.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们证明了每个具有有界团宽度和足够大维度的偏序集都包含一个作为子偏序集的标准维数示例。这特别适用于覆盖图具有有界树宽度的偏序集，因为偏序集的团宽度在覆盖图的树宽度的某种意义下是有界的。对于后一种偏序集，我们证明了更强的陈述：每个具有足够大维度的此类偏序集都包含一个作为子偏序集的凯利维数示例。利用这一结果，我们获得了关于极小闭图类的完全刻画，使得覆盖图在该类中的偏序集具有有界维度：这些类恰好是排除某些凯利示例的覆盖图的类。最后，我们考虑偏序集维度的一个变体，称为布尔维度，并证明具有有界团宽度的偏序集具有有界的布尔维度。证明依赖于Colcombet的确定性版本的Simon因子分解定理，这是形式语言和自动机理论中的一个基本工具，我们认为它在结构图论和算法图论中值得更广泛的认可。
Keyword:
GRAPHS
查看更多机构
.png){kind=icon}
