Flip-packability: uniform characterisations of tame graph classes
Abstract
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 ε-fraction of the weight, so that every set carrying an ε-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an ε-fraction of the weight has m elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on ε and m. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with m=2, if and only if it is monadically dependent. The passage from two scattered elements to m is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number m of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case m separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.
Related
- Flip classes and elementary expansions of vertical-strip LLT polynomials
- Flip-graph non-convexity for once-punctured polygons
- Maximal regular subsemigroups containing the group of units of transformation semigroups that preserve a uniform equivalence relation with two classes
- Iterated Graph Systems (II): Bernoulli percolation and critical-exponent universality classes on hierarchical lattices
- Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
BibTeX
@misc{eleftheriadis2026flippackability,
title = {{Flip-packability: uniform characterisations of tame graph classes}},
author = {Ioannis Eleftheriadis},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33705},
eprint = {2609.33705},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33705},
}
RIS
TY - UNPB
TI - Flip-packability: uniform characterisations of tame graph classes
AU - Ioannis Eleftheriadis
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.33705
UR - https://arxiv.org/abs/2609.33705
AB - 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 ε-fraction of the weight, so that every set carrying an ε-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an ε-fraction of the weight has m elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on ε and m. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with m=2, if and only if it is monadically dependent. The passage from two scattered elements to m is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number m of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case m separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.
ER -