On infinite-finite duality pairs of directed graphs

DOI10.1007/S11083-012-9278-9MaRDI QIDQ382885zbMATH OpenOpenAlexFDO

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

Publication date 22 November 2013

Published in Order (Search for Journal in Brave)

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

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)

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.

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

Cites work

• Antichains in the homomorphism order of graphs.
• Caterpillar dualities and regular languages
• Duality theorems for finite structures (characterising gaps and good characterisations)
• 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
• On classes of relations and graphs determined by subobjects and factorobjects
• Regular families of forests, antichains and duality pairs of relational structures

Cited in

(6)

• 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
• Duality in Infinite Graphs
• Duplication of directed graphs and exponential blow up of proofs
• Regular families of forests, antichains and duality pairs of relational structures
• Finite duality for some minor closed classes

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)