3 papers
math.RA2026
The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms
Manuel Bodirsky, Moritz Jahn, Simon Knäuer +2
Andréka and Maddux classified the relation algebras with at most 3 atoms, and in particular they showed that all of them are representable. Hirsch and Cristiani showed that the ne…
math.LO2026
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction
Michael Pinsker, Jakub Rydval, Moritz Schöbi +2
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain wel…
math.CO2025
Circular Chromatic Numbers, Balanceability, Relation Algebras, and Network Satisfaction Problems
Manuel Bodirsky, Santiago Guzmán-Pro, Moritz Jahn +2
In this paper, we characterize graphs with circular chromatic number less than 3 in terms of certain balancing labellings studied in the context of signed graphs. In fact, we const…