Adjoint functors and tree duality

Details Adjoint functors and tree duality Adjoint functors and tree duality

2008-05-19

arxiv.org/abs/0805.2978v2

Discrete Math. Theor. Comput. Sci., 11(2), pp. 97-110, 2009

Mathematics

Combinatorics

14 pages, 2 figures; v2: minor revisions

Scientific paper

A family T of digraphs is a complete set of obstructions for a digraph H if for an arbitrary digraph G the existence of a homomorphism from G to H is equivalent to the non-existence of a homomorphism from any member of T to G. A digraph H is said to have tree duality if there exists a complete set of obstructions T consisting of orientations of trees. We show that if H has tree duality, then its arc graph delta H also has tree duality, and we derive a family of tree obstructions for delta H from the obstructions for H. Furthermore we generalise our result to right adjoint functors on categories of relational structures. We show that these functors always preserve tree duality, as well as polynomial CSPs and the existence of near-unanimity functions.

Affiliated with

Also associated with

No associations

Rating

Adjoint functors and tree duality 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 Adjoint functors and tree duality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adjoint functors and tree duality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-299528