Separability Properties of Monadically Dependent Graph Classes
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916739921477632 |
|---|---|
| author | Bonnet, Édouard Braunfeld, Samuel Eleftheriadis, Ioannis Geniet, Colin Mählmann, Nikolas Pilipczuk, Michał Przybyszewski, Wojciech Toruńczyk, Szymon |
| author_facet | Bonnet, Édouard Braunfeld, Samuel Eleftheriadis, Ioannis Geniet, Colin Mählmann, Nikolas Pilipczuk, Michał Przybyszewski, Wojciech Toruńczyk, Szymon |
| contents | A graph class $\mathcal C$ is monadically dependent if one cannot interpret all graphs in colored graphs from $\mathcal C$ using a fixed first-order interpretation. We prove that monadically dependent classes can be exactly characterized by the following property, which we call flip-separability: for every $r\in \mathbb{N}$, $\varepsilon>0$, and every graph $G\in \mathcal{C}$ equipped with a weight function on vertices, one can apply a bounded (in terms of $\mathcal{C},r,\varepsilon$) number of flips (complementations of the adjacency relation on a subset of vertices) to $G$ so that in the resulting graph, every radius-$r$ ball contains at most an $\varepsilon$-fraction of the total weight. On the way to this result, we introduce a robust toolbox for working with various notions of local separations in monadically dependent classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11144 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Separability Properties of Monadically Dependent Graph Classes Bonnet, Édouard Braunfeld, Samuel Eleftheriadis, Ioannis Geniet, Colin Mählmann, Nikolas Pilipczuk, Michał Przybyszewski, Wojciech Toruńczyk, Szymon Combinatorics Discrete Mathematics Logic in Computer Science Logic A graph class $\mathcal C$ is monadically dependent if one cannot interpret all graphs in colored graphs from $\mathcal C$ using a fixed first-order interpretation. We prove that monadically dependent classes can be exactly characterized by the following property, which we call flip-separability: for every $r\in \mathbb{N}$, $\varepsilon>0$, and every graph $G\in \mathcal{C}$ equipped with a weight function on vertices, one can apply a bounded (in terms of $\mathcal{C},r,\varepsilon$) number of flips (complementations of the adjacency relation on a subset of vertices) to $G$ so that in the resulting graph, every radius-$r$ ball contains at most an $\varepsilon$-fraction of the total weight. On the way to this result, we introduce a robust toolbox for working with various notions of local separations in monadically dependent classes. |
| title | Separability Properties of Monadically Dependent Graph Classes |
| topic | Combinatorics Discrete Mathematics Logic in Computer Science Logic |
| url | https://arxiv.org/abs/2505.11144 |