Qualitative Representations for Combinatorially De fined Relation Algebras

Abstract

The representation of relation algebras involves partitioning the edges of directed graphs according to the compositional rules of the abstract algebra; in general, the problem is known to be algorithmically undecidable. This thesis considers two less stringent representability concepts: feeble and qualitative representations. These can again be understood through edge colourings of complete directed graphs, but the more flexible conditions provide a more natural combinatorial problem and a comparatively better computational challenge: both qualitative and feeble representability are known to be "only" NP-complete. The combinatorial nature of these weakened representations lends itself to the defi nition of natural families of non-associative relation algebras, algebras determined by the number of different colours that are allowed in any triangle. These form the focus of this thesis. We begin with symmetric algebra cases, for which we offer a detailed classification of qualitative and feeble representation possibilities. There are eight families of these algebras, each indexed by the number of allowed colours, and we report our contributions to a complete characterisation of the qualitative and feeble representations for these. Outcomes vary; notably, every Ramsey algebra is qualitatively representable, and Lyndon algebra representations are linked to combinatorial geometries. As a final combinatorial consideration in the symmetric case, we consider a combinatorially de fined intermediate between feeble and qualitative representations, the Yes-No representations. We obtain a full classi fication in the symmetric case. The antisymmetric case presents a greater challenge due to the more complex combinatorial interactions; there are now 32 families, and the classification program is too broad to achieve a full characterisation. For many cases, we are able to provide complete results, and partial results are provided in all cases, as a base for the future resolution of the classification program.