2012/07/18 by Péter L. Erdős, Dömötör Pálvölgyi, Erdős, Péter L. +5 · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Constraint Satisfaction and Optimization #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1207.4402
openalex publication_date 2012/07/18 · arxiv created 2015/06/03 · arxiv updated 2015/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both side are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the infinite-finite antichain dualities and infinite-finite dualities with trees or forest on the left hand side. This work builds on our earlier papers that gave several examples of infinite-finite antichain duality pairs of directed graphs and a complete characterization for caterpillar dualities.