Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated just now
PreprintarXiv licencearXiv

Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width

  • Matthias Lanzinger
  • Timo Camillo Merkl
  • Dan Suciu
Open at sourcePDFDOICite

Abstract

We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, except for the entropic width, where we only give a lower and upper bound. We use Ingleton's inequality and the Zhang-Yeung inequality for upper bounds, and give explicit constructions of modular, normal, linear, entropic, and non-entropic polymatroids for lower bounds.

Related

  1. Rigidity and weak notions of spectral scalar curvature
    Xiaoxiang Chai
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  2. On the stability of proximal operators in Wasserstein spaces under different notions of convexity
    Simone Di Marino, Sara Farinelli, Emanuele Naldi
    arXivPreprintarXiv licenceFull textAnalysis & PDEsOptimisation & controlarXiv
  3. Notions of equivalence among constant Yang--Baxter Operators: To āˆž-Equivalence and Beyond
    Paul P. Martin, Eric C. Rowell
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Some New Notions of Mathematical Integral Inequalities: Theory and Applications
    Hijaz Ahmad, Muhammad Usman Tariq, Ali Asghar +3
    International Journal of Analysis and ApplicationsPeer-reviewedCC BYFull text12 citedGeneral mathematicsOpenAlex
  5. Master Equations for Mean Field Game of Controls: A Unification of Weak Solution Notions
    Mengzhen Li, Xintian Liu, Chenchen Mou +1
    arXivPreprintarXiv licenceFull textOptimisation & controlProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{lanzinger2026separating,
  title = {{Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width}},
  author = {Matthias Lanzinger and Timo Camillo Merkl and Dan Suciu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.40018},
  eprint = {2609.40018},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.40018},
}
RIS
TY  - UNPB
TI  - Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
AU  - Matthias Lanzinger
AU  - Timo Camillo Merkl
AU  - Dan Suciu
PY  - 2026
DA  - 2026/09/30
PB  - arXiv
DO  - 10.48550/arxiv.2609.40018
UR  - https://arxiv.org/abs/2609.40018
AB  - We describe one explicit simple graph G on 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, except for the entropic width, where we only give a lower and upper bound. We use Ingleton's inequality and the Zhang-Yeung inequality for upper bounds, and give explicit constructions of modular, normal, linear, entropic, and non-entropic polymatroids for lower bounds.
ER  -