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

Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width Matthias Lanzinger1 , Timo Camillo Merkl2,1 , and Dan Suciu3

arXiv:2609.40018v1 [math.CO] 30 Sep 2026

1

2

TU Wien, Austria Max Planck Institute for Software Systems, Germany 3 University of Washington, United States

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 [Ing71] and the Zhang–Yeung inequality [ZY98] for upper bounds, and give explicit constructions of modular, normal, linear, entropic, and non-entropic polymatroids for lower bounds.

1

Introduction

This work is motivated by the decision problem for graph pattern matching: given a pattern graph G and database graph D, check if D contains a homomorphic image of G. Since the introduction of the submodular width of a graph by Marx [Mar13], variations of this notion have been used to prove both upper [KNS25] and lower bounds [FKZ24, FKZ23] on the complexity of graph pattern matching. For example, a pattern G with submodular width subw can be checked in time Õ(N subw ), where N is the size of the database graph. However, there are several variations of the “width” notion that one could consider. The original definition of subw by Marx used a polymatroid, which is a monotone and submodular set-function on the vertices of the pattern graph. Bounds obtained from polymatroids can be converted into an algorithm. On the other hand, circuit lower bounds require the more stringent notion of entropic width [FKZ24], while fine-grained complexity lower bounds [FKZ23, BG25] require the much stricter notion of clique embedding, which in turn is a restriction of the normal width. The question we address here is whether these notions of width coincide. A separation of the “polymatroid bound” and the “entropic bound” was proved in [KNS17] for bounds on the number of matches of a hypergraph pattern under cardinality constraints and functional dependencies. These bounds optimize the value of a polymatroid on the full set of variables. The widths studied here additionally involve minimizing the maximum bag value over tree decompositions, so a separation of those bounds does not directly imply a separation of widths. Moreover, we seek a separation for graph patterns under edge domination alone, without functional dependencies and cardinality constraints. Thus, it was an open question whether these variations of width coincide for graphs. When G is a cycle of length k, then its submodular width is 2 − 1/⌈k/2⌉, and this width is attained by using a normal polymatroid. Thus, for graphs G that are a simple cycle, the normal width coincides with

1

the entropic width, and with the submodular width. This naturally raises the question whether these notions are equal for all graphs G. However, the “boat query” [FKZ23], which is a graph pattern with 8 nodes originally studied in [JR16], has a submodular width of 2, which is strictly larger than the normal width. Thus, equality of normal- and submodular width fails for the boat query. However, for this query, the polymatroid witnessing subw = 2 is a linear polymatroid, meaning that it can be realized by the rank function in a vector space (definitions in Section 2). This, in turn, raised the natural question whether the submodular width coincides with the linear width, for every graph G. We answer this question negatively. We describe a single graph G with 32 vertices whose adaptive, normal, linear, entropic, and submodular widths are pairwise distinct. We compute all these widths exactly, except for the entropic width, for which we only provide a lower and upper bound (which are sufficient to separate it from the other widths). Our results were obtained with significant assistance from AI Agents: we used both OpenAI’s ChatGPT and Anthropic’s Claude (different authors used different agents). We did not obtain these results in a single shot, but instead went through a long journey until we arrived at the current results. We have entirely rewritten the AI-generated output, making it human-readable, and highlighted the important lessons carried by this construction. In particular, we identify clearly the role of Ingleton’s inequality [Ing71], and of the Zhang–Yeung inequality [ZY98] in these separation results, and describe a general class of non-entropic polymatroids (denoted fG in Section 5), all of which are of independent interest. By necessity, some tedious calculations remain, but they are clearly isolated in the paper, are verified by the verify.py script accompanying this paper, and their role in the big picture is clearly explained. Structure of the Paper. Section 2 introduces the classes of polymatroids. Section 3 defines the corresponding graph widths and states our main result. Section 4 presents the inequalities used for the upper bounds, and Section 5 gives examples that prepare the lower-bound constructions. Section 6 introduces the 32-vertex graph that witnesses the separation of the width notions. It consists of a central graph on five vertices and scaffolding that connects the bounds on the central graph to the widths of the full graph. Section 7 establishes these central bounds, and Section 8 uses them to prove the width separations. Section 9 concludes with open problems.

2

Classes of Polymatroids

Fix a set of n variables X = {X1 , . . . , Xn }. A polymatroid is a function h : 2X → R+ that satisfies for all U, V ⊆ X: h(∅) =0

(1)

h(U ∪ V ) ≥h(U )

(2)

h(U ) + h(V ) ≥h(U ∪ V ) + h(U ∩ V )

(3)

The second and third conditions are called monotonicity and submodularity. We write Γn for the set of polymatroids over n variables, or, alternatively, ΓX to emphasize that the set of variables is X. This set is a cone: if h is a polymatroid and c ≥ 0, then c · h is also a polymatroid. We consider several subsets of Γn : Modular Polymatroids. A polymatroid h is modular if equality holds in (3) for all U, V ⊆ X.

2

Equivalently, there exist weights wi ≥ 0 such that X h(U ) = wi for every U ⊆ X. Xi ∈U

