No finite-infinite antichain duality in the homomorphism poset of directed graphs
Let \(\mathbb{D}\) denote the homomorphism poset of finite directed graphs. An antichain duality is a pair \(\left\langle{\mathcal F},{\mathcal D}\right\rangle\) of antichains of \(\mathbb D\) such that \(({{\mathcal F}\to}) \cup ({\to{\mathcal D}}) = \mathbb D\) is a partition. A generalized duality pair in \(\mathbb{D}\) is an antichain duality \(\left\langle{\mathcal F},{\mathcal D}\right\rangle\) with finite \({\mathcal F}\) and \({\mathcal D}\). (See [\textit{D. Duffus}, \textit{P. L. Erdős}, \textit{J. Nešetřil}, and \textit{L. Soukup}, ``Antichains in the homomorphism order of graphs, Commentat. Math. Univ. Carol. 48, No.\,4, 571--583 (2007; Zbl 1199.06008)], where the study of antichain duality was initiated.) Here the authors give a simplified proof of the Foniok-Nešetřil--Tardif theorem for the special case \(\mathbb D\), which gave full description of the generalized duality pairs in \(\mathbb{D}\). (See [\textit{J. Foniok}, \textit{J. Nešetřil}, and \textit{C. Tardif}, ``Generalised dualities and maximal finite antichains in the homomorphism order of relational structures, Eur. J. Comb. 29, No.\,4, 881--899 (2008; Zbl 1147.05037)].) Although there are many antichain dualities \(\left\langle{\mathcal F},{\mathcal D}\right\rangle\) with infinite \({\mathcal D}\) and \({\mathcal F}\), they can show that there is no antichain duality \(\left\langle{\mathcal F},{\mathcal D}\right\rangle\) with finite \({\mathcal F}\) and infinite \({\mathcal D}\).
- Finite duality for some minor closed classes
- Antichains in the homomorphism order of graphs.
- On infinite-finite duality pairs of directed graphs
- On maximal finite antichains in the homomorphism order of directed graphs
- Generalised Dualities and Finite Maximal Antichains
- Greene-Kleitman's theorem for infinite posets
- On Finite Maximal Antichains in the Homomorphism Order
- From finite posets to chain complete posets having no infinite antichain
- Duality pairs and homomorphisms to oriented and unoriented cycles
- Posets with the maximal antichain property
- A splitting property of maximal antichains
- Antichains in the homomorphism order of graphs.
- Duality and Polynomial Testing of Tree Homomorphisms
- Duality theorems for finite structures (characterising gaps and good characterisations)
- Finite paths are universal
- Generalised Dualities and Finite Maximal Antichains
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- How to split antichains in infinite posets
- scientific article; zbMATH DE number 3650785 (Why is no real title available?)
- On classes of relations and graphs determined by subobjects and factorobjects
- On Finite Maximal Antichains in the Homomorphism Order
- Splitting property in infinite posets
- Universal partial order represented by means of oriented trees and other simple graphs
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- Antichains in the homomorphism order of graphs.
- On Finite Maximal Antichains in the Homomorphism Order
- Finite duality for some minor closed classes
- Generalised Dualities and Finite Maximal Antichains
- On infinite-finite duality pairs of directed graphs
- On maximal finite antichains in the homomorphism order of directed graphs
- Regular families of forests, antichains and duality pairs of relational structures
This page was built for publication: No finite-infinite antichain duality in the homomorphism poset of directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q603883)
