Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 34 min ago
PreprintCC BY 4.0arXiv

Monadically Dependent Graph Classes Have Almost Bounded Merge-Width

  • Jan Dreier
  • Nikolas Mählmann
  • Michał Pilipczuk
  • Szymon Toruńczyk
Open at sourcePDFDOICite

Abstract

A graph class 𝒞 is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from 𝒞 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.

Related

  1. First-Order Model Checking on Monadically Dependent Graph Classes
    Jan Dreier, Nikolas Mählmann, Szymon Toruńczyk
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsLogic & foundationsarXiv
  2. Almost perfect graph classes
    Cicely Henderson, Hidde Koerts, Taite LaGrange +4
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. A polynomial time algorithm for almost bounded denumerant
    Guoce Xin, Chen Zhang, Zihao Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Push forwards of smooth measures on the unitary group in odd characteristic under the Chevalley map are almost bounded
    Avraham Aizenbud, Nir Avni, Dmitry Gourevitch +2
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  5. On the order of a finite group with trivial centre and bounded conjugacy classes
    Ilya Gorshkov
    arXivPreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{dreier2026monadically,
  title = {{Monadically Dependent Graph Classes Have Almost Bounded Merge-Width}},
  author = {Jan Dreier and Nikolas Mählmann and Michał Pilipczuk and Szymon Toruńczyk},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06804},
  eprint = {2611.06804},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06804},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Monadically Dependent Graph Classes Have Almost Bounded Merge-Width
AU  - Jan Dreier
AU  - Nikolas Mählmann
AU  - Michał Pilipczuk
AU  - Szymon Toruńczyk
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06804
UR  - https://arxiv.org/abs/2611.06804
AB  - A graph class 𝒞 is monadically dependent if one cannot interpret all graphs in vertex-colored graphs from 𝒞 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.
ER  -