On canonical antichains |
| |
Authors: | Guoli Ding |
| |
Affiliation: | Department of Mathematics, Louisiana State University, Baton Rouge, LA 70803, United States |
| |
Abstract: | 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. |
| |
Keywords: | Well-quasi-ordering Infinite antichain Subgraph Induced subgraph |
本文献已被 ScienceDirect 等数据库收录! |
|