Adjoint functors and tree duality

zbMATH Open1196.05035MaRDI QIDQ3575461FDOQ3575461

Authors Jan Foniok, Claude Tardif

Publication date 27 July 2010

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

zbMATH Keywords

adjoint functorconstraint satisfactiontree duality

Mathematics Subject Classification ID

Trees (05C05) Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40)

Abstract: 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.

Recommendations

• Digraph functors which admit both left and right adjoints
• Duality and Polynomial Testing of Tree Homomorphisms
• Duality pairs and homomorphisms to oriented and unoriented cycles
• Homomorphisms to oriented paths
• Tree dualities for constraint satisfaction

Cited in

(8)

• Interleaved adjoints of directed graphs
• Functors on relational structures which admit both left and right adjoints
• Hedetniemi's conjecture and dense Boolean lattices
• Adjoint-triangle theorems for conservative functors
• Hedetniemi's conjecture and adjoint functors in thin categories
• On cylindrical graph construction and its applications
• scientific article; zbMATH DE number 858784 (Why is no real title available?)
• Digraph functors which admit both left and right adjoints

This page was built for publication: Adjoint functors and tree duality

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