Brunar, J. B. (2025, May 23). The sorrows of a smooth digraph: from finite to infinite [Conference Presentation]. The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl, Germany. http://hdl.handle.net/20.500.12708/225264
The Constraint Satisfaction Problem: Complexity and Approximability
en
Event date:
18-May-2025 - 23-May-2025
-
Event place:
Dagstuhl, Germany
-
Keywords:
graph colouring problem; list homomorphism problem; Constraint Satisfaction Problem (CSP); conservative CSP; pseudoloop; primitive positive construction; polymorphism; oligomorphic permutation group
en
Abstract:
As powerful as algebraic methods are for finite-domain CSPs, they exhibit challenges to be generalised for infinite, countably categorical structures.
Rather than lifting the algebraic notions tailored for finite algebras, it is often easier to extend combinatorial constructions to the infinite setting. The broader goal, therefore, is to recast known finite algebraic proofs as combinatorial ones that can then be lifted to the countably categorical case. Pursuing this programme, we overcome previous obstacles to lifting results for digraphs in this context from the finite to the $\omega$-categorical realm -- the strongest lifting results hitherto not going beyond a generalisation of the Hell-Nešetřil theorem for undirected graphs.
Based on joint work with Marcin Kozik, Tomáš Nagy, and Michael Pinsker.
en
Research Areas:
Mathematical and Algorithmic Foundations: 60% Computer Science Foundations: 40%