Monadic NIP in monotone classes of relational structures
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10489761" target="_blank" >RIV/00216208:11320/24:10489761 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-029" target="_blank" >https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-029</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.5817/CZ.MUNI.EUROCOMB23-029" target="_blank" >10.5817/CZ.MUNI.EUROCOMB23-029</a>
Alternative languages
Result language
angličtina
Original language name
Monadic NIP in monotone classes of relational structures
Original language description
We prove that for any monotone class of finite relational structures, the first-order theory of the class is NIP in the sense of stability theory if, and only if, the collection of Gaifman graphs of structures in this class is nowhere dense. This generalises results previously known for graphs to relational structures and answers an open question posed by Adler and Adler (2014). The result is established by the application of Ramsey-theoretic techniques and shows that the property of being NIP is highly robust for monotone classes. We also show that the model-checking problem for first-order logic is intractable on any monotone class of structures that is not (monadically) NIP. This is a contribution towards the conjecture that the hereditary classes of structures admitting fixed-parameter tractable model-checking are precisely those that are monadically NIP.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA21-10775S" target="_blank" >GA21-10775S: Ramsey theory in the context of group theory, model theory and topological dynamics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and Applications EUROCOMB’23
ISBN
978-80-280-0344-9
ISSN
2788-3116
e-ISSN
—
Number of pages
6
Pages from-to
210-215
Publisher name
Masaryk University Press
Place of publication
Masaryk University, Brno
Event location
Praha
Event date
Aug 28, 2023
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—