Endlich beschränkte Homogene Strukturen
Zusammenfassung der Projektergebnisse
Homogene Strukturen werden in mehreren Forschungsgebieten intensiv untersucht: Modelltheorie, universelle Algebra, strukturelle Ramseytheorie, topologische Dynamik und theoretische Informatik. In all diesen Bereichen stellen sie eine wichtige und reichhaltige Quelle für Beispiele und Gegenbeispiele dar. Abzählbare homogene Strukturen entstehen auf natürliche Weise als (bis auf Isomorphie eindeutige) Grenzwerte von Klassen endlicher Strukturen. Oft werden diese Klassen endlicher Strukturen durch das Verbot endlich vieler induzierter Substrukturen beschrieben; diese werden manchmal als Schranken der entsprechenden homogenen Strukturen bezeichnet. Somit sind endlich beschränkte homogene Strukturen (bis auf Isomorphie eindeutig) durch eine endliche Menge endlicher Strukturen gegeben, was diese Strukturen aus Sicht der Kombinatorik und aus Sicht der theoretischen Informatik besonders attraktiv macht. Das Projekt FinHom erforschte endlich beschränkte homogene Strukturen in einem breiten Anwendungsspektrum der Mathematik und theoretischen Informatik. Eines der Ergebnisse des Projekts ist ein überraschender Zusammenhang, bei dem endlich beschränkte homogene Strukturen entscheidend sind, um Resilienzprobleme aus der Datenbanktheorie als valued constraint satisfaction problems (VCSPs) zu formulieren und dann Techniken und Ergebnisse aus der VCSP-Forschung zu nutzen, um die Berechnungskomplexität von Resilienzproblemen zu bestimmen. Dieses Ergebnis wurde von Zaneta Semanišinová, einer durch das Projekt geförderten Doktorandin (in Zusammenarbeit mit Manuel Bodirsky und Carsten Lutz), auf der renommierten Konferenz Logic in Computer Science (LICS 2024) präsentiert. Wir sind zuversichtlich, dass unser Ansatz letztlich die Berechnungskomplexität aller Resilienzprobleme klären wird – eine Herausforderung aus der Datenbanktheorie, die seit über 10 Jahren ungelöst ist. Weitere Resultate wurden im Rahmen des Projektes erzielt zu Themen wie unitären Repräsentationen von Automorphismengruppen abzählbarer Strukturen, Keisler-Maßen, erststufigen asymptotischen Zufallstheorien von Klassen, die durch verbotene Homomorphismen beschrieben werden, und Strukturen, die von primitiven Wirkungen von Sω bewahrt werden.
Projektbezogene Publikationen (Auswahl)
-
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
