Metraipolis › archive › dc_7c335d5e66ea

Monadically Dependent Graph Classes Have Almost Bounded Merge-Width — arXiv:2611.06804

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.06804
License (as archived): CC0-1.0
Archived: 2026-11-05T18:28:43.728Z
SHA-256 of the archived text: f7c8469a2dd70656cb0e55104b030a1f140cdfc76e556df860aeef6e7b858c59
Stable URL of this page: https://metraipolis.com/documento/dc_7c335d5e66ea

How to cite

Monadically Dependent Graph Classes Have Almost Bounded Merge-Width — arXiv:2611.06804 — arXiv (en), https://arxiv.org/abs/2611.06804 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7c335d5e66ea (Metraipolis archive dc_7c335d5e66ea, sha256 f7c8469a2dd70656cb0e55104b030a1f140cdfc76e556df860aeef6e7b858c59)

BibTeX

@misc{dc7c335d5e66ea,
  title = {Monadically Dependent Graph Classes Have Almost Bounded Merge-Width — arXiv:2611.06804},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06804},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7c335d5e66ea; sha256 f7c8469a2dd70656cb0e55104b030a1f140cdfc76e556df860aeef6e7b858c59},
  year = {2026}
}

Archived text

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

A graph class $\mathcal{C}$ is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from $\mathcal{C}$ using a fixed formula of first-order logic. We prove that every monadically dependent graph class has almost bounded merge-width, thereby confirming a conjecture of the first and the last author [STOC '25]. Our proof is algorithmic and the witnessing decompositions in the form of merge sequences can be computed in nearly-cubic time. This is a step towards the proof of fixed-parameter tractability of model checking first-order logic on monadically dependent graph classes, which is achieved in a companion paper.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Data Structures and Algorithms (cs.DS); Logic in Computer Science (cs.LO); Combinatorics (math.CO); Logic (math.LO).
Pagina del lavoro: https://arxiv.org/abs/2611.06804 — 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-11-05T18:18:34.007Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).