Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.40018
curl -X POST /api/v1/records/arxiv/2609.40018/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.40018/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'