On canonical antichains
On canonical antichains
复制标题
关于规范反链
DOI：
10.1016/j.disc.2007.12.018
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Guoli Ding
中科院分区：
文献类型：
--
作者：
Guoli Ding
一个有良好基础的拟序Q的反链A是正则的，如果对Q的每个理想F，F有无限反链当且仅当F∩A是无穷的。在这篇文章中，我们刻画了具有正则反链的障碍。作为应用，我们证明了在导出子图关系下，有限图类不存在典范反链。相反，这个类确实有一个关于子图关系的规范反链。
An antichain A of a well-founded quasi-order Q is canonical if for every ideal F of Q, F has an infinite antichain if and only if F∩A is infinite. In this paper we characterize the obstructions to having a canonical antichain. As an application we show that, under the induced subgraph relation, the class of finite graphs does not have a canonical antichain. In contrast, this class does have a canonical antichain with respect to the subgraph relation.