Symmetries of graphs and structures that fail to interpret a finite thing

Publikationstyp
Conference Paper
Date Issued
2023
Sprache
English
Author(s)
Barto, Libor  
Bodor, Bertalan
Kozik, Marcin  
Mottet, Antoine  
Theoretische Informatik E-EXK6  
Pinsker, Michael  
TORE-URI
https://hdl.handle.net/11420/42748
Volume
2023-June
Article Number
190687
Citation
Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2023)
Contribution to Conference
38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023  
Publisher DOI
10.1109/LICS56636.2023.10175732
Scopus ID
2-s2.0-85166025758
Publisher
Institute of Electrical and Electronics Engineers Inc.
ISBN
9798350335873
We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theorems from the literature and yield further algebraic invariance properties that must be satisfied in every such graph. Algebraic properties of this kind are tightly connected to the tractability of constraint satisfaction problems, and we obtain new such properties even for infinite countably categorical graphs. We balance these positive results by showing the existence of a countably categorical hypergraph that fails to interpret some finite structure, while still lacking some of the most essential algebraic invariance properties known to hold for finite structures.
Subjects
Constraint Satisfaction Problem
finitely bounded homogeneous structures
loop conditions
DDC Class
510: Mathematics