Finitely Bounded Homogeneous Structures
Final Report Abstract
Homogeneous structures are intensively studied in several research fields: model theory, universal algebra, structural Ramsey theory, topological dynamics, and theoretical computer science. In all of the areas mentioned above, they provide an important and rich source of examples and counterexamples. Countable homogeneous structures arise naturally as (up to isomorphism unique) limits of classes of finite structures. Often, these classes of finite structures are described by forbidding finitely many finite substructures; these are sometimes referred to as the bounds of the respective homogeneous structure. Hence, finitely bounded homogeneous structures are (up to isomorphism uniquely) given by a finite set of finite structures, which makes the subject particularly attractive from a combinatorial and from a computer science perspective. The project FinHom explored finitely bounded homogeneous structures in a wide range of application domains in mathematics and theoretical computer science. One of the results of the project is a surprising connection between a central recent research topic from database theory on the one hand, and the theory of valued constraint satisfaction problem on the other hand. In this connection, finitely bounded homogeneous structures play a crucial role to phrase resilience problems from database theory as valued constraint satisfaction problems (VCSPs), to then use techniques and results from VCSPs to determine the computational complexity of resilience problems. This result has been presented at the prestigious conference ˇLogic in Computer Science (LICS 2024) by Zaneta Semanišinová, a PhD student partly funded by the project (joint work with Manuel Bodirsky and Carsten Lutz). We are hopeful that with our approach we will eventually settle the computational complexity of all resilience problems, a challenge from Database theory which remains open for more than 10 years. Other results of the project concern unitary representations of automorphism groups of countable structures, Keisler measures, almost-sure theories of classes described by forbidden homomorphisms, and structures preserved by primitive actions of Sω.
Publications
-
A non-de Finetti theorem for countable Euclidian spaces, preprint
Colin Jahel & Pierre Perruchaud
-
Asymptotic Theories of Classes Defined by Forbidden Homomorphisms, preprint
Manuel Bodirsky & Colin Jahel
-
Complexity Classification Transfer for CSPs via Algebraic Products. SIAM Journal on Computing, 53(5), 1293-1353.
Bodirsky, Manuel; Jonsson, Peter; Martin, Barnaby; Mottet, Antoine & Semanišinová, Žaneta
-
The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems. Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 1-14. ACM.
Bodirsky, Manuel; Semanišinová, Žaneta & Lutz, Carsten
-
Unitary representations of the isometry groups of Urysohn spaces, preprint
Rémi Barritault, Colin Jahel & Matthieu Joseph
-
When invariance implies exchangeability (and applications to invariant Keisler measures), preprint
Sam Braunfeld, Colin Jahel & Paolo Marimon
-
Network satisfaction problems solved by k -consistency. International Journal of Algebra and Computation, 36(02), 121-152.
Bodirsky, Manuel & Knäuer, Simon
-
Stabilizers for Ergodic Actions and Invariant Random Expansions of Non-Archimedean Polish Groups. International Mathematics Research Notices, 2025(9).
Jahel, Colin & Joseph, Matthieu
-
Structures preserved by primitive action of Sω, preprint
Manuel Bodirsky & Bertalan Bodor
-
Temporal Valued Constraint Satisfaction Problems. Accepted for publication in the proceedings in the 50th International Symposium on Mathematical Foundations of Computer Science, Warsaw, 2025
Manuel Bodirsky, Zaneta Semanišinová & Edouard Bonnet
