Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650018 | Discrete Mathematics | 2009 | 12 Pages |
Abstract
An antichain AA of a well-founded quasi-order QQ is canonical if for every ideal FF of QQ, FF has an infinite antichain if and only if F∩AF∩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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Guoli Ding,