Monadic NIP in monotone classes of relational structures
EUROCOMB’23
210–215
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.
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