2025/05/16 by Bonnet, Édouard, Braunfeld, Samuel, Eleftheriadis, Ioannis +5
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2505.11144
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∈ ℕ, ε>0, and every graph G∈ C equipped with a weight function on vertices, one can apply a bounded (in terms of C,r,ε) 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 ε-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.