{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T20:48:31Z","timestamp":1768337311659,"version":"3.49.0"},"reference-count":16,"publisher":"MathDoc\/Centre Mersenne","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"\n Stability<\/jats:italic>\n and\n dependence<\/jats:italic>\n 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\n nowhere dense<\/jats:italic>\n class). The theory of sparsity was initially built on the notion of\n shallow minors<\/jats:italic>\n and on the idea of excluding different sets of minors, depending on the depth at which these minors can appear.\n <\/jats:p>\n \n In this paper, we follow a similar path, where\n shallow vertex minors<\/jats:italic>\n replace shallow minors. In this setting, we provide a neat characterization of stable \/ dependent hereditary classes of graphs: A hereditary class of graphs\n \n \ud835\udc9e<\/mml:mi>\n <\/mml:math>\n is\n dependent<\/jats:italic>\n if and only if it does not contain all permutation graphs and, for each integer\n \n r<\/mml:mi>\n <\/mml:math>\n , it excludes some split interval graph as a depth-\n \n r<\/mml:mi>\n <\/mml:math>\n vertex minor; it is\n stable<\/jats:italic>\n if and only if, for each integer\n \n r<\/mml:mi>\n <\/mml:math>\n , it excludes some half-graph as a depth-\n \n r<\/mml:mi>\n <\/mml:math>\n vertex minor.\n <\/jats:p>\n 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.<\/jats:p>","DOI":"10.5802\/igt.5","type":"journal-article","created":{"date-parts":[[2024,11,26]],"date-time":"2024-11-26T08:30:34Z","timestamp":1732609834000},"page":"87-112","source":"Crossref","is-referenced-by-count":0,"title":["Shallow vertex minors, stability, and dependence"],"prefix":"10.5802","volume":"1","author":[{"given":"Hector","family":"Buffi\u00e8re","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eun Jung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrice","family":"Ossona de Mendez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"3842","published-online":{"date-parts":[[2024,11,26]]},"reference":[{"key":"key2025101311040260821_1","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.ejc.2013.06.048","article-title":"Interpreting nowhere dense graph classes as a classical notion of model theory","volume":"36","author":"Adler, H.","year":"2014","unstructured":"[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","journal-title":"Eur. J. Comb."},{"key":"key2025101311040260821_2","doi-asserted-by":"publisher","first-page":"924","DOI":"10.1145\/3519935.3520037","article-title":"Twin-width IV: ordered graphs and matrices","author":"Bonnet, E.","year":"2022","unstructured":"[2] Bonnet, E.; Giocanti, U.; Ossona de Mendez, P.; Simon, P.; Thomass\u00e9, S.; Toru\u0144czyk, 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","journal-title":"STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"},{"key":"key2025101311040260821_3","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1109\/FOCS46700.2020.00062","article-title":"Twin-width I: tractable FO model checking","author":"Bonnet, E.","year":"2020","unstructured":"[3] Bonnet, E.; Kim, E. J.; Thomass\u00e9, 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","journal-title":"61st Annual Symposium on Foundations of Computer Science (FOCS 2020)"},{"issue":"3","key":"key2025101311040260821_4","doi-asserted-by":"publisher","DOI":"10.46298\/lmcs-20(3:4)2024","article-title":"Twin-width and permutations","volume":"20","author":"Bonnet, E.","year":"2024","unstructured":"[4] Bonnet, E.; Ne\u0161et\u0159il, J.; Ossona de Mendez, P.; Siebertz, S.; Thomass\u00e9, S. Twin-width and permutations, Logical Methods in Computer Science, Volume 20 (2024) no. 3, 4, 25 pages","journal-title":"Logical Methods in Computer Science"},{"key":"key2025101311040260821_5","author":"Braunfeld, S.","year":"2022","unstructured":"[5] Braunfeld, S.; Laskowski, M. C. Existential characterizations of monadic NIP (2022)","journal-title":"Existential characterizations of monadic NIP"},{"key":"key2025101311040260821_6","article-title":"Decomposition horizons: from graph sparsity to model-theoretic dividing lines","author":"Braunfeld, S.","year":"2024","unstructured":"[6] Braunfeld, S.; Ne\u0161et\u0159il, 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)","journal-title":"Eur. J. Comb."},{"key":"key2025101311040260821_7","author":"Dreier, J.","year":"2023","unstructured":"[7] Dreier, J.; Eleftheriadis, I.; M\u00e4hlmann, N.; McCarty, R.; Pilipczuk, M.; Toru\u0144czyk, S. First-Order Model Checking on Monadically Stable Graph Classes (2023) (accepted at FOCS 2024)","journal-title":"First-Order Model Checking on Monadically Stable Graph Classes"},{"key":"key2025101311040260821_8","article-title":"Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes","author":"Dreier, J.","year":"2023","unstructured":"[8] Dreier, J.; M\u00e4hlmann, N.; Siebertz, S.; Toru\u0144czyk, 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\u00fcr Informatik (2023)","journal-title":"50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)"},{"key":"key2025101311040260821_9","doi-asserted-by":"publisher","first-page":"1550","DOI":"10.1145\/3618260.3649739","article-title":"Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes","author":"Dreier, J.","year":"2024","unstructured":"[9] Dreier, J.; M\u00e4hlmann, N.; Toru\u0144czyk, 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","journal-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing"},{"issue":"3","key":"key2025101311040260821_10","doi-asserted-by":"publisher","first-page":"666","DOI":"10.4153\/CJM-1977-069-1","article-title":"Split graphs having Dilworth number two","volume":"29","author":"Foldes, S.","year":"1977","unstructured":"[10] Foldes, S.; Hammer, P. L. Split graphs having Dilworth number two, Can. J. Math., Volume 29 (1977) no. 3, pp. 666-672","journal-title":"Can. J. Math."},{"key":"key2025101311040260821_11","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.jctb.2020.08.004","article-title":"The Grid Theorem for vertex-minors","volume":"158","author":"Geelen, J.","year":"2023","unstructured":"[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)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"key2025101311040260821_12","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1016\/j.jctb.2021.01.005","article-title":"Obstructions for bounded shrub-depth and rank-depth","volume":"149","author":"Kwon, O.","year":"2021","unstructured":"[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","journal-title":"J. Comb. Theory, Ser. B"},{"key":"key2025101311040260821_13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-27875-4","volume":"28","author":"Ne\u0161et\u0159il, J.","year":"2012","unstructured":"[13] Ne\u0161et\u0159il, J.; Ossona de Mendez, P. Sparsity (Graphs, Structures, and Algorithms), Algorithms and Combinatorics, 28, Springer, 2012, 465 pages","journal-title":"Sparsity (Graphs, Structures, and Algorithms)"},{"key":"key2025101311040260821_14","doi-asserted-by":"publisher","first-page":"2014","DOI":"10.1137\/1.9781611976465.120","article-title":"Rankwidth meets stability","author":"Ne\u0161et\u0159il, J.","year":"2021","unstructured":"[14] Ne\u0161et\u0159il, 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","journal-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)"},{"issue":"8","key":"key2025101311040260821_15","doi-asserted-by":"publisher","first-page":"113700","DOI":"10.1016\/j.disc.2023.113700","article-title":"Modulo-Counting First-Order Logic on Bounded Expansion Classes","volume":"347","author":"Ne\u0161et\u0159il, J.","year":"2024","unstructured":"[15] Ne\u0161et\u0159il, 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","journal-title":"Discrete Math."},{"issue":"1","key":"key2025101311040260821_16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.jctb.2005.03.003","article-title":"Rank-width and vertex-minors","volume":"95","author":"Oum, S.","year":"2005","unstructured":"[16] Oum, S. Rank-width and vertex-minors, J. Comb. Theory, Ser. B, Volume 95 (2005) no. 1, pp. 79-100","journal-title":"J. Comb. Theory, Ser. B"}],"container-title":["Innovations in Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/igt.centre-mersenne.org\/item\/10.5802\/igt.5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T09:04:26Z","timestamp":1760346266000},"score":1,"resource":{"primary":{"URL":"https:\/\/igt.centre-mersenne.org\/articles\/10.5802\/igt.5\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,26]]},"references-count":16,"alternative-id":["10.5802\/igt.5"],"URL":"https:\/\/doi.org\/10.5802\/igt.5","relation":{},"ISSN":["3050-743X"],"issn-type":[{"value":"3050-743X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,26]]}}}