Shallow vertex minors, stability, and dependence
Buffière, Hector1; Kim, Eun Jung2; Ossona de Mendez, Patrice3
1 École Normale Supérieure Paris France
2 KAIST, Daejeon South Korea and CNRS Paris France
3 Centre d’Analyse et de Mathématiques Sociales (CNRS, UMR 8557) Paris France and Computer Science Institute of Charles University Praha Czech Republic
Innovations in Graph Theory, Volume 1 (2024), pp. 87-112.

Stability and dependence are model-theoretic notions that have recently proved highly effective in the study of structural and algorithmic properties of hereditary graph classes, and are considered key notions for generalizing to hereditary graph classes the theory of sparsity developed for monotone graph classes (where an essential notion is that of nowhere dense class). The theory of sparsity was initially built on the notion of shallow minors and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear.

In this paper, we follow a similar path, where shallow vertex minors replace shallow minors. In this setting, we provide a neat characterization of stable / dependent hereditary classes of graphs: A hereditary class of graphs 𝒞 is dependent if and only if it does not contain all permutation graphs and, for each integer r, it excludes some split interval graph as a depth-r vertex minor; it is stable if and only if, for each integer r, it excludes some half-graph as a depth-r vertex minor.

A key ingredient in proving these results is the preservation of stability and dependence of a class when taking bounded depth shallow vertex minors. We extend this preservation result to binary structures and get, as a direct consequence, that bounded depth shallow vertex minors of graphs with bounded twin-width have bounded twin-width.

Received:
Accepted:
Published online:
DOI: 10.5802/igt.5
Classification: 05C75, 03C13
Mots-clés : graph, local complementation, shallow vertex minor, dependence, NIP, stability, twin-width, binary relational structure

Buffière, Hector 1; Kim, Eun Jung 2; Ossona de Mendez, Patrice 3

1 École Normale Supérieure Paris France
2 KAIST, Daejeon South Korea and CNRS Paris France
3 Centre d’Analyse et de Mathématiques Sociales (CNRS, UMR 8557) Paris France and Computer Science Institute of Charles University Praha Czech Republic
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{IGT_2024__1__87_0,
     author = {Buffi\`ere, Hector and Kim, Eun Jung and Ossona de Mendez, Patrice},
     title = {Shallow vertex minors, stability,  and dependence},
     journal = {Innovations in Graph Theory},
     pages = {87--112},
     publisher = {Stichting Innovations in Graph Theory},
     volume = {1},
     year = {2024},
     doi = {10.5802/igt.5},
     language = {en},
     url = {https://igt.centre-mersenne.org/articles/10.5802/igt.5/}
}
TY  - JOUR
AU  - Buffière, Hector
AU  - Kim, Eun Jung
AU  - Ossona de Mendez, Patrice
TI  - Shallow vertex minors, stability,  and dependence
JO  - Innovations in Graph Theory
PY  - 2024
SP  - 87
EP  - 112
VL  - 1
PB  - Stichting Innovations in Graph Theory
UR  - https://igt.centre-mersenne.org/articles/10.5802/igt.5/
DO  - 10.5802/igt.5
LA  - en
ID  - IGT_2024__1__87_0
ER  - 
%0 Journal Article
%A Buffière, Hector
%A Kim, Eun Jung
%A Ossona de Mendez, Patrice
%T Shallow vertex minors, stability,  and dependence
%J Innovations in Graph Theory
%D 2024
%P 87-112
%V 1
%I Stichting Innovations in Graph Theory
%U https://igt.centre-mersenne.org/articles/10.5802/igt.5/
%R 10.5802/igt.5
%G en
%F IGT_2024__1__87_0
Buffière, Hector; Kim, Eun Jung; Ossona de Mendez, Patrice. Shallow vertex minors, stability,  and dependence. Innovations in Graph Theory, Volume 1 (2024), pp. 87-112. doi : 10.5802/igt.5. https://igt.centre-mersenne.org/articles/10.5802/igt.5/

[1] Adler, H.; Adler, I. Interpreting nowhere dense graph classes as a classical notion of model theory, Eur. J. Comb., Volume 36 (2014), pp. 322-330 | DOI | Zbl

[2] Bonnet, E.; Giocanti, U.; Ossona de Mendez, P.; Simon, P.; Thomassé, S.; Toruńczyk, S. Twin-width IV: ordered graphs and matrices, STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, ACM (2022), pp. 924-937 | DOI | Zbl

[3] Bonnet, E.; Kim, E. J.; Thomassé, S.; Watrigant, R. Twin-width I: tractable FO model checking, 61st Annual Symposium on Foundations of Computer Science (FOCS 2020), IEEE (2020), pp. 601-612 | DOI

[4] Bonnet, E.; Nešetřil, J.; Ossona de Mendez, P.; Siebertz, S.; Thomassé, S. Twin-width and permutations, Logical Methods in Computer Science, Volume 20 (2024) no. 3, Paper no. 4, 25 pages | DOI | Zbl

[5] Braunfeld, S.; Laskowski, M. C. Existential characterizations of monadic NIP (2022) | arXiv

[6] Braunfeld, S.; Nešetřil, J.; Ossona de Mendez, P.; Siebertz, S. Decomposition horizons: from graph sparsity to model-theoretic dividing lines, Eur. J. Comb. (2024) (Eurocomb 2023 special issue; submitted)

[7] Dreier, J.; Eleftheriadis, I.; Mählmann, N.; McCarty, R.; Pilipczuk, M.; Toruńczyk, S. First-Order Model Checking on Monadically Stable Graph Classes (2023) (accepted at FOCS 2024) | arXiv

[8] Dreier, J.; Mählmann, N.; Siebertz, S.; Toruńczyk, S. Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), Schloss-Dagstuhl-Leibniz Zentrum für Informatik (2023)

[9] Dreier, J.; Mählmann, N.; Toruńczyk, S. Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, ACM (2024), pp. 1550-1560 | DOI

[10] Foldes, S.; Hammer, P. L. Split graphs having Dilworth number two, Can. J. Math., Volume 29 (1977) no. 3, pp. 666-672 | DOI | Zbl

[11] Geelen, J.; Kwon, O.; McCarty, R.; Wollan, P. The Grid Theorem for vertex-minors, J. Comb. Theory, Ser. B, Volume 158 (2023), pp. 93-116 (Robin Thomas 1962-2020) | DOI | Zbl

[12] Kwon, O.; McCarty, R.; Oum, S.; Wollan, P. Obstructions for bounded shrub-depth and rank-depth, J. Comb. Theory, Ser. B, Volume 149 (2021), pp. 76-91 | DOI | Zbl

[13] Nešetřil, J.; Ossona de Mendez, P. Sparsity (Graphs, Structures, and Algorithms), Algorithms and Combinatorics, 28, Springer, 2012, 465 pages | DOI

[14] Nešetřil, J.; Ossona de Mendez, P.; Pilipczuk, M.; Rabinovich, R.; Siebertz, S. Rankwidth meets stability, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), ACM (2021), pp. 2014-2033 | DOI | Zbl

[15] Nešetřil, J.; Ossona de Mendez, P.; Siebertz, S. Modulo-Counting First-Order Logic on Bounded Expansion Classes, Discrete Math., Volume 347 (2024) no. 8, p. 113700 | DOI | Zbl

[16] Oum, S. Rank-width and vertex-minors, J. Comb. Theory, Ser. B, Volume 95 (2005) no. 1, pp. 79-100 | DOI | Zbl

Cited by Sources: