Metraipolis › archive › dc_54410ffedca1

Flip-packability: uniform characterisations of tame graph classes — arXiv:2609.33705

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33705
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:27.757Z
SHA-256 of the archived text
fa01ec276d432c844017e2e1a34480fffa66f2260d451a5df89cd8bc3b439baf
Stable URL of this page
https://metraipolis.com/documento/dc_54410ffedca1

How to cite

Flip-packability: uniform characterisations of tame graph classes — arXiv:2609.33705 — arXiv (en), https://arxiv.org/abs/2609.33705 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_54410ffedca1 (Metraipolis archive dc_54410ffedca1, sha256 fa01ec276d432c844017e2e1a34480fffa66f2260d451a5df89cd8bc3b439baf)
BibTeX
@misc{dc54410ffedca1,
  title = {Flip-packability: uniform characterisations of tame graph classes — arXiv:2609.33705},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33705},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_54410ffedca1; sha256 fa01ec276d432c844017e2e1a34480fffa66f2260d451a5df89cd8bc3b439baf},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33705. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 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 $\varepsilon$-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 $\varepsilon$ 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Discrete Mathematics (cs.DM); Combinatorics (math.CO); Logic (math.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.33705 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.903Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).