3 papers
math.LO2025
The random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra
Michael Pinsker, Jakub Rydval, Moritz Schöbi +1
We prove that the random ordered graph is a semi-retract of the canonically ordered atomless Boolean algebra, hereby answering an open question of Bartošová and Scow.
cs.CC2025
New Sufficient Algebraic Conditions for Local Consistency over Homogeneous Structures of Finite Duality
Tomáš Nagy, Michael Pinsker, Michał Wrona
The path to the solution of Feder-Vardi dichotomy conjecture by Bulatov and Zhuk led through showing that more and more general algebraic conditions imply polynomial-time algorithm…
cs.LO2025
The sorrows of a smooth digraph: the first hardness criterion for infinite directed graph-colouring problems
Johanna Brunar, Marcin Kozik, Tomáš Nagy +1
Two major milestones on the road to the full complexity dichotomy for finite-domain constraint satisfaction problems were Bulatov's proof of the dichotomy for conservative template…