Digraph functors which admit both left and right adjoints
arXiv:1304.2204 · doi:10.1016/j.disc.2014.10.018
Abstract
For our purposes, two functors Λ and Γ are said to be respectively left and right adjoints of each other if for any digraphs G and H, there exists a homomorphism of Λ(G) to H if and only if there exists a homomorphism of G to Γ(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.
16 pages, 1 figure
Cited by in corpus (7)
- Improved hardness for H-colourings of G-colourable graphs
- On inverse powers of graphs and topological implications of Hedetniemi's conjecture
- Adjoint functors in graph theory
- Topology and adjunction in promise constraint satisfaction
- Cylindrical Graph Construction (definition and basic properties)
- Iterated Arc Graphs
- Hedetniemi's conjecture and adjoint functors in thin categories