The weights are the singleton values wi = h(Xi ). We write Mn for the set of modular polymatroids. Normal Polymatroids. If K ⊆ X, then we call the indicator function hK (U ) := 1U ∩K̸=∅ a step function. Every step function is a polymatroid. A normal polymatroid is a nonnegative linear combination of step functions. We write Nn for the set of normal polymatroids. Normal polymatroids have the following equivalent description, up to closure. Fix a set Ω. S A coverage function is φ : X → Pfin (Ω). If U ⊆ X then we write φ(U ) for the union ). Every function of the form h(U ) := c·|φ(U )| with c ≥ 0 is a normal polymatroid: Xi ∈U φ(X Pi it equals ∅̸=K⊆X c mK hK , where mK is the number of ω ∈ Ω with {Xi | ω ∈ φ(Xi )} = K. P Conversely, a normal polymatroid K mK hK is of this form exactly when the coefficients mK are commensurable (i.e. their ratio is a rational number), and in general it is a limit of such functions. Since wh (G) is continuous and positively homogeneous in h, the two descriptions give the same value of normw(G), and we use them interchangeably. Every normal witness in this paper has rational coefficients, so it is literally of the form c · |φ(·)|. Linear Polymatroids. Consider a vector space Rd and let φ : X → Pfin (Rd ) be a coverage function. The function r : 2X → R+ defined by: r(U ) := dim(span(φ(U ))) is called a rank function. One can check that r is a polymatroid. A polymatroid is called linear if it is a limit of nonnegative scalar multiples of rank functions. We write Linn for the set of linear polymatroids. Entropic and Almost Entropic Polymatroids. Let (Xi )ni=1 be a set of joint random variables, and set h(U ) := H(U ) the entropy of the subset U ⊆ X. Then h is a polymatroid, called an entropic polymatroid. The set of entropic polymatroids is denoted Γ∗n . Its topological closure is denoted Γ̄∗n , and its elements are called almost entropic functions. It is known that Mn ⊆ Nn ⊆ Linn ⊆ Γ̄∗n ⊆ Γn , with all inclusions strict for n ≥ 4.

3

Graph Widths and the Separation Theorem

All graphs are finite, simple, and have no isolated vertices. A tree decomposition of a graph G = (V, E) is a tree T together with bags Bt ⊆ V (t ∈ V (T )) such that every edge of G is contained in some bag and, for every x ∈ V , the set {t | x ∈ Bt } is nonempty and connected in T . We write TD(G) for the set of tree decompositions of G, and for h : 2V → R+ we put wh (G) :=

min

max h(Bt ).

(T,B)∈TD(G) t∈V (T )

A function h : 2V → R+ is edge dominated on G if h(e) ≤ 1 for every e ∈ E. We write ED(G) for the edge dominated functions on G, and define adw(G) :=

sup

wh (G)

adaptive width

h∈Mn ∩ED(G)

3

normw(G) :=

sup

wh (G)

normal width

wh (G)

linear width

wh (G)

entropic width

wh (G)

submodular width

h∈Nn ∩ED(G)

linw(G) :=

sup h∈Linn ∩ED(G)

entw(G) :=

sup h∈Γ̄∗n ∩ED(G)

subw(G) :=

sup h∈Γn ∩ED(G)

Since Mn ⊆ Nn ⊆ Linn ⊆ Γ̄∗n ⊆ Γn we always have adw(G) ≤ normw(G) ≤ linw(G) ≤ entw(G) ≤ subw(G). Edge domination can always be enforced by normalization. For any nonzero polymatroid h, let ch := maxe∈E h(e). Since G has no isolated vertices, ch > 0: otherwise monotonicity forces every singleton value to vanish, and subadditivity gives h = 0. The polymatroid h/ch is edge dominated. Since wh (G) is positively homogeneous in h, for every nontrivial class C of polymatroids closed under multiplication by positive scalars, sup

wh (G) =

h∈C∩ED(G)

wh (G) . max e∈E h(e) h∈C\{0} sup

Thus we may construct a polymatroid first and normalize it afterwards. By continuity, taking the closures in the definitions of linear and entropic polymatroids does not change the normalized suprema. Furthermore, since G has no isolated vertices, edge domination implies h(U ) ≤ |U | for every U ⊆ V (G). The five classes used in the width definitions are closed, so their edge dominated subsets are compact. Continuity of wh (G) therefore shows that all five suprema are attained. Theorem 1. There is a graph G on 32 vertices such that adw(G) = 6 < normw(G) =

69 44 635 183 19 < linw(G) = < ≤ entw(G) ≤ < subw(G) = . 11 7 101 29 3

The graph G mentioned in the theorem is defined in Section 6 and shown in Figure 1. In particular, for this graph adw(G) < normw(G) < linw(G) < entw(G) < subw(G). Notice that the theorem gives exact values for four out of the five widths. We leave open the exact value of entw(G), but notice that it belongs to the interval [635/101, 183/29].

4

Linear Inequalities

We consider linear inequalities of the form in terms of the following quantities: Hh (A | C) =h(AC) − h(C)

P

U ⊆X cU h(U ) ≥ 0. Often we express these inequalities

Ih (A; B | C) =h(AC) + h(BC) − h(ABC) − h(C)

Throughout this section A, B, C, X, Y denote arbitrary subsets of X. From Section 7 on, those inequalities are only ever instantiated at single central variables. 4

Inequalities in Γn . An inequality satisfied by all polymatroids is called a Shannon inequality. Inequalities (1), (2), and (3) are the Basic Shannon Inequalities. Consider a graph G = (V P(G), E(G)), and a set of weights we ≥ 0 for e ∈ E. Fix a set S ⊆ V (G) such that e∋v we ≥ 1 for every v ∈ S. Then we say that w is a fractional edge cover of S, and one can prove that the following is a Shannon inequality: X h(S) ≤ we h(e) (4) e

Inequalities in Γ̄∗n . If an inequality holds for all entropic functions h ∈ Γ∗n , then it also holds for all almost entropic functions h ∈ Γ̄∗n . For that reason we consider only the latter in our discussion. The following is called the Zhang–Yeung inequality [ZY98] and holds for all h ∈ Γ̄∗n : Ih (X; Y ) ≤ Ih (X; Y | A) + Ih (X; Y | B) + Ih (A; B) + Ih (X; Y | A) + Ih (A; Y | X) + Ih (A; X | Y ).

(5)

The term Ih (X; Y | A) occurs twice, and we have deliberately not collected the two copies into a single 2Ih (X; Y | A): the first line of (5) is precisely Ingleton’s inequality (6) below, and the second line is the surplus that (5) carries over it, as recorded in (9). Note also that (5) is not symmetric in A and B; this is why Lemma 8 has to apply it twice, once in each order. We write ZYh (X, Y ; A, B) for the slack of (5), i.e. the right-hand side minus the left-hand side of (5), so that (5) reads ZYh (X, Y ; A, B) ≥ 0. We note that no general characterization of all entropic inequalities is known. Inequalities in Linn . The following inequality holds for all linear polymatroids h ∈ Linn , and is called Ingleton’s inequality [Ing71]: Ih (X; Y ) ≤ Ih (X; Y | A) + Ih (X; Y | B) + Ih (A; B).

(6)

The inequality holds for rank functions, and hence for their nonnegative scalar multiples and limits by continuity. We write Ingh (X, Y ; A, B) for the slack, i.e. the right-hand side minus the left-hand side of (6), so that (6) reads Ingh (X, Y ; A, B) ≥ 0. We note that no general characterization of all linear rank inequalities is known; see [DFZ09] for the state of the art on five or more variables. Inequalities in Nn . Write ȟ(A) := h(X) − h(X \ A). For any nonempty K ⊆ X, a normal polymatroid h ∈ Nn satisfies: X (−1)|K\A| ȟ(A) ≥ 0 (7) A⊆K

Indeed, for h = c · |φ(·)| the left-hand side is c times the number of ω ∈ Ω lying in φ(Xi ) for exactly the Xi ∈ K, so (7) just says that these counts are nonnegative. One can also show that these inequalities completely characterize the normal polymatroids: h ∈ Γn is normal iff it satisfies all inequalities of the form (7). Inequalities in Mn . Every modular polymatroid h ∈ Mn satisfies: h(A) + h(B) ≤ h(A ∪ B) + h(A ∩ B).

(8)

Together with submodularity, this inequality holds with equality. Conversely, a polymatroid h ∈ Γn is modular iff it satisfies (8) for all A, B ⊆ X. 5

It is useful to compare Equations (5) and (6). ZYh (X, Y ; A, B) ≥ Ingh (X, Y ; A, B) for any polymatroid h, more precisely: ZYh (X, Y ; A, B) − Ingh (X, Y ; A, B) = Ih (X; Y | A) + Ih (A; Y | X) + Ih (A; X | Y ).

5

(9)

Three Special Polymatroids

To separate two width notions, it is not enough to exhibit a polymatroid belonging to one class but not the other. Instead we need a graph on which this additional freedom yields a strictly larger width. The following examples introduce the ingredients for our lower-bound constructions. The linear example illustrates a dependence pattern that normal polymatroids cannot represent. The entropic example violates Ingleton’s inequality and will serve as a building block for the entropic lower bound. Finally, the graph-induced polymatroid will supply the submodular lower bound. In the subsequent sections, we use these ideas to construct witnesses on the central graph, then extend those witnesses to the separating graph and prove that every tree decomposition contains a bag of sufficiently large value. The following notation will be convenient. Given a set X = {X1 , X2 , . . .} we abbreviate a subset of them by the string of its indices, for example X123 stands for {X1 , X2 , X3 }. A Linear Polymatroid. Consider the following coverage function from {X1 , X2 , X3 } to vectors in the vector space R2 : φ(X1 ) ={(1, 0)}

φ(X2 ) ={(0, 1)}

φ(X3 ) ={(1, 1)}

Let h be its rank function. More precisely: h(∅) =0

h(X1 ) = h(X2 ) = h(X3 ) =1

h(X12 ) = h(X13 ) = h(X23 ) = h(X123 ) = 2

This is a linear polymatroid which is not normal, because it violates inequality (7) for K = X123 : h(X1 ) + h(X2 ) + h(X3 ) − h(X12 ) − h(X13 ) − h(X23 ) + h(X123 ) = − 1 We will use a linear polymatroid in Section 7.3, where the same argument shows that it is not a normal polymatroid. An Entropic Polymatroid. The following entropic polymatroid is a building block for Section 7.4 below. Consider the following probability distribution on 4 variables X1 , X2 , X3 , X4 , computed from 2 independent fair Bernoulli random variables R, S: R S 0 0 0 1 1 0 1 1

X1 := R ∧ S X2 := R ∨ S X3 := R X4 := S 0 0 0 0 0 1 0 1 0 1 1 0 1 1 1 1

p 1/4 1/4 1/4 1/4

Let h0 be the entropy function of these four variables. For example, h0 (X1 ) = h0 (X2 ) = 14 log2 4+ 3 3 4 log2 (4/3) = 2 − 4 log2 3, h0 (X3 ) = h0 (X4 ) = 1, etc. Notice that h0 is not a linear polymatroid,

6

because it fails Ingleton’s inequality. To see this, instantiate (6) at (X, Y, A, B) = (X1 , X2 , X3 , X4 ), which reads Ih0 (X1 ; X2 ) ≤ Ih0 (X1 ; X2 | X3 ) + Ih0 (X1 ; X2 | X4 ) + Ih0 (X3 ; X4 ). All three terms on the right vanish. Indeed Ih0 (X3 ; X4 ) = 0 because R and S are independent; and conditioned on X3 = R one of X1 , X2 is constant, since R = 0 forces X1 = 0 while R = 1 forces X2 = 1, so Ih0 (X1 ; X2 | X3 ) = 0, and Ih0 (X1 ; X2 | X4 ) = 0 by the same argument with S in place of R. The left-hand side, however, is  3  3 5 3 Ih0 (X1 ; X2 ) = h0 (X1 ) + h0 (X2 ) − h0 (X12 ) = 2 2 − log2 3 − = − log2 3 ≈ 0.1226 > 0. 4 2 2 2 Hence Ingh0 (X1 , X2 ; X3 , X4 ) ≈ −0.1226 < 0, so h0 is not a linear polymatroid. A Polymatroid Induced by a Graph. function fG : 2V → R+ :

Fix any graph G = (V, E) and define the following

  0    2 fG (U ) :=  3    4

when U = ∅ when |U | = 1 when U ∈ E otherwise

(10)

In words, fG is 2 on singleton sets, is 3 on edges, and 4 everywhere else. One can check that fG is monotone and submodular, thus fG is a polymatroid. Zhang and Yeung showed that fG , where G = K4 − {34} (the complete graph on 4 vertices, without one edge), does not satisfy inequality (5), thus fG is not entropic: see Fig.5 in [Suc23] for a representation of fG . The polymatroid we use in Section 7.5 is fG for K5 − {15, 25, 34}.

6

The Separating Graph

The Central Graph G0 is K5 − {15, 25, 34}. On this graph we prove several upper and lower bounds for the different classes of polymatroids. However, G0 is insufficient to separate the corresponding notions of widths. The Big Graph, G, extends G0 with scaffolding that ensures that the separations on G0 extend to separations of corresponding notions of widths on G. The Central Graph. Let G0 = (X, E0 ), where X = {X1 , X2 , X3 , X4 , X5 } E0 = {X12 , X13 , X14 , X23 , X24 , X35 , X45 }. We will often refer to the five nodes X1 , . . . , X5 as variables. A key role will be played by the following five sets of variables: (U1 , U2 , U3 , U4 , U5 ) = (X123 , X124 , X34 , X15 , X25 )

(11)

The sets Ui are exactly the minimal subsets of X that are not contained in any edge of E0 : there are three non-edges X34 , X15 , X25 , and two triangles X123 and X124 . The Big Graph G. The big graph G has G0 as an induced subgraph, and is defined as follows. Let Ai = {ai,1 , ai,2 }, i = 1, . . . , 5, be five disjoint pairs of anchor nodes, all disjoint from X; we call 7

S each pair Ai an anchor group. We set A = i Ai . Join every pair of anchors from distinct groups, so that G[A] is the complete multipartite graph K2,2,2,2,2 whose five parts are the anchor groups: the two anchors of one group are non-adjacent, while every anchor is adjacent to all eight anchors outside its own group. Set (r1 , r2 , r3 , r4 , r5 ) = (3, 3, 3, 4, 4). For each i = 1, . . . , 5, let pi,1 , . . . , pi,ri be ri connector nodes, each adjacent to every vertex of Ai ∪ Ui . The graph G consists of the central graph G0 , the anchor graph G[A], and the connector nodes and their edges. Figure 1 shows the complete graph. The number of nodes and edges are: |V (G)| =5 + 10 + 17 = 32 |E(G)| =7 + 40 + 74 = 121

7

The Central Graph

We start by considering only the central graph G0 = (X, E0 ) and the sets U1 , . . . , U5 defined in (11). A “polymatroid on G0 ” means a polymatroid with variables X. We establish here several inequalities for polymatroids on G0 : they do not refer to tree decompositions of G0 , but instead are bounds on the following quantity: M (h) := min(h(U1 ), h(U2 ), h(U3 ), h(U4 ), h(U5 ))

(12)

In the next section we will use these bounds to compute bounds on the widths of the large graph G. In this section we prove the following: Theorem 2. With M as above, the following hold: max

h∈MX ∩ED(G0 )

14 11 h∈NX ∩ED(G0 ) 130 38 ≤ max M (h) ≤ ∗ 101 h∈Γ̄X ∩ED(G0 ) 29

M (h) = 1

max

9 7 h∈LinX ∩ED(G0 ) 4 max M (h) = 3 h∈ΓX ∩ED(G0 ) max

M (h) =

M (h) =

(13)

In particular: max

h∈MX ∩ED(G0 )

M (h) < <

max

M (h) <

max

M (h) <

h∈NX ∩ED(G0 ) h∈Γ̄∗X ∩ED(G0 )

max

h∈LinX ∩ED(G0 )

max

h∈ΓX ∩ED(G0 )

M (h)

M (h)

(14)

We prove the theorem in the rest of the section. The upper bounds 1, 14/11, 9/7, 38/29, and 4/3 are Lemmas 3, 4, 6, 8, and 10. The modular bound is attained by h(U ) = |U |/2, as shown in Lemma 3. The matching lower bounds 14/11, 9/7, and 4/3 are Lemmas 5, 7 and 11, and the lower bound 130/101 is Lemma 9. The inequalities (14) follow by 1 < 14/11, 14/11 < 9/7 (because 14 · 7 = 98 < 99 = 11 · 9), 9/7 < 130/101 (because 9 · 101 = 909 < 910 = 7 · 130), and 38/29 < 4/3 (because 38 · 3 = 114 < 116 = 29 · 4). Discussion. The theorem immediately implies that the entropic bound differs from the polymatroid bound for Disjunctive Datalog Rules (DDR) [KNS25]. More precisely, consider the following DDR: U1 (X1 , X2 , X3 ) ∨ U2 (X1 , X2 , X4 ) ∨ U3 (X3 , X4 ) ∨ U4 (X1 , X5 ) ∨ U5 (X2 , X5 ) 8

A1 U1 = X123

A2 U2 = X124 a1,1

a2,2

p1,1

a1,2

p2,3

p1,2

a2,1 p2,2

p1,3

p2,1

X2

X1

p5,1 a5,1

p4,4

X3

p5,2

X4

p5,3

A5 U5 = X25

a5,2

p4,2

X5

p5,4

p4,1

p3,1

a4,2

p4,3

a4,1

A4 U4 = X15

p3,3

p3,2

a3,1

a3,2

A3 U3 = X34 central vertex

connector

anchor

anchor edge

Figure 1: The 32-vertex graph G, drawn with all 121 edges. The five central variables X1 , . . . , X5 sit on the inner pentagon. Its five sides, together with two of its five diagonals, are exactly the seven central edges E0 . The other three diagonals, X34 , X15 and X25 , are absent from G. They are therefore minimal subsets of X contained in no central edge, and together with the only two triangles of G0 , namely X123 and X124 , they make up the five sets U1 , . . . , U5 of Section 6. Filled colored vertices are the ten anchors ai,k and hollow ones the 17 connectors pi,k ; each connector of group i is joined to both anchors of Ai and to every central variable in Ui . The 40 light arcs join every pair of anchors from distinct groups, forming K2,2,2,2,2 ; they are routed outside the anchor circle, so every arc that appears inside it is a connector edge. Edge crossings are not vertices.

9

← A(X1 , X2 ) ∧ B(X1 , X3 ) ∧ C(X1 , X4 ) ∧ D(X2 , X3 ) ∧ E(X2 , X4 ) ∧ F (X3 , X5 ) ∧ G(X4 , X5 ) The entropic- or polymatroid-bound of this DDR is the quantity maxh M (h), where h is an almost entropic polymatroid, or an arbitrary polymatroid respectively (h ∈ Γ̄∗X or h ∈ ΓX ). Denote these two bounds by e and p respectively: thus e ≤ 38/29 and p = 4/3. Then, the results in [KNS25] prove that, on one hand, for any input relations A, B, . . . , G of size N , there exists an output of the DDR rule where max(|U1 |, |U2 |, |U3 |, |U4 |, |U5 |) is ≤ N e , and, on the other hand, there exists an algorithm that can compute an output of size O(N p ) in time Õ(N p ). Theorem 2 proves that there is a gap between these two bounds.

7.1

Modular Polymatroids

Lemma 3. Every modular polymatroid h ∈ MX satisfies: h(U3 ) + h(U4 ) + h(U5 ) = h(X12 ) + h(X35 ) + h(X45 ).

(15)

In particular, if h is an edge dominated modular polymatroid on the central graph G0 , then mini h(Ui ) ≤ 1. This bound is attained by h(U ) = |U |/2. Proof. By modularity, both sides of the identity equal h(X1 ) + h(X2 ) + h(X3 ) + h(X4 ) + 2h(X5 ). If h is edge dominated, then 3 min h(Ui ) ≤ h(U3 ) + h(U4 ) + h(U5 ) = h(X12 ) + h(X35 ) + h(X45 ) ≤ 3, i

since X12 , X35 , X45 are central edges. For h(U ) = |U |/2, every central edge has value 1, and mini h(Ui ) = 1. This proves the lemma.

7.2

Normal Polymatroids

Lemma 4. Every normal polymatroid h ∈ NX satisfies: h(X123 ) + h(X124 ) + 5h(X34 ) + 2h(X15 ) + 2h(X25 ) ≤ 2h(X13 ) + 2h(X14 ) + 2h(X23 ) + 2h(X24 ) + 3h(X35 ) + 3h(X45 ).

(16)

In particular, if h is an edge dominated normal polymatroid on the central graph G0 then mini h(Ui ) ≤ 14/11. Proof. To prove inequality (16) we use Pthe fact that every normal polymatroid is a nonnegative linear combination of step functions, h = K⊆X m(K) hK with all m(K) ≥ 0, where hK (U ) = 1U ∩K̸=∅ (see Section 2). Therefore, it suffices to check inequality (16) for a step function hK : 1{K∩X123 ̸=∅} + 1{K∩X124 ̸=∅} + 5 · 1{K∩X34 ̸=∅} + 2 · 1{K∩X15 ̸=∅} + 2 · 1{K∩X25 ̸=∅} ≤ 2 · 1{K∩X13 ̸=∅} + 2 · 1{K∩X14 ̸=∅} + 2 · 1{K∩X23 ̸=∅} + 2 · 1{K∩X24 ̸=∅} + 3 · 1{K∩X35 ̸=∅} + 3 · 1{K∩X45 ̸=∅}

10

This inequality can be checked exhaustively for all 32 possible sets K ⊆ {X1 , . . . , X5 }. The same exhaustive check shows that equality holds iff K is one of the following sets: X1 ,

X2 ,

X13 ,

X23 ,

X123 ,

X14 ,

X24 ,

X124 ,

X35 ,

X45 .

(17)

The inequality implies for edge dominated normal polymatroids: 11 mini h(Ui ) ≤ h(X123 ) + h(X124 ) + 5h(X34 ) + 2h(X15 ) + 2h(X25 ) ≤ 2h(X13 ) + 2h(X14 ) + 2h(X23 ) + 2h(X24 ) + 3h(X35 ) + 3h(X45 ) ≤ 2 + 2 + 2 + 2 + 3 + 3 = 14. Inequality (16) is genuinely a normal inequality: it fails for the polymatroid gP of Lemma 11 below, whose left-hand side is 11 · 43 > 14, and, by Lemma 7 below, it already fails for a linear polymatroid, so it is not a linear rank inequality. Lemma 5. There exists an edge dominated, normal polymatroid gN on the central graph G0 such that gN (Ui ) = 14/11 for i = 1, . . . , 5. Furthermore, gN (X1 ) = gN (X2 ) =

6 2 < , 11 3

gN (X3 ) = gN (X4 ) =

7 2 < , 11 3

gN (X5 ) =

8 3 < . 11 4

(18)

Proof. We define gN to be the following nonnegative combination of the ten step functions hK given by the sets K in (17); the ten coefficients sum to 18/11: gN =

1 2hX1 + 2hX2 + hX13 + hX23 + hX123 11
+ hX14 + hX24 + hX124 + 4hX35 + 4hX45

(19)

Observe that gN (X12 ) = 10/11 and gN (e) = 1 for the other six central edges e ∈ E0 , so gN is edge dominated. We also observe that gN (Ui ) = 14/11 for i = 1, . . . , 5. The singleton values follow directly from (19). This proves the lemma.

7.3

Linear Polymatroids

The remaining three bounds, for linear, almost entropic and general polymatroids, all come from the same source. We start from the identity:   h(X123 ) + h(X124 ) + h(X34 ) + Ih (X1 ; X2 | X3 ) + Ih (X1 ; X2 | X4 ) + Ih (X3 ; X4 ) (20) = h(X13 ) + h(X23 ) + h(X14 ) + h(X24 ), which can be checked immediately by expanding the three information terms. Dropping the bracket gives the polymatroid bound of Lemma 10; replacing it by the sharper lower bound Ih (X1 ; X2 ) supplied by (6) gives Lemma 6; and (5) gives the intermediate Lemma 8. Lemma 6. Every linear polymatroid h ∈ LinX satisfies h(X123 ) + h(X124 ) + 3h(X34 ) + h(X15 ) + h(X25 ) ≤ h(X12 ) + h(X13 ) + h(X14 ) + h(X23 ) + h(X24 ) + 2h(X35 ) + 2h(X45 ).

(21)

In particular, if h is an edge dominated linear polymatroid on the central graph G0 , then mini h(Ui ) ≤ 9/7.

11

Proof. The inequality follows immediately by adding up the following inequalities: 1×

h(X123 )+h(X124 ) + h(X34 ) + h(X1 ) + h(X2 ) ≤ h(X12 ) + h(X13 ) + h(X14 ) + h(X23 ) + h(X24 )

from (20) and (6)

1×

h(X15 ) ≤ h(X1 ) + h(X5 )

from (1), (3)

1×

h(X25 ) ≤ h(X2 ) + h(X5 )

from (1), (3)

2×

h(X345 ) + h(X5 ) ≤ h(X35 ) + h(X45 )

from (3)

2×

h(X34 ) ≤ h(X345 )

from (2)

Each inequality needs to be multiplied by the factor on the left, then added up. The terms h(X1 ), h(X2 ), 2h(X5 ) and 2h(X345 ) occur on both sides and cancel, and what remains is inequality (21). The first line above uses Ingleton’s inequality (6), which is valid because h is a linear polymatroid. All the others are basic Shannon inequalities, valid for all polymatroids. Our discussion also implies that the right-hand side of (21) minus its left-hand side is Ingh (X1 , X2 ; X3 , X4 ) + Ih (X1 ; X5 ) + Ih (X2 ; X5 ) + 2Ih (X3 ; X4 | X5 ) + 2Hh (X5 | X34 ).

(22)

For the consequence, assume h(e) ≤ 1 for every e ∈ E0 . The LHS of (21) is h(U1 ) + h(U2 ) + 3h(U3 ) + h(U4 ) + h(U5 ) ≥ 7 mini h(Ui ), while the RHS is ≤ 1 + 1 + 1 + 1 + 1 + 2 + 2 = 9. The bound 9/7 is attained, by an explicit configuration of subspaces. Lemma 7. There exists an edge dominated, linear polymatroid gL ∈ LinX on the central graph G0 such that gL (Ui ) = 9/7 for i = 1, . . . , 5. Furthermore, the polymatroid gL satisfies: gL (X1 ) = gL (X2 ) =

4 2 < , 7 3

gL (X3 ) = gL (X4 ) =

9 2 < , 14 3

gL (X5 ) =

5 3 < . 7 4

(23)

1 Proof. Consider the vector space W = R18 with basis a1 , . . . , a9 , b1 , . . . , b9 . We define gL := 14 r, 1 where r is the rank function of the following coverage function:

V3 = ⟨a1 , . . . , a9 ⟩,

V4 = ⟨b1 , . . . , b9 ⟩,

V5 = ⟨a1 , . . . , a5 , b1 , . . . , b5 ⟩,

V1 = ⟨a6 , a7 , a8 , b6 , b7 , b8 , a9 + a2 + b3 , b9 + a3 + b2 ⟩,

(24)

V2 = ⟨a9 , a7 + a1 , a8 + a1 , b9 , b7 + b1 , b8 + b1 , a6 + a4 + b5 , b6 + a5 + b4 ⟩.
P As in Section 2, the rank function is r(S) := dim Xi ∈S Vi . Observe that V1 , . . . , V5 have dimensions 8, 8, 9, 9, 10 respectively, proving the bounds (23). For the remaining values, note first that W = V3 +V4 , so r(X34 ) = 18; and V5 = (V5 ∩V3 )+(V5 ∩V4 ) with both summands of dimension 5, so r(X35 ) = r(X45 ) = 9 + 10 − 5 = 14. Reducing modulo V5 sends the eight displayed generators of V1 to ā6 , ā7 , ā8 , b̄6 , b̄7 , b̄8 , ā9 , b̄9 , a basis of W/V5 , so V1 ∩V5 = 0 and r(X15 ) = 8 + 10 = 18; the generators of V2 reduce to the same basis in a different order, so r(X25 ) = 18 likewise. Next V1 ∩ V3 = ⟨a6 , a7 , a8 ⟩,

V2 ∩ V3 = ⟨a9 , a1 + a7 , a1 + a8 ⟩,

both of dimension 3, with the mirror statements for V4 obtained by exchanging ai ↔ bi ; hence r(X13 ) = r(X14 ) = r(X23 ) = r(X24 ) = 8+9−3 = 14. Also V1 ∩V2 = ⟨a7 −a8 , b7 −b8 ⟩ has dimension 1

More formally, the coverage function φ is φ(X3 ) := {a1 , . . . , a9 }, φ(X4 ) := {b1 , . . . , b9 }, etc: what we show in Eq. (24) is directly Vi := span(φ(Xi )).

12

2, so r(X12 ) = 8 + 8 − 2 = 14 and every central edge has gL -value 1. Finally, let π4 : W → V4 be the projection defined by π4 (ai ) = 0 and π4 (bi ) = bi . The projections of the generators of V1 and V2 span V4 : they include b3 , b5 , b6 , b7 , b8 , b9 , and the remaining basis vectors are obtained from b1 = (b7 + b1 ) − b7 ,

b2 = (b9 + b2 ) − b9 ,

b4 = (b6 + b4 ) − b6 .

Since ker π4 = V3 , it follows that V1 + V2 + V3 = W . Exchanging ai and bi gives V1 + V2 + V4 = W . Hence r(X123 ) = r(X124 ) = 18, so r(Ui ) = 18 and gL (Ui ) = 18/14 = 9/7 for all five i. Since 9/7 > 14/11, the configuration (24) is linear but not normal; we return to this in Section 8.6. The polymatroid gL is not a normal polymatroid. This can be seen by observing that its restriction to the set {X1 , X2 , X5 } violates (7) at K = {X1 , X2 , X5 }. We check this inequality for the rank function: r(X1 ) + r(X2 ) + r(X5 ) − r(X12 ) − r(X15 ) − r(X25 ) + r(X125 ) = 8 + 8 + 10 − 14 − 18 − 18 + 18 = −6 < 0, using r(X125 ) = 18, which follows from r(X15 ) = 18 = dim W by monotonicity. This is the same computation that gave −1 for the linear polymatroid in Section 5.

7.4

Almost Entropic Polymatroids

Lemma 8. Every almost entropic polymatroid h ∈ Γ̄∗X satisfies 5h(X123 ) + 5h(X124 ) + 11h(X34 ) + 4h(X15 ) + 4h(X25 ) ≤ 6h(X12 ) + 4h(X13 ) + 4h(X14 ) + 4h(X23 ) + 4h(X24 ) + 8h(X35 ) + 8h(X45 ).

(25)

In particular, if h is an edge dominated, almost entropic polymatroid on the central graph G0 , then mini h(Ui ) ≤ 38/29. Proof. Apply (5) twice, with (X, Y, A, B) equal to (X1 , X2 , X3 , X4 ) and to (X1 , X2 , X4 , X3 ); the two instances play the symmetric roles that the single instance of (6) played above, and their sum replaces Ingh (X1 , X2 ; X3 , X4 ). The inequality follows by adding up the following inequalities: 1×

4h(X123 ) + h(X124 ) + h(X34 ) + 2h(X1 ) + 2h(X2 ) + h(X3 ) from (5) ≤ 3h(X12 ) + 3h(X13 ) + 3h(X23 ) + h(X14 ) + h(X24 )

1×

h(X123 ) + 4h(X124 ) + h(X34 ) + 2h(X1 ) + 2h(X2 ) + h(X4 ) from (5) ≤ 3h(X12 ) + 3h(X14 ) + 3h(X24 ) + h(X13 ) + h(X23 )

1×

h(X34 ) ≤ h(X3 ) + h(X4 )

from (1), (3)

4×

h(X15 ) ≤ h(X1 ) + h(X5 )

from (1), (3)

4×

h(X25 ) ≤ h(X2 ) + h(X5 )

from (1), (3)

8× h(X345 ) + h(X5 ) ≤ h(X35 ) + h(X45 ) 8×

from (3)

h(X34 ) ≤ h(X345 )

from (2)

Each inequality needs to be multiplied by the factor on the left, then added up. The terms 4h(X1 ), 4h(X2 ), h(X3 ), h(X4 ), 8h(X5 ) and 8h(X345 ) occur on both sides and cancel, and what remains is inequality (25). Equivalently, the right-hand side of (25) minus its left-hand side is ZYh (X1 , X2 ; X3 , X4 ) + ZYh (X1 , X2 ; X4 , X3 ) + Ih (X3 ; X4 ) + 4Ih (X1 ; X5 ) + 4Ih (X2 ; X5 ) + 8Ih (X3 ; X4 | X5 ) + 8Hh (X5 | X34 ), 13

(26)

the sum of the slacks of the seven inequalities above, with the same multiplicities. Only the first two use (5); the other five are Shannon inequalities. Note the parallel with (22): the four Shannon terms Hh (X5 | X34 ), Ih (X1 ; X5 ), Ih (X2 ; X5 ), Ih (X3 ; X4 | X5 ) occur with exactly four times their earlier weights, and the extra Ih (X3 ; X4 ) together with the replacement of Ing by ZY is what forces the coefficients 5, 5, 11 and 6 in place of 4, 4, 12 and 4. For the consequence, assume h(e) ≤ 1 for every e ∈ E0 . The coefficients on the left of (25) sum to 29, so its left-hand side is at least 29 mini h(Ui ); the coefficients on the right sum to 38, and every set there is a central edge, so its right-hand side is at most 38. The upper bound 38/29 is not known to be attained. The next lemma gives a lower bound of 130/101. Lemma 9. Define the number a := H2 (1/4) = 2 − 34 log2 3. There exists an edge dominated, almost entropic polymatroid gE on the central graph G0 such that gE (e) = 1 for all edges e ∈ E0 , 130 122 + 10a 130 gE (U1 ) = gE (U2 ) = gE (U3 ) = , gE (U4 ) = gE (U5 ) = > . 101 101 101

(27) (28)

Furthermore, gE satisfies: 50 + 10a 2 < , 101 3 3 72 < . gE (X5 ) = 101 4

gE (X1 ) = gE (X2 ) =

gE (X3 ) = gE (X4 ) =

65 2 < , 101 3 (29)

Proof. We will use the following inequalities below: 4/5 < a < 1 and 35 < 28 . Let R, S be independent fair bits, and let h0 be the entropy function, in bits, of (X1 := R ∧ S, X2 := R ∨ S, X3 := R, X4 := S, X5 := 0). More precisely, h0 is the entropy of the following probability distribution: R S 0 0 0 1 1 0 1 1

X1 := R ∧ S X2 := R ∨ S X3 := R X4 := S X5 := 0 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0

p 1/4 1/4 1/4 1/4

In particular, h0 (X1 ) = h0 (X2 ) = 14 log2 4 + 34 log2 (4/3) = 2 − 43 log2 3 = a, h0 (X3 ) = h0 (X4 ) = 1 and h0 (X5 ) = 0. Notice that the restriction of h0 to X1 , . . . , X4 is precisely the entropic, non-linear polymatroid defined in Section 5. Similarly, let q1 , . . . , q4 be the entropy functions of the following five-tuples; the fair bits used in different independent copies are always fresh (R ⊕ S denotes xor):

q1 q2 q3 q4

X1 X2 X3 X4 X5 0 0 0 R R 0 R 0 S S R R 0 (R, S) S R S 0 (R, S) R ⊕ S 14

Each qj is a linear polymatroid. Let Π consist of the following four permutations of {1, . . . , 5}: Π = {id, (12), (34), (12)(34)}. For π ∈ Π and B ⊆ X, write π(B) := {Xπ(i) : Xi ∈ B}. Thus qj (π(B)) evaluates qj on the set obtained by relabeling the variables in B according to π. For example, if π = (12) and B = X135 , then π(B) = X235 . Define 10h0 + 10s1 + 24s2 + 14s3 + 24s4 1X qj (π(B)), gE = . sj (B) = 4 101 π∈Π

Each π ∈ Π maps central edges to central edges and permutes the sets U1 , . . . , U5 . For example, (12) exchanges U4 and U5 , while (34) exchanges U1 and U2 . Consequently, averaging over these permutations preserves edge domination and any common lower bound on the values at the Ui . Since each qj ◦ π and h0 is an entropy function, gE is a nonnegative combination of entropy vectors and hence almost entropic. More explicitly, X
202gE = 20h0 + 5q1 ◦ π + 12q2 ◦ π + 7q3 ◦ π + 12q4 ◦ π (30) π∈Π

is an actual finite entropy vector: concatenate the indicated integer numbers of independent copies at each coordinate. For transparency, all values claimed above are obtained from the following entropy table: B h0 (B) s1 (B) s2 (B) s3 (B) s4 (B) X1 , X2 a 0 1/2 1 1 1 1/2 1/2 1 1 X3 , X4 X5 0 1 1 1 1 X12 3/2 0 1 1 2 X13 , X14 , X23 , X24 3/2 1/2 1 3/2 3/2 X35 , X45 1 1 1 3/2 3/2 X123 , X124 2 1/2 3/2 3/2 2 X34 2 1 1 2 2 X15 , X25 a 1 3/2 2 2 Substitution gives (27)–(29); every strict inequality there uses only 4/5 < a < 1. This explicitly separates the entropic optimization on the central graph from its Ingleton upper bound, since 130/101 > 9/7; consistently with Lemma 8, 130/101 < 38/29. For the upper bound 38/29 we verified with a linear programming solver that it is tight for the relaxation from which we derived it: 38/29 is the exact value of maxh M (h) over the edge dominated polymatroids on G0 that satisfy every instance of the Zhang–Yeung inequality (5). That relaxation is a polyhedron containing Γ̄∗X ∩ ED(G0 ), so for Γ∗X or Γ̄∗X the value 38/29 is only an upper bound, and we do not know whether it is tight. Nor can a linear programming solver settle the question, because Γ̄∗X is not a polyhedron: maxh∈Γ̄∗ ∩ED(G0 ) M (h) is not the optimum of any linear program. X

7.5

General Polymatroids

Lemma 10. Every polymatroid h ∈ ΓX satisfies h(X123 ) + h(X124 ) + h(X34 ) ≤ h(X13 ) + h(X23 ) + h(X14 ) + h(X24 ).

(31)

In particular, if h is an edge dominated polymatroid on the central graph G0 then mini h(Ui ) ≤ 4/3. 15

Proof. The inequality follows immediately by adding up the following inequalities: 1×

h(X123 ) + h(X3 ) ≤ h(X13 ) + h(X23 )

from (3)

1×

h(X124 ) + h(X4 ) ≤ h(X14 ) + h(X24 )

from (3)

h(X34 ) ≤ h(X3 ) + h(X4 )

1×

from (1), (3)

For the consequence, assume h(e) ≤ 1 for every e ∈ E0 . The LHS of (31) is h(U1 ) + h(U2 ) + h(U3 ) ≥ 3 mini h(Ui ), while the RHS is ≤ 1 + 1 + 1 + 1 = 4 for any edge dominated polymatroid. The bound 4/3 is attained, by an explicit polymatroid. Lemma 11. There exists an edge dominated polymatroid gP ∈ ΓX on the central graph G0 such that gP (Ui ) = 4/3 for i = 1, . . . , 5. Furthermore, the polymatroid gP satisfies gP (Xi ) = 2/3 for i = 1, . . . , 5, and gP (B) = 4/3 for every B ⊆ X that is contained in no central edge. Proof. Recall from Eq. (10) in Section 5 the polymatroid induced by a graph, and apply it to the def

central graph: set gP (U ) = 13 fG0 (U ) for all U ⊆ X. Observe that gP (e) = 1 for every edge e ∈ E0 , so gP is edge dominated, and that gP (Xi ) = 2/3. Since every central edge has two elements, the sets contained in some central edge are exactly ∅, the five singletons and the seven elements of E0 , so gP (B) = 4/3 precisely when B is contained in no central edge. By (11) no Ui is contained in a central edge. We also observe that gP (Ui ) = 4/3 for i = 1, . . . , 5. This proves the lemma.

8

The Big Graph

We now use the central bounds of Theorem 2 to prove the width separations on the big graph G. The scaffolding introduced in Section 6 connects the values M (h) = mini h(Ui ) to the values of bags in tree decompositions. For the upper bounds, Lemma 12 constructs, for every edge dominated polymatroid h, a tree decomposition showing that wh (G) ≤ max{6, 5 + M (h)}. Thus each central upper bound gives an upper bound on the corresponding width of G. For the lower bounds, Lemma 13 identifies a bag in every tree decomposition that contains some Ui and meets every edge joining an anchor to a connector. For adaptive width, this forces a bag with at least 12 vertices, giving the lower bound 6 under the uniform modular polymatroid h(B) = |B|/2. For the other four widths, we extend each central witness g0 to an edge dominated polymatroid Fg0 of the same class on G. The extension ensures that the scaffolding contributes 5 to the value of the selected bag, so Lemma 16 gives wFg0 (G) ≥ 5 + M (g0 ). Together, these bounds yield the separations stated in Theorem 1. Throughout this section we denote by N [x] the closed neighborhood of a node x, that is, {x} together with all neighbors of x. For every a ∈ Ai and 1 ≤ k ≤ ri , set Ka,k = {a, pi,k }.

16

8.1

The Decomposition Lemma

Recall from Section 7 that M (h) = min(h(U1 ), h(U2 ), h(U3 ), h(U4 ), h(U5 )) (Eq. (12)). Lemma 12. For every edge-dominated polymatroid h on G, wh (G) ≤ max(6, 5 + M (h)). By Theorem 2, maxh M (h) ∈ [1, 4/3] when h ranges over any of the classes of polymatroids considered in this paper. Therefore, the dominant term for wh is 5 + M (h), a quantity coming from the central graph G0 , for which we have precise bounds from Theorem 2. The contribution of the rest of the big graph G to wh is at most 6 and we will ignore it when we compute the upper bounds of the various notions of width. Proof of Lemma 12. It suffices to describe one tree decomposition T for which maxt∈V (T ) h(Bt ) ≤ max(6, 5 + M (h)). We show T in Figure 2 and describe it here. We will refer to the components of the big graph G as defined in Section 6: anchor nodes A, and connector nodes p. Choose i ∈ {1, . . . , 5} minimizing h(Ui ), and take j = 2 if i = 1, otherwise j = 1. Construct the following three bags, call them main bags, and connect them in a chain: C1 = A ∪ U i ,

C2 = (A \ Ai ) ∪ (Ui ∪ Uj ),

C3 = (A \ (Ai ∪ Aj )) ∪ X.

For each connector pi,ℓ , ℓ = 1, . . . , ri , create a bag N [pi,ℓ ] consisting of its closed neighborhood, and connect it to C1 . Similarly, for each connector in group j create a bag N [pj,ℓ ] and attach it to C2 . For all remaining connector nodes p, create a bag N [p] and attach it to C3 . The resulting tree is sketched in Figure 2. The complete tree for the case i = 1 is shown in Figure 3: it has 20 bags (ignore the function FE for now). This is a correct tree decomposition, because all neighbors of pk,ℓ are included in Ak ∪ Uk , which, by construction, belongs to the appropriate main bag C1 , C2 , or C3 respectively: Ai ∪ Ui ⊆ C1 , Aj ∪ Uj ⊆ C2 , and Ak ∪ Uk ⊆ C3 for k ∈ / {i, j}. The first main bag covers all anchor edges and the last covers all central edges. Along the main path central vertices are only added and anchors only removed, so all vertex occurrences are connected. Recall that the anchor nodes consist of five sets: A = A1 ∪ · · · ∪ A5 , and any two of them, Ak and Ak′ , induce a complete bipartite graph, K2,2 , with 4 edges. Consider the union of any 2 ≤ m ≤ 5 of the anchor groups. Their induced subgraph has a fractional edge cover of weight m, because there are 2m vertices, and each vertex has exactly 2(m − 1) neighbors. If we give every edge a weight of
1/[2(m − 1)], then every vertex is covered. There are m 4 = 2m(m − 1) edges in this induced · 2 1 subgraph, so the total weight is 2m(m − 1) · 2(m−1) = m. By (4) with m = 5, 4, 3, for any edge dominated polymatroid h, the anchor parts of C1 , C2 , C3 have values at most 5, 4, 3, more precisely h(A) ≤ 5, h(A \ Ai ) ≤ 4 and h(A \ (Ai ∪ Aj )) ≤ 3. For i = 1, 2, 3, the set Ui ∪ Uj = X1234 is covered by X13 , X24 ; for i = 4, 5, the set Ui ∪ Uj = X1235 is covered by X12 , X35 . The whole central graph is covered by X12 , X35 , X45 . Consequently h(C1 ) ≤ 5 + h(Ui ),

h(C2 ) ≤ 6,

h(C3 ) ≤ 6.

It remains to compute h(N [p]) for every connector node p. Each connector has degree at most five, and its incident edges cover all its neighbors, N [p]. Thus every connector bag N [p] has h(N [p]) ≤ 5. This completes the proof of Lemma 12.

17

N [pi,1 ]

C1 = A ∪ Ui

.. .

anchors ≤ 5, central part Ui

h(C1 ) ≤ 5 + h(Ui )

N [pi,ri ]

C2 = (A \ Ai ) ∪ (Ui ∪ Uj )

N [pj,1 ]

.. .

anchors ≤ 4, central part in two central edges

h(C2 ) ≤ 4 + 2 = 6

N [pj,rj ]

C3 = A \ (Ai ∪ Aj ) ∪ X

N [pk,1 ]

anchors ≤ 3, central part in three central edges

.. .

the ri connectors of group i

the rj connectors of group j

the connectors of the other three groups

N [pk,rk ]

h(C3 ) ≤ 3 + 3 = 6

Figure 2: The tree decomposition of Lemma 12: a path of three main bags with the 17 connector leaves hung off it. Here i minimizes h(Ui ) and j = 2 if i = 1, else j = 1. Every leaf is N [p] = {p} ∪ Ak ∪ Uk for a connector p = pk,l ; its own incident edges cover it, so h(N [p]) ≤ deg(p) ≤ 5. Along the path central vertices are only added and anchors only removed, which is what makes all vertex occurrences connected; C1 carries all anchor edges and C3 all central edges. Only the bound for C1 can exceed 6, and it does so by h(Ui ) − 1.

8.2

The Bramble Lemma

For the lower bounds, we need to show that every tree decomposition has a single bag that captures both a central contribution and a contribution from the anchors and connectors. More precisely, the bag should contain some Ui and meet every anchor–connector pair Ka,k . We enforce these requirements using a bramble: a family of connected vertex sets that pairwise intersect or are joined by an edge. We say that two such sets touch. Every tree decomposition has a bag meeting all members of a bramble (see Bellenbaum and Diestel [BD02, proof of Theorem 5]). We recall the short argument below. Our family consists of the anchor–connector pairs together with the complements X \ e of the central edges. Meeting all these complements forces the central part of the bag to contain some Ui . Lemma 13. Every tree decomposition of G has a bag B such that B ∩ X contains some Ui and B meets every Ka,k . Proof. Consider the family B = {X \ e : e ∈ E0 } ∪ {Ka,k : a ∈ Ai , 1 ≤ i ≤ 5, 1 ≤ k ≤ ri }. We first verify that B is a bramble. Each central complement induces a path or a triangle, and each Ka,k is an edge, so every member is connected. There are three types of pairs to consider. Two central complements intersect because each contains three of the five central vertices. Next, consider two anchor–connector pairs Ka,k and Ka′ ,ℓ . If a = a′ , they intersect at their common anchor. If the anchors belong to different groups, the edge {a, a′ } joins the two pairs. If the anchors are distinct but belong to the same group Ai , the edge {a, pi,ℓ } joins them. Finally, consider a central complement X \ e and a pair Ka,k with a ∈ Ai . No Ui is contained in a central edge, as noted in Section 6, so there is a vertex x ∈ Ui \ e. The edge {x, pi,k } joins the complement to the pair. Thus all members of B pairwise touch. 18

C1 = A ∪ X123

13 vertices

N [p1,1 ]

anchors 5; central part U1 = X123

N [p1,2 ]

635 FE (C1 ) = 5 + 130 101 = 101

N [p1,3 ]

C2 = (A \ A1 ) ∪ X1234

12 vertices

N [p2,1 ]

anchors 4; X1234 covered by X13 , X24

N [p2,2 ]

154 = 558 FE (C2 ) = 4 + 101 101

N [p2,3 ]

N [p3,1 ] N [p3,2 ] N [p3,3 ]

C3 = A \ (A1 ∪ A2 ) ∪ X

11 vertices

N [p4,1 ] N [p4,2 ]

anchors 3; X covered by X12 , X35 , X45

N [p4,3 ]

457 FE (C3 ) = 3 + 154 101 = 101

N [p4,4 ] N [p5,1 ] N [p5,2 ] N [p5,3 ] N [p5,4 ]

Leaf bags: N [p1,k ] = {p1,k } ∪ A1 ∪ X123 , N [p2,k ] = {p2,k } ∪ A2 ∪ X124 , N [p3,k ] = {p3,k } ∪ A3 ∪ X34 , N [p4,k ] = {p4,k } ∪ A4 ∪ X15 , N [p5,k ] = {p5,k } ∪ A5 ∪ X25 . Every leaf has FE = 231 or 223+10a , both below 73 . 101 101

Figure 3: The complete tree decomposition from Figure 2, assuming i = 1 (hence j = 2), with the entropic witness FE of (32) evaluated on all 20 bags. Leaf colors are the anchor-group colors of Figure 1. The maximum is attained at the single bag C1 , giving wFE (G) = 635/101; every other bag is below 6. For i ∈ {4, 5} the shape is the same, with Ui as the central part of C1 , central part X1235 in C2 covered by X12 , X35 instead of X13 , X24 , and the leaf fans redistributed among the three hosts.

19

Now fix any tree decomposition (T, (Bt )t∈V (T ) ) of G. For each S ∈ B, let TS = {t ∈ V (T ) : Bt ∩ S ̸= ∅}. This is a nonempty connected subtree of T as the bags containing each vertex v ∈ S form a nonempty connected subtree, and the subtrees for adjacent vertices of S intersect in a bag containing their edge. Since S is connected, the union of these vertex subtrees is connected. Moreover, if two members S, S ′ of B intersect at a vertex, any bag containing that vertex belongs to both TS and TS ′ . If instead an edge joins S to S ′ , a bag containing that edge belongs to both subtrees. Hence the subtrees TS pairwise intersect. The Helly property for subtrees of a tree states that a finite family of pairwise intersecting subtrees has a common node. Applying it here gives a node t whose bag B = Bt meets every member of B. In particular, for every e ∈ E0 we have B ∩ (X \ e) ̸= ∅

⇐⇒

B ∩ X ̸⊆ e.

Thus the central part B ∩ X is contained in no central edge. The sets U1 , . . . , U5 are exactly the minimal subsets of X with this property, as shown in Section 6, so B ∩ X contains some Ui . The bag B also meets every Ka,k , since these pairs are members of B.

8.3

The Exact Adaptive Width

Lemma 14. The 32-vertex graph G satisfies adw(G) = 6. Proof. For the upper bound, let h be an edge dominated modular polymatroid on G. Its restriction to the nodes X of the central graph G0 is again modular and edge dominated. Lemma 3 gives mini h(Ui ) ≤ 1, while Lemma 12 implies wh (G) ≤ max{6, 5 + 1} = 6. Taking the supremum proves adw(G) ≤ 6. For the lower bound, let h(B) = |B|/2 for every B ⊆ V (G). This is a modular polymatroid, and it is edge dominated since every edge has value 1. Lemma 13 gives a bag B whose central part contains some Ui and which meets every Ka,k . Thus |B ∩ X| ≥ 2. For each anchor group Ai , either B contains both anchors, or an omitted anchor forces B to contain all ri ≥ 3 connectors of that group. Hence B contains at least two vertices from each of the five groups of anchors and connectors. Consequently, |B| ≥ 2 + 5 · 2 = 12, h(B) ≥ 6. Therefore adw(G) ≥ wh (G) ≥ 6. This proves the lemma.

8.4

Extending a Central Witness to the Big Graph

Given any function g0 : 2X → R+ on the central graph, extend it to all vertices of G by Fg0 (B) = g0 (B ∩ X) +

ri 5 X 1 XX i=1

2ri

1{B∩Ka,k ̸=∅} .

(32)

a∈Ai k=1

We notice that the sum we added to g0 is a normal polymatroid, because it is a positive linear combination of step functions (Section 2). This implies that, if g0 is a normal, or linear, or almost entropic, or general polymatroid, then so is Fg0 . Each of the four lower bounds below is obtained 20

by substituting for g0 the corresponding witness on the central graph from Section 7. We record conditions for (32) to be edge dominated and a lower bound on its value on a bag of every tree decomposition. Note that Fg0 (B) = g0 (B) for B ⊆ X, since every Ka,k is disjoint from X. Lemma 15. Suppose that g0 (e) ≤ 1 for every e ∈ E0 , that g0 (Xi ) ≤ 2/3 for i = 1, . . . , 4, and that g0 (X5 ) ≤ 3/4. Then Fg0 is edge dominated on G. Proof. Central edges have value g0 (e) ≤ 1. Each anchor meets all ri coverage sets belonging to it, for total value 1/2; an anchor–anchor edge therefore has value one. A connector in group i meets two coverage sets, one for each anchor, for value 1/ri . Consequently an anchor–connector edge has value 1/2 + 1/(2ri ) ≤ 1. A central–connector edge {x, pi,k } has value g0 (x) + 1/ri , where x ∈ Ui . For i = 1, 2, 3 we have ri = 3 and Ui ⊆ X1234 , so this is at most 2/3 + 1/3 = 1; for i = 4, 5 we have ri = 4 and Ui ⊆ X125 , so it is at most 3/4 + 1/4 = 1. These are all edge types. Lemma 16. For every monotone g0 : 2X → R+ , every tree decomposition of G has a bag B such that Fg0 (B) ≥ min g0 (Ui ) + 5. i

Proof. Let B be a bag given by Lemma 13. Meeting every Ka,k makes every coverage term in (32) attain its full value. There are ten anchors, each contributing 1/2, for a total of five. Since g0 is monotone, g0 (B ∩ X) ≥ g0 (Ui ) ≥ mini g0 (Ui ), and the displayed bound follows.

8.5

The Exact Normal Width

Lemma 17. The 32-vertex graph G satisfies normw(G) = 69/11. Proof. For the upper bound, let h be an edge-dominated normal polymatroid on G. Its restriction to the nodes X of the central graph G0 is again normal, since deleting the variables outside X from a coverage function leaves a coverage function, and it is edge dominated on (X, E0 ). So Theorem 2 (more precisely, Lemma 4) gives mini h(Ui ) ≤ 14/11, while Lemma 12 implies   14 69 wh (G) ≤ max 6, 5 + = , 11 11 since 69/11 > 6. Taking the supremum proves normw(G) ≤ 69/11. For the lower bound, let FN := FgN be the extension (32) of the normal witness gN of (19). This is normal. Indeed, gN is a nonnegative combination of step functions on X by (19), and for K ⊆ X the extension B 7→ hK (B ∩ X) is again the step function hK , now on V (G); each term 1{B∩Ka,k ̸=∅} is the step function hKa,k ; and a nonnegative combination of step functions is normal. FN is edge dominated by Lemma 15: central edges have value gN (e) ≤ 1 by Lemma 5, and by (18) the singletons satisfy gN (Xi ) ≤ 7/11 < 2/3 for i = 1, . . . , 4 and gN (X5 ) = 8/11 < 3/4. Lemma 16 now gives a bag B with FN (B) ≥ min gN (Ui ) + 5 = i

14 69 +5= , 11 11

and normw(G) ≥ wFN (G) ≥ 69/11. Comparing with Lemma 14, normw(G) − adw(G) = 21

69 3 −6= > 0, 11 11

so G separates adaptive width from normal width. The normal witness gN also violates the modular identity (15): its left-hand side is gN (U3 ) + gN (U4 ) + gN (U5 ) = 42 11 , while its right-hand side is gN (X12 ) + gN (X35 ) + gN (X45 ) = 32 . 11

8.6

The Exact Linear Width

Lemma 18. The 32-vertex graph G satisfies linw(G) = 44/7. Proof. For the upper bound, let h ∈ Lin32 be edge dominated on G. Its restriction to the nodes X of the central graph G0 belongs to LinX and is edge dominated on (X, E0 ). Lemma 6 gives mini h(Ui ) ≤ 9/7. Lemma 12 implies   9 44 wh (G) ≤ max 6, 5 + = , 7 7 since 44/7 > 6. Taking the supremum proves linw(G) ≤ 44/7. For the lower bound, let FL := FgL be the extension (32) of the linear witness gL = r/14 of Lemma 7. This is linear. Indeed gL is a linear polymatroid on X, and extending it by B 7→ gL (B ∩X) keeps it one, assigning the empty set of vectors to every vertex outside X; each coverage term is normal, hence linear; and clearing denominators, XXX XXX 168 FL = 12 r + 28 1{ · ∩Ka,k ̸=∅} + 21 1{ · ∩Ka,k ̸=∅} i≤3 a∈Ai k

i≥4 a∈Ai k

is a nonnegative integer combination of rank functions, hence itself the rank function of the direct 1 ′ sum of the corresponding vector configurations. So FL = 168 r with r′ a rank function, and FL ∈ Lin32 . FL is edge dominated by Lemma 15: central edges have value gL (e) ≤ 1 by Lemma 7, and by (23) the singletons satisfy gL (Xi ) ≤ 9/14 < 2/3 for i = 1, . . . , 4 and gL (X5 ) = 5/7 < 3/4. Lemma 16 now gives a bag B with FL (B) ≥ min gL (Ui ) + 5 = i

44 9 +5= , 7 7

giving linw(G) ≥ wFL (G) ≥ 44/7. Comparing with Lemma 17, linw(G) − normw(G) =

44 69 484 − 483 1 − = = > 0, 7 11 77 77

so G separates normal width from linear width. The linear witness also violates the covering inequality (16): the configuration (24) has r(X123 ) + r(X124 ) + 5r(X34 ) + 2r(X15 ) + 2r(X25 ) = 198 while 2r(X13 ) + 2r(X14 ) + 2r(X23 ) + 2r(X24 ) + 3r(X35 ) + 3r(X45 ) = 196.

8.7

The Entropic Width

Lemma 19. The 32-vertex graph G satisfies 183 635 ≤ entw(G) ≤ . 101 29

22

Proof. For the upper bound, the restriction to X of any edge dominated almost entropic function on G is almost entropic on X and edge dominated on (X, E0 ), so Lemma 8 applies. Lemma 12 then gives   183 38 = wh (G) ≤ max 6, 5 + . 29 29 Therefore entw(G) ≤ 183/29. For the lower bound, let gE be the almost entropic polymatroid on the central graph constructed in Lemma 9, and let FE := FgE be its extension (32) to G. Every coverage term is the entropy profile of a random variable copied to the two vertices in Ka,k , with constant values at all other vertices. Choose these variables independently of one another and of the central graph. Thus FE is almost entropic. There is also a direct finite realization after multiplying by 2424: take twelve independent copies of the vector in (30), and for each Ka,k share 2424/(2ri ) fresh independent fair bits between its two vertices. These numbers are 404 for ri = 3 and 303 for ri = 4. The resulting entropy vector is exactly 2424FE . By (27) and (29) the function gE satisfies the hypotheses of Lemma 15, so FE is edge dominated; and mini gE (Ui ) = 130/101 by (28), so Lemma 16 produces a bag B with FE (B) ≥ 130/101 + 5 = 635/101. Hence entw(G) ≥ wFE (G) ≥ 635/101. In fact Lemma 12 shows wFE (G) = 635/101, because mini FE (Ui ) = 130/101 and 5 + 130/101 = 635/101 > 6. Comparing with Lemma 18, entw(G) − linw(G) ≥

635 44 1 − = > 0, 101 7 707

so G separates linear width from entropic width. The almost entropic witness gE also violates the linear rank inequality (21). Indeed, its left-hand side is gE (X123 ) + gE (X124 ) + 3gE (X34 ) + gE (X15 ) + gE (X25 ) =

894 + 20a > 9, 101

where the strict inequality follows from a > 4/5. Its right-hand side is 9, since gE (e) = 1 for every central edge.

8.8

The Exact Submodular Width

Lemma 20. The 32-vertex graph G satisfies subw(G) = 19/3. Proof. For the upper bound, Lemma 10 and Lemma 12 give wh (G) ≤ max{6, 5 + 4/3} = 19/3 for every edge-dominated polymatroid h, proving subw(G) ≤ 19/3. For the lower bound, let gP be the edge dominated polymatroid of Lemma 11: it satisfies gP (e) = 1 for e ∈ E0 , and gP (B) = 4/3 whenever B is contained in no central edge, so gP (Ui ) = 4/3 for every i. Let FP := FgP be the extension (32) of gP . This is a polymatroid, being a nonnegative combination of gP and the coverage functions B 7→ 1{B∩K̸=∅} , and it is edge dominated by Lemma 15, since gP (e) = 1 for e ∈ E0 and gP (Xi ) = 2/3 for every i. Lemma 16 now gives a bag B with FP (B) ≥ min gP (Ui ) + 5 = i

This proves the matching lower bound. 23

4 19 +5= . 3 3

Comparing with Lemma 19, subw(G) − entw(G) ≥

19 183 2 − = > 0, 3 29 87

so G separates entropic width from submodular width. The polymatroid witness gP also violates inequality (25). Its left-hand side is 5gP (X123 ) + 5gP (X124 ) + 11gP (X34 ) + 4gP (X15 ) + 4gP (X25 ) = 116 3 > 38. Its right-hand side is 38, since gP (e) = 1 for every central edge.

8.9

Proof of the Separation Theorem

Proof of Theorem 1. Let G be the 32-vertex graph defined in Section 6. Lemmas 14, 17, 18, 19, and 20 give, respectively, adw(G) = 6,

normw(G) =

183 635 ≤ entw(G) ≤ , 101 29

69 , 11

linw(G) =

subw(G) =

44 , 7

19 . 3

The strict separations follow from 69 3 −6= > 0, 11 11 635 44 1 − = > 0, 101 7 707

44 69 1 − = > 0, 7 11 77 19 183 2 − = > 0. 3 29 87

This proves the theorem. Computer-aided Validation. This proves the separation for the 32-vertex graph specified here. The proof is algebraic and combinatorial; the companion script verify.py independently checks the entropy table, edge feasibility, every displayed decomposition, the bramble incidences, every bag value drawn in Figure 3, all three information-inequality certificates (22), (26) and (20), the equivalence of (6)–(5) with their usual formulations, the atom-by-atom check behind (16) together with the normal witness (19), every rank of the subspace arrangement (24), and the exact normal-, linear- and submodular-width witnesses. It also parses the Tik Z source of Figure 1 and checks that the edge set actually drawn there is exactly E(G), and that the pentagon claim made in its caption holds. Finally, it confirms by linear programming that the bounds 14/11, 9/7 and 4/3 cannot be improved: they are the exact optima of maxh mini h(Ui ) over the edge dominated normal polymatroids on G0 , over the edge dominated polymatroids satisfying every instance of (6), and over all edge dominated polymatroids, respectively, and the witnesses gN , gL and gP attain them. It also confirms that 38/29 cannot be improved over the Zhang–Yeung relaxation; as discussed after Lemma 9, that leaves the entropic value undetermined.

9

Conclusions

We have separated the notions of adaptive, normal, linear, entropic, and submodular width by using a single graph G with 32 vertices. We leave two open problems. The first is to study the connection between the various notions of width and fine-grained complexity lower bounds. The currently known fine-grained complexity lower bounds in [FKZ23] use a clique embedding, which is a further restriction of a normal polymatroid. For patterns with higher complexity, Bringmann and Gorbachev [BG25] use a reduction from the 3SUM conjecture, which appears to have similarities 24

with the linear width. The question we raise is if there exists a general rule connecting the notions of width with fine-grained complexity reductions. Second, we leave open the question of identifying “natural” classes of graphs where the submodular width coincides with simpler notions of width. If matched with appropriate fine-grained reductions, these restricted classes are the most likely candidates for patterns for which the exact complexity can be characterized, i.e. the lower and upper bounds coincide.

Acknowledgements The work of Lanzinger and Merkl was partially supported by the Vienna Science and Technology Fund (WWTF) [10.47379/ICT2201]. Suciu was partially supported by NSF 2507117 and NSF SHF 2312195.

References [BD02]

Patrick Bellenbaum and Reinhard Diestel. Two short proofs concerning tree-decompositions. Combinatorics, Probability and Computing, 11(6):541–547, 2002.

[BG25]

Karl Bringmann and Egor Gorbachev. A fine-grained classification of subquadratic patterns for subgraph listing and friends. In Michal Koucký and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czechia, June 23-27, 2025, pages 2145–2156. ACM, 2025.

[DFZ09] Randall Dougherty, Chris Freiling, and Kenneth Zeger. Linear rank inequalities on five or more variables. CoRR, abs/0910.0284, 2009. [FKZ23] Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. The fine-grained complexity of boolean conjunctive queries and sum-product problems. In Kousha Etessami, Uriel Feige, and Gabriele Puppis, editors, 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn, Germany, July 10-14, 2023, volume 261 of LIPIcs, pages 127:1–127:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. [FKZ24] Austen Z. Fan, Paraschos Koutris, and Hangdong Zhao. Tight bounds of circuits for sum-product queries. Proc. ACM Manag. Data, 2(2):87, 2024. [Ing71]

A. W. Ingleton. Representation of matroids. In D. J. A. Welsh, editor, Combinatorial Mathematics and its Applications, pages 149–167. Academic Press, London, 1971.

[JR16]

Manas Joglekar and Christopher Ré. It’s all a matter of degree: Using degree information to optimize multiway joins. In Wim Martens and Thomas Zeume, editors, 19th International Conference on Database Theory, ICDT 2016, Bordeaux, France, March 15-18, 2016, volume 48 of LIPIcs, pages 11:1–11:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.

[KNS17] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 429–444. ACM, 2017. Extended version available at http://arxiv.org/abs/1612.02503. 25

[KNS25] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu. PANDA: query evaluation in submodular width. TheoretiCS, 4, 2025. [Mar13] Dániel Marx. Tractable hypergraph properties for constraint satisfaction and conjunctive queries. J. ACM, 60(6):42:1–42:51, 2013. [Suc23]

Dan Suciu. Applications of information inequalities to database theory problems. In 38th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023, pages 1–30. IEEE, 2023.

[ZY98]

Zhen Zhang and Raymond W Yeung. On characterization of entropy function via information inequalities. IEEE Transactions on Information Theory, 44(4):1440–1452, 1998.

26

Related documents

• Separating Notions of Graph Width: the Adaptive, Normal, Linear, Entropic, and Submodular Width#1145185
• Awesome graph parameters#1063805
• Outer-clique Roman dominating function in graphs#72023
• The maximum number of edges in minimal matching covered graphs#1105537
• Polynomial Lower Bounds for Distributed Graph Sketching with Tiny Error: Connectivity and Spanning Tree Construction#973425