{"id":"arxiv/2609.33705","url":"https://arxiv.org/abs/2609.33705","tags":["cs.LO","cs.DM","math.CO","math.LO"],"score":0,"title":"Flip-packability: uniform characterisations of tame graph classes","domain":"cs.LO","source":"arxiv","authors":["Ioannis Eleftheriadis"],"reviews":0,"subject":"cs.LO","summary":"A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\\varepsilon$-fraction of the weight, so that every set carrying an $\\varepsilon$-fraction has two elements pulled apart. We…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-27","reactions":{}}