Algebraically universal categories of relational structures

Abstract

We study the problem of representability of categories of algebras in categories of relational structures. This is a general framework for a long line of research pertaining to the realisation of algebraic structures in graphs. Drawing inspiration from a combinatorial property of classes of finite graphs known as nowhere density that originates from the work of Nešetřil and Ossona de Mendez, we establish a partial characterisation of those relational categories which are algebraically universal, meaning that they fully embed all categories of algebras. More precisely, we show that the any algebraically universal category of relational structures must necessarily contain subdivided complete graphs of any infinite size. Conversely, we establish that any relational category closed under removal of relations and having this property may be oriented to obtain an algebraically universal category. For the proof of the above, we develop a categorical framework for relational gadget constructions. This generalises existing work on algebraic representability in categories of finite graphs to categories of relational structures of unbounded size.