On infinite-finite duality pairs of directed graphs

DOI10.1007/S11083-012-9278-9zbMATH Open1276.05053arXiv1203.1257OpenAlexW2951827106MaRDI QIDQ382885FDOQ382885

Authors: Péter L. Erdős, Claude Tardif, Gábor Tardos 

Publication date: 22 November 2013

Published in: Order (Search for Journal in Brave)

Abstract: The (A,D) duality pairs play crucial role in the theory of general 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 (which is the first one of a series) we start the detailed study of the infinite-finite case. Here we concentrate on directed graphs. We prove some elementary properties of the infinite-finite duality pairs, including lower and upper bounds on the size of D, and show that the elements of A must be equivalent to forests if A is an antichain. Then we construct instructive examples, where the elements of A are paths or trees. Note that the existence of infinite-finite antichain dualities was not previously known.

Full work available at URL: https://arxiv.org/abs/1203.1257

Recommendations

• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• Regular families of forests, antichains and duality pairs of relational structures
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Generalised Dualities and Finite Maximal Antichains
• Many Facets of Dualities

zbMATH Keywords

graph homomorphismconstraint satisfaction problemregular languagesduality pairsgeneral relational structuresnondeterministic finite automaton

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Cites Work

• On classes of relations and graphs determined by subobjects and factorobjects
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• Caterpillar dualities and regular languages
• Antichains in the homomorphism order of graphs.
• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• Regular families of forests, antichains and duality pairs of relational structures

Cited In (6)

• Finite duality for some minor closed classes
• Duplication of directed graphs and exponential blow up of proofs
• Duality in Infinite Graphs
• Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
• No finite-infinite antichain duality in the homomorphism poset of directed graphs
• Regular families of forests, antichains and duality pairs of relational structures

This page was built for publication: On infinite-finite duality pairs of directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q382885)