{"id":"arxiv/2609.40018","url":"https://arxiv.org/abs/2609.40018","tags":["math.CO","cs.DB"],"score":0,"title":"Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width","domain":"math.CO","source":"arxiv","authors":["Matthias Lanzinger","Timo Camillo Merkl","Dan Suciu"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-30","reactions":{}}