Functors on relational structures which admit both left and right adjoints

The study of homomorphisms between (di)graphs and general relational structures is of prominent importance in combinatorics and theoretical computer science [\textit{P. Hell} and \textit{J. Nešetřil}, Graphs and homomorphisms. Oxford: Oxford University Press (2004; Zbl 1062.05139); \textit{T. Feder} and \textit{M. Y. Vardi}, SIAM J. Comput. 28, No. 1, 57--104 (1998; Zbl 0914.68075); \textit{A. Krokhin} (ed.) and \textit{S. Živný} (ed.), The constraint satisfaction problem: complexity and approximability, Dagstuhl seminar 15301, July 2015. Wadern: Schloss Dagstuhl -- Leibniz Zentrum für Informatik (2017; Zbl 1375.68019)]. A (thin) functor from the class of structures of some signature to the class of structures of a possibly different signature is a mapping that is monotone with respect to the homomorphism preorder. This paper investigates a kind of homomorphism duality of such functors called \textit{adjunction}. Two functors \(\Lambda,\Gamma\)\ form an adjoint pair if for all relational structures \(\boldsymbol{G},\boldsymbol{H}\)\ of the corresponding signature, \(\Lambda\left( \boldsymbol{H}\right) \) maps homomorphically to \(\boldsymbol{G}\)\ iff \(\boldsymbol{H}\)\ maps homomorphically to \(\Gamma\left( \boldsymbol{G}\right) \), where \(\Lambda \)\ is called a \textit{left adjoint} of \(\Gamma\)\ and \(\Gamma\)\ is called a \textit{right adjoint} of \(\Lambda\). It is clear that left and right adjoints in genuinely categorical sense (the former is called a \textit{left Pultr functor}, while the latter is called a \textit{central Pultr functor}) are so in the above sense. Left Pultr functors and central Pultr functors were described in full by \textit{A. Pultr} [Lect. Notes Math. 137, 100--113 (1970; Zbl 0203.31401)]. This paper studies the problem of characterizing central Pultr functors for arbitrary relational structures that admit a right adjoint, and, for those that do, giving an explicit construction for such an adjoint. The authors give a necessary condition for the existence of such an adjoint (Theorem 2.10), while they give a sufficient condition (Theorem 7.3). There is a gap between them, and it remains open what the necessary and sufficient condition should be (even in the case of digraphs). As far as possible applications of the results in this paper are concerned, the authors go as follows. Left Pultr functors and central Pultr functors can alternatively be described as gadget replacements and pp-constructions, respectively. These two constructions are central to the algebraic theory of complexity of (promise) CSPs, where gadget replacements are used as log-space reductions between (promise) CSPs whose templates are related via pp-constructions [\textit{L. Barto} et al., J. ACM 68, No. 4, Article No. 28, 66 p. (2021; Zbl 1499.68140)]. The opposite type of reduction, where gadgets are replaced by individual constraints, is less common, but has already been shown to be significant [\textit{L. Barto} and \textit{M. Kozik}, in: Proceedings of the 33rd annual ACM-SIAM symposium on discrete algorithms, SODA 2022, Alexandria, VA, USA, both virtually and physically, January 9--12, 2022. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1204--1220 (2021; Zbl 07883631); \textit{A. Krokhin} et al., SIAM J. Comput. 52, No. 1, 38--79 (2023; Zbl 07672224)].

Recommendations

Cites work

This page was built for publication: Functors on relational structures 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 Q6573001)