Digraph functors which admit both left and right adjoints

DOI10.1016/J.DISC.2014.10.018zbMATH Open1305.05087arXiv1304.2204OpenAlexW2015485247MaRDI QIDQ488275FDOQ488275

Authors: Jan Foniok, Claude Tardif 

Publication date: 23 January 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Graph powers and graph homomorphisms
• Adjoint functors and tree duality
• Title not available (Why is that?)
• The right adjoints into the categories of relational systems
• Multiplicative graphs and semi-lattice endomorphisms in the category of graphs
• Duality theorems for finite structures (characterising gaps and good characterisations)

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.
• Title not available (Why is that?)
• 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)