Digraph functors which admit both left and right adjoints

DOI10.1016/J.DISC.2014.10.018MaRDI QIDQ488275zbMATH OpenOpenAlexFDO

Authors Jan Foniok, Claude Tardif

Publication date 23 January 2015

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

adjoint functorsdigraph functorhomomorphism dualityPultr functor

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Adjoint functors (universal constructions, reflective subcategories, Kan extensions, etc.) (18A40)

Abstract: For our purposes, two functors {Lambda} and {Gamma} are said to be respectively left and right adjoints of each other if for any digraphs G and H, there exists a homomorphism of {Lambda}(G) to H if and only if there exists a homomorphism of G to {Gamma}(H). We investigate the right adjoints characterised by Pultr in [A. Pultr, The right adjoints into the categories of relational systems, in Reports of the Midwest Category Seminar, IV, volume 137 of Lecture Notes in Mathematics, pages 100-113, Berlin, 1970]. We find necessary conditions for these functors to admit right adjoints themselves. We give many examples where these necessary conditions are satisfied, and the right adjoint indeed exists. Finally, we discuss a connection between these right adjoints and homomorphism dualities.

Recommendations

• Adjoint functors and tree duality
• Digraph categories and line digraph functors
• Induction, coinduction, and adjoints
• On the scarcity of contravariant left adjunctions
• Adjunctions of quasi-functors between dg-categories

Cites work

• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• Adjoint functors and tree duality
• Duality theorems for finite structures (characterising gaps and good characterisations)
• Graph powers and graph homomorphisms
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• The right adjoints into the categories of relational systems

Cited in

(7)

• Hedetniemi's conjecture and adjoint functors in thin categories
• Functors on relational structures which admit both left and right adjoints
• Iterated arc graphs.
• scientific article; zbMATH DE number 3851342 (Why is no real title available?)
• Topology and Adjunction in Promise Constraint Satisfaction
• On inverse powers of graphs and topological implications of Hedetniemi's conjecture
• Adjoint functors and tree duality

This page was built for publication: Digraph functors which admit both left and right adjoints

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