Monadic NIP in monotone classes of relational structures

EUROCOMB’23

Samuel Braunfeld Anuj Dawar Ioannis Eleftheriadis Aris Papadopoulos

https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-029

PDF
Abstract
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.

Pages:
210–215
References

Hans Adler and Isolde Adler. Interpreting nowhere dense graph classes as a classical notion of model theory. European Journal of Combinatorics, 36:322-330, 2014.
https://doi.org/10.1016/j.ejc.2013.06.048

John T. Baldwin. Fundamentals of Stability Theory. Perspectives in Logic. Cambridge University Press, 2017.

Samuel Braunfeld and Michael C. Laskowski. Existential characterizations of monadic NIP, 2022.

Anuj Dawar. Finite model theory on tame classes of structures. In MFCS, volume 4708 of Lecture Notes in Computer Science, pages 2-12. Springer, 2007.
https://doi.org/10.1007/978-3-540-74456-6_2

Paul Erdős and Richard Rado. A combinatorial theorem. Journal of the London Mathematical Society, 1(4):249-255, 1950.
https://doi.org/10.1112/jlms/s1-25.4.249

Jakub Gajarský, Michal Pilipczuk, and Szymon Torunczyk. Stable graphs of bounded twin-width. In Christel Baier and Dana Fisman, editors, LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2 - 5, 2022, pages 39:1-39:12. ACM, 2022.
https://doi.org/10.1145/3531130.3533356

Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. J. ACM, 64(3), jun 2017.
https://doi.org/10.1145/3051095

Stephan Kreutzer and Anuj Dawar. Parameterized complexity of first-order logic. Electron. Colloquium Comput. Complex., TR09-131, 2009.

Jaroslav Nešetřil and Patrice Ossona De Mendez. Sparsity: graphs, structures, and algorithms, volume 28. Springer Science & Business Media, 2012.
https://doi.org/10.1007/978-3-642-27875-4

Michal Pilipczuk, Sebastian Siebertz, and Szymon Torunczyk. Parameterized circuit complexity of model-checking on sparse structures. In Anuj Dawar and Erich Grädel, editors, Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018, Oxford, UK, July 09-12, 2018, pages 789-798. ACM, 2018.
https://doi.org/10.1145/3209108.3209136

Klaus-Peter Podewski and Martin Ziegler. Stable graphs. Fund. Math, 100(2):101-107, 1978.
https://doi.org/10.4064/fm-100-2-101-107

Saharon Shelah. Classification theory and the number of nonisomorphic models, volume 92 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam-New York, 1978.

Metrics

0

Views

0

PDF views

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Copyright © 2023 Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, Aris Papadopoulos

PDF