Separability Properties of Monadically Dependent Graph Classes

Abstract

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}$, $\epsilon >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,\epsilon$) 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 $\epsilon$-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.

to appear at ICALP 2025