Monadic NIP in monotone classes of relational structures

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Monadic NIP in monotone classes of relational structures

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Monadic NIP in monotone classes of relational structures

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA21-10775S" target="_blank" >GA21-10775S: Ramseyova teorie v kontextu teorie grup, teorie modelů a topologické dynamiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

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

—

Počet stran výsledku

6

Strana od-do

210-215

Název nakladatele

Masaryk University Press

Místo vydání

Masaryk University, Brno

Místo konání akce

Praha

Datum konání akce

28. 8. 2023

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—