On infinite-finite duality pairs of directed graphs

Details On infinite-finite duality pairs of directed graphs On infinite-finite duality pairs of directed graphs

2012-03-06

arxiv.org/abs/1203.1257v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On infinite-finite duality pairs of directed graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On infinite-finite duality pairs of directed graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On infinite-finite duality pairs of directed graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-537818