9 Pathwidth sequences and the bootstrap
The two previous sections bound the pathwidth of graphs of maximum degree at most \(k\in\{3,4,5\}\) by \(\sum_{d=3}^ka_dn_d+o(n)\), for several coefficient vectors \((a_3,\dots,a_k)\), none of which is best for all graphs (Theorems 7.1, 7.2, 8.1 and 8.2). This section states all of them in one format, the pathwidth sequence, and extends each of them to all graphs by the bootstrap lemma (Lemma 9.3). In this format, a vertex of degree at most \(2\) adds nothing to the bound, a vertex of degree \(d\ge3\) adds its coefficient \(a_d\), and a vertex whose degree is beyond the given coefficients adds \(1\), which is what putting it into every bag adds to the width. Applied to the triple \(\mathsf{S}=(\frac5{32},\frac14,\frac{11}{32})\) of Theorem 7.2, the bootstrap lemma gives the bound for all graphs (Theorem 1.3) and the bound in terms of edges (Corollary 1.4).
The sequences below use the constants \[c_{3}=\frac{3}{4\pi}\arccos\frac56\approx 0.1398221,\qquad F_3\approx 0.1401583,\qquad F_4\approx 0.2457720,\] where \(F_3\) and \(F_4\) are the maxima of the ideal \(3\)-star and \(4\)-star functions with edge correlations \(\frac{2\sqrt2}{3}\) and \(\frac{\sqrt3}{2}\), defined in Section 6; certified enclosures are given in Proposition 6.9.
Definition 9.1 (pathwidth sequence). A sequence \(a=(a_d)_{d\ge3}\) of reals is a pathwidth sequence if there is a function \(\rho(n)=o(n)\) such that every graph \(G\) satisfies \(\mathop{\mathrm{pw}}(G)\le\sum_{d\ge3}a_d\,n_d+\rho(n)\). A finite tuple \((a_3,\dots,a_k)\) stands for the sequence that continues it with \(a_d=1\) for all \(d>k\).
Lean proof: PwSeq.targetRhoForm (what is formalised)
So a finite tuple \((a_3,\dots,a_k)\) is a pathwidth sequence if and only if there is a function \(\rho(n)=o(n)\) with \(\mathop{\mathrm{pw}}(G)\le\sum_{d=3}^ka_dn_d+\sum_{d>k}n_d+\rho(n)\) for every graph \(G\).
Two consequences of the definition are used below. A sequence that is entrywise at least a pathwidth sequence is again one. For a graph \(G\) of maximum degree at most \(k\), a pathwidth sequence \((a_3,\dots,a_k)\) gives the bound \(\mathop{\mathrm{pw}}(G)\le\sum_{d=3}^ka_dn_d+o(n)\).
Theorem 9.2 (pathwidth sequences). Each of the following six tuples is a pathwidth sequence: \[\mathsf{C}=(c_{3}),\qquad \mathsf{M}=(c_{3},\,0.2627),\qquad \mathsf{F}=(F_4,\,F_4),\] \[\mathsf{S}=\bigl(\tfrac{5}{32},\,\tfrac14,\,\tfrac{11}{32}\bigr),\qquad \mathsf{P}=(F_3,\,0.2575,\,0.3667),\qquad \mathsf{R}=(0.1455,\,0.2530,\,0.3600).\]
Lean proof for all six sequences, \(\mathsf{C}\) without hypotheses: PwSeq.targetThm1C, PwSeq.targetThm1F, PwSeq.targetThm1P, PwSeq.targetThm1R, PwSeq.targetThm1S, Sw4.targetThm1M (what is formalised)
For graphs of maximum degree at most \(k\), the six bounds are those of Theorem 8.1 (\(\mathsf{C}\)), Theorem 8.2 (\(\mathsf{M}\)), Theorem 7.1(a) (\(\mathsf{F}\)) and Theorem 7.2 (\(\mathsf{P}\), \(\mathsf{R}\), \(\mathsf{S}\)), stated in Sections 8 and 7. In particular, every graph of maximum degree \(3\) satisfies \(\mathop{\mathrm{pw}}(G)\le c_{3}n_3+o(n)\), and every graph of maximum degree \(4\) satisfies \(\mathop{\mathrm{pw}}(G)\le c_{3}n_3+0.2627\,n_4+o(n)\) and \(\mathop{\mathrm{pw}}(G)\le F_4(n_3+n_4)+o(n)\).
The sequence \(\mathsf{M}\) is entrywise below \(\mathsf{C}\), so \(\mathsf{M}\) implies \(\mathsf{C}\). We list \(\mathsf{C}\) nevertheless: its proof uses no computation, while that of \(\mathsf{M}\) rests on computer-assisted certificates (Appendix A.3.1). Apart from this pair, none of the six sequences is entrywise below another, and each of \(\mathsf{M},\mathsf{F},\mathsf{P},\mathsf{R},\mathsf{S}\) gives the smallest bound of the six for some graphs (Remark A.18).
9.1 The bootstrap lemma
Each of the six sequences has coefficients up to some degree \(k\le5\) only, so every vertex of degree above \(k\) adds \(1\) to its bound. The bootstrap lemma replaces these coefficients \(1\) by the entries of the following recurrence, which are at most \(1\), and smaller than \(1\) in every row of Table 4 except \(\mathsf{F}\).
Let \(k\ge3\) and let \(0\le b_3\le\dots\le b_k\) be reals, and put \(b_0=b_1=b_2:=0\). For every \(d\ge3\) for which \(b_d\) is defined, the increment \(h_d\) and the running minimum \(H_d\) are \[h_d:=b_d-b_{d-1},\qquad H_d:=\min_{3\le i\le d}h_i .\] Thus \(h_3=b_3\), the sequence \(H\) is nonincreasing, and \(H_d\le h_d\) and \(H_d\le h_3=b_3\) for every \(d\ge3\). The bootstrap of \((b_3,\dots,b_k)\) is the infinite sequence \((b_d)_{d\ge3}\) obtained by defining \(b_d\) for \(d=k+1,k+2,\dots\) in turn by \[\begin{equation*} \tag{9.1} b_d:=\max\Bigl\{\frac{1+(d-1)\,b_{d-1}-H_{d-1}}{d},\;1-d\,H_{d-1}\Bigr\} \qquad(d>k). \end{equation*}\] This is well defined, since \(H_{d-1}\) depends only on \(b_3,\dots,b_{d-1}\). For a graph \(G\) we write \[\psi_b(G):=\sum_{v\in V(G)}b_{d_G(v)}=\sum_{d\ge3}b_d\,n_d(G);\] vertices of degree at most \(2\) contribute nothing. We drop the subscript \(b\) when the sequence is fixed.
Lemma 9.3 (bootstrap). Let \(k\ge3\) and let \(0\le b_3\le\dots\le b_k\) be reals with \(b_k+H_k\le1\). Suppose that there is a function \(\rho(N)=o(N)\) such that every graph \(J\) with \(\delta(J)\ge3\) and \(\Delta(J)\le k\) satisfies \(\mathop{\mathrm{pw}}(J)\le\sum_{d=3}^kb_d\,n_d(J)+\rho(|V(J)|)\). Then the bootstrap of \((b_3,\dots,b_k)\) is a pathwidth sequence. It is nondecreasing, and all its entries are at most \(1\).
Lean proof: PwSeq.targetBootstrapLemma, PwSeq.targetLemma2 (what is formalised)
The graphs \(J\) in Lemma 9.3 have no vertex of degree above \(k\), so the bound on them holds whenever \((b_3,\dots,b_k)\) is a pathwidth sequence. Conversely, under the hypotheses of Lemma 9.3 the tuple \((b_3,\dots,b_k)\) is entrywise at least its bootstrap, which agrees with it up to degree \(k\) and has all entries at most \(1\); hence the tuple is a pathwidth sequence. This is how Theorem 9.2 follows from Theorems 8.1, 8.2, 7.1 and 7.2 (Appendix A.4.1). The bootstrap is used with \(k=3\) for the seed \(\mathsf{C}\), with \(k=4\) for \(\mathsf{M}\) and \(\mathsf{F}\), and with \(k=5\) for \(\mathsf{P}\), \(\mathsf{R}\) and \(\mathsf{S}\).
Reading the recurrence.
By Lemma 9.6(ii) below, \(b_d\) is determined by \[\begin{equation*} \tag{9.2} 1-b_d=(d-1)\,H_d+H_{d-1}\qquad(d>k). \end{equation*}\] Heuristically (Section 2.5), this identity says that deleting a vertex of degree \(d\) that has a neighbor of smaller degree lowers the potential \(\psi\) by at least \(1\), while putting the vertex back adds at most \(1\) to the width, since \(\mathop{\mathrm{pw}}(G)\le\mathop{\mathrm{pw}}(G-v)+1\). Indeed, the deletion lowers the potential by \(b_d\) for the vertex itself, by at least \(H_{d-1}\) for that neighbor and by at least \(H_d\) for each of the other \(d-1\) neighbors, whose degrees drop by one; by (9.2), these amounts add up to \(1\). The two terms of the maximum in (9.1) are the two cases of Lemma 9.6(iv). Regular graphs, in which no neighbor has smaller degree, are handled by the negative term of the potential \(\psi^-\) in Section 9.3.
Remark 9.4 (the recurrence of Edwards and McDermid). Take \(k=3\) and \(b_3=\alpha\) with \(\frac16\le\alpha\le\frac3{10}\). Then \(H_3=\alpha\) and \(b_3+H_3=2\alpha\le1\). By (9.1), \(b_4=\max\{\frac{1+2\alpha}4,\,1-4\alpha\}=\frac{1+2\alpha}4\), because \(1+2\alpha\ge4-16\alpha\) is equivalent to \(\alpha\ge\frac16\). So \(b_4=g_\alpha(4)\) and \(h_4=\frac{1-2\alpha}4\le\alpha\), whence \(H_4=h_4\). Moreover \(H_3\le3H_4\) is equivalent to \(4\alpha\le3-6\alpha\), that is, \(\alpha\le\frac3{10}\). Hence Lemma 9.7 below applies with \(j=4\), and its last part gives \(d\,b_d=(d-2)\,b_{d-1}+b_{d-2}+1\) for all \(d\ge5\). So \(b=g_\alpha\): Lemma 9.3 with \(k=3\) contains the recurrence of Edwards and McDermid on exactly their range of \(\alpha\). For \(\alpha<\frac16\) the second term wins and \(b_4=1-4\alpha\); for \(\alpha=c_{3}\) this is about \(0.4407\), worse than \(g_{1/6}(4)=\frac13\). This is why a smaller cubic coefficient alone does not improve the coefficients of higher degrees, and why Theorem 1.3 needs the base of maximum degree \(5\) from Theorem 7.2.
Prior work, and what is new.
The induction is that of Fomin, Gaspers, Saurabh and Stepanov (Fomin et al. 2009 Lemma 1), seeded with the cubic bound \(\frac n6+o(n)\) of Fomin and Høie (Fomin and Høie 2006) and extended by Gaspers (Gaspers 2010 Table 6.1), in the form of the reduction theorem of Edwards and McDermid (Edwards and McDermid 2015 Theorem 3.2), whose cost function \(g_\alpha\) satisfies \(d\,g_\alpha(d)=(d-2)\,g_\alpha(d-1)+g_\alpha(d-2)+1\) and needs \(\frac16\le\alpha\le\frac3{10}\); the proofs of Lemma 9.9 and Proposition 9.10 follow theirs step by step. Three things are new. The seeds \(b_3\le\dots\le b_k\) are arbitrary, with the increment of Edwards and McDermid replaced by the running minimum \(H_d\), so that the cubic coefficient \(c_{3}<\frac16\), which their theorem cannot use, and the seeds of Theorem 7.2 are admissible (Remark 9.4). The base is a per-degree bound for all graphs of minimum degree at least \(3\) and maximum degree at most \(k\), not a bound for cubic graphs. And Lemma 4.5 replaces the two facts on reductions taken from Kneis, Mölle, Richter and Rossmanith (Kneis et al. 2009).
The bootstraps of the six sequences.
All six sequences of Theorem 9.2 satisfy the hypotheses of Lemma 9.3. Their bootstraps, rounded up, form Table 4; the bootstrap of \(\mathsf{C}\) is entrywise at least that of \(\mathsf{M}\) and is omitted.
Corollary 9.5 (the bootstraps). Each row of Table 4 is a pathwidth sequence.
Code: bootstrap_table.py
Table 4: The pathwidth sequences of Corollary 9.5. The row named \(X\) is the bootstrap of the sequence \(X\) of Theorem 9.2, rounded up to four decimals; in the last column, the bootstrap is bounded by a closed form. The bootstrap of \(\mathsf{C}\), \((0.1399,\,0.4408,\,0.5247,\,\dots)\), is entrywise at least row \(\mathsf{M}\) and is omitted. Highlighted: the smallest entry of its column. Grey: produced by the bootstrap (9.1). Black entries are those of Theorem 9.2, with \(c_{3}\), \(F_3\) and \(F_4\) rounded up.
| \(a_3\) | \(a_4\) | \(a_5\) | \(a_6\) | \(a_7\) | \(a_8\) | \(a_9\) | \(a_{10}\) | \(a_d\), \(d\ge11\) | |
|---|---|---|---|---|---|---|---|---|---|
| \(\mathsf{M}\) | \(\boldsymbol{0.1399}\) | \(0.2627\) | \(0.3857\) | \(0.4676\) | \(0.5319\) | \(0.5824\) | \(0.6232\) | \(0.6568\) | \(1-\frac{3.77}{d+1}\) |
| \(\mathsf{F}\) | \(0.2458\) | \(\boldsymbol{0.2458}\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) | \(1\) |
| \(\mathsf{P}\) | \(0.1402\) | \(0.2575\) | \(0.3667\) | \(0.4541\) | \(0.5196\) | \(0.5715\) | \(0.6133\) | \(0.6478\) | \(1-\frac{3.87}{d+1}\) |
| \(\mathsf{R}\) | \(0.1455\) | \(0.2530\) | \(0.3600\) | \(0.4489\) | \(0.5149\) | \(0.5673\) | \(0.6096\) | \(0.6444\) | \(1-\frac{3.91}{d+1}\) |
| \(\mathsf{S}\) | \(\frac{5}{32}\) | \(\frac14\) | \(\boldsymbol{\frac{11}{32}}\) | \(\boldsymbol{0.4375}\) | \(\boldsymbol{0.5045}\) | \(\boldsymbol{0.5581}\) | \(\boldsymbol{0.6012}\) | \(\boldsymbol{0.6368}\) | \(\boldsymbol{1-\frac{4}{d+1}}\) |
Among the rows of Table 4, the bootstrap of \(\mathsf{S}\) has the smallest coefficient at every degree \(d\ge5\). Rounded up to closed forms, it gives the bound for all graphs of Theorem 1.3, and through it the bound in terms of edges of Corollary 1.4 (Sections 9.4 and 9.5). Which row of Table 4 is best for a given graph depends only on the proportions of its degrees (Remark A.18, Figure 4).
The decompositions behind the bounds of Theorem 9.2 and Corollary 9.5 can be computed in polynomial time (Theorem 1.5). For the bootstrap of a sequence \(X\) of Theorem 9.2 with entries up to degree \(k\), the algorithm runs the deletion process of the bootstrap lemma and decomposes the remaining components, of maximum degree at most \(k\), by a sweep: the plain sweep for \(\mathsf{F}\), \(\mathsf{P}\), \(\mathsf{R}\) and \(\mathsf{S}\), and the median-switched one for \(\mathsf{C}\) and \(\mathsf{M}\) (Appendices A.5.9 and A.6).
The proof of the bootstrap lemma.
The proof involves no probability. A combinatorial induction deletes vertices of large degree one at a time; putting a deleted vertex back into every bag adds at most one to the width. The number of deletions is at most the potential \(\psi(G)\) of the input graph \(G\): each deletion, together with the reductions that follow it, lowers a modified potential by at least one. Vertices of degree at most \(2\) are removed by the reduction operations of Definition 4.2, and Lemma 4.5 bounds the effect of all reductions on the pathwidth at once, by an additive term \(O(\log n)\). Section 9.2 proves the properties of the bootstrap that the induction needs, and Section 9.3 runs the deletion process and proves Lemma 9.3. Sections 9.4 and 9.5 derive Theorem 1.3 and Corollary 1.4. Appendix A.4 derives Theorem 9.2 and Corollary 9.5 from the lemma and compares the coefficients with the previous ones, and Appendix A.5.9 makes the deletion process algorithmic.
9.2 The extended sequence
We first show that the recurrence keeps the sequence nondecreasing and bounded by \(1\), and that it satisfies (9.2); this is all that the deletion process needs. We also record which term of the maximum is attained, because Lemma 9.7 and the proof of Proposition 9.13 use it. For \(d>k\) put \[\theta_d:=\frac{1-b_{d-1}-H_{d-1}}{d},\] the increment \(h_d\) that the first term of the maximum in (9.1) would give.
Lemma 9.6 (the extended sequence). Let \(k\ge3\), let \(0\le b_3\le\dots\le b_k\) be reals with \(b_k+H_k\le1\), and extend them by (9.1). Then \(h_d\ge0\) and \(H_d\ge0\) for every \(d\ge3\), and for every \(d>k\):
(i) \(b_{d-1}\le b_d\le1\);
(ii) \(1-b_d=(d-1)\,H_d+H_{d-1}\);
(iii) \(b_d+H_d\le1\);
(iv) if \(\theta_d\le H_{d-1}\), then \(b_d\) is the first term of the maximum in (9.1) and \(h_d=H_d=\theta_d\); otherwise \(b_d\) is the second term and \(H_d=H_{d-1}<h_d\).
Proof. We first treat the seeds, and then argue by induction on \(d>k\), comparing both terms of the maximum in (9.1) with \(b_{d-1}\).
For \(3\le d\le k\) we have \(h_d=b_d-b_{d-1}\ge0\), because the seeds are nondecreasing and \(b_2=0\); hence also \(H_d\ge0\).
Now let \(d>k\). The induction hypothesis is that \(H_{d-1}\ge0\) and \(b_{d-1}+H_{d-1}\le1\). For \(d=k+1\) this holds by the first part and by the assumption \(b_k+H_k\le1\). Put \(\mu:=H_{d-1}\ge0\) and \(\theta:=\theta_d\), so that \(\theta=(1-b_{d-1}-\mu)/d\ge0\) by the induction hypothesis. Let \(p\) and \(q\) be the first and second terms of the maximum in (9.1). Then \[p-b_{d-1}=\frac{1-b_{d-1}-\mu}{d}=\theta,\] and since \(1-b_{d-1}=d\theta+\mu\), \[q-b_{d-1}=1-b_{d-1}-d\mu=d\theta-(d-1)\mu=\theta+(d-1)(\theta-\mu).\] Case \(\theta\le\mu\). Then \(q\le p\), so \(b_d=p\) and \(h_d=\theta\). Hence \(H_d=\min\{\mu,\theta\}=\theta\), and \(1-b_d=(1-b_{d-1})-\theta=(d-1)\theta+\mu=(d-1)H_d+H_{d-1}\).
Case \(\theta>\mu\). Then \(q>p\), so \(b_d=q\) and \(h_d=d\theta-(d-1)\mu>d\mu-(d-1)\mu=\mu\). Hence \(H_d=\mu<h_d\), and \(1-b_d=d\mu=(d-1)H_d+H_{d-1}\).
This proves (ii) and (iv). In both cases \(h_d\ge0\) (as \(\theta\ge0\) and \(\mu\ge0\)), so \(b_d\ge b_{d-1}\) and \(H_d\ge0\). By (ii) and \(d\ge2\), \(1-b_d=(d-1)H_d+H_{d-1}\ge(d-1)H_d\ge H_d\ge0\), which gives \(b_d\le1\) and (iii). In particular the induction hypothesis holds for \(d+1\). ∎
Once two consecutive running minima are within a factor \(3\) of each other, the first term of the maximum is attained at every later degree, and the running minima follow a linear recurrence. If, in addition, the increment \(h_j\) at the later degree \(j\) equals \(H_j\), then from there on the extended sequence satisfies the recurrence of Edwards and McDermid. This is how the coefficients of Theorem 1.3 are computed.
Lemma 9.7 (the concave regime). Let \(b\) be as in Lemma 9.6, and suppose that \(H_j\le H_{j-1}\le3H_j\) for some \(j>k\). Then for every \(d>j\), \[d\,H_d=(d-3)\,H_{d-1}+H_{d-2},\qquad h_d=H_d,\qquad H_d\le H_{d-1}\le3H_d .\] If moreover \(h_j=H_j\), then \(d\,b_d=(d-2)\,b_{d-1}+b_{d-2}+1\) for every \(d>j\).
Proof. We prove the three statements by induction on \(d>j\), together with the hypothesis \(H_{d-1}\le H_{d-2}\le3H_{d-1}\), which holds for \(d=j+1\) by assumption. Since \(d-1\ge j>k\), Lemma 9.6(ii) at \(d-1\) gives \(1-b_{d-1}=(d-2)H_{d-1}+H_{d-2}\), and therefore \[\theta_d=\frac{1-b_{d-1}-H_{d-1}}{d}=\frac{(d-3)\,H_{d-1}+H_{d-2}}{d}.\] The inequality \(\theta_d\le H_{d-1}\) is equivalent to \(H_{d-2}\le3H_{d-1}\), which holds. By Lemma 9.6(iv), \(h_d=H_d=\theta_d\); this is the claimed recurrence for \(H_d\), and \(H_d\le H_{d-1}\) because \(H\) is nonincreasing. Finally, \(H_{d-1}\le3H_d=3\theta_d\) is equivalent to \(d\,H_{d-1}\le3(d-3)H_{d-1}+3H_{d-2}\), that is, to \((9-2d)\,H_{d-1}\le3H_{d-2}\). This holds because \(d\ge j+1\ge k+2\ge5\) makes the left side nonpositive, while \(H_{d-2}\ge0\) by Lemma 9.6. So the hypothesis holds for \(d+1\).
For the last statement, let \(d>j\). Then \(h_d=H_d\) by the first part, and \(h_{d-1}=H_{d-1}\), by assumption if \(d-1=j\) and by the first part if \(d-1>j\). Substituting into Lemma 9.6(ii) gives \(1-b_d=(d-1)(b_d-b_{d-1})+(b_{d-1}-b_{d-2})\), which rearranges to \(d\,b_d=(d-2)\,b_{d-1}+b_{d-2}+1\). ∎
9.3 The deletion process and the proof of the bootstrap lemma
Throughout this subsection, \(b\) is as in Lemma 9.6, and \(\rho\colon\mathbb{N}\to[0,\infty)\) is a nondecreasing function such that every graph \(J\) with \(\delta(J)\ge3\) and \(\Delta(J)\le k\) satisfies \[\begin{equation*} \tag{9.3} \mathop{\mathrm{pw}}(J)\le\sum_{d=3}^{k}b_d\,n_d(J)+\rho\bigl(|V(J)|\bigr). \end{equation*}\] By Lemma 9.6, \(b\) is nondecreasing, \(0\le b_d\le1\), and (9.2) holds for all \(d>k\). We show that every graph \(G\) with \(n\ge1\) vertices satisfies \[\begin{equation*} \tag{9.4} \mathop{\mathrm{pw}}(G)\le\sum_{d\ge3}b_d\,n_d+b_3+\rho(n)+6\log_2n+2, \end{equation*}\] and deduce Lemma 9.3.
The proof of (9.4) combines three bounds. The deletion process (Proposition 9.10) deletes vertices of large degree and applies reductions until every component is basic (Definition 9.8); the number of deleted vertices is at most the decrease of a modified potential \(\psi^-\). Lemma 9.11 bounds the pathwidth of basic graphs, and Lemma 4.5 bounds the effect of the reductions. The three bounds are added up after Lemma 9.11.
Facts about reductions.
We use the properties (RP1)–(RP3) of the reduction operations, stated after Definition 4.2. Since \(b\) is nondecreasing and nonnegative, (RP1) implies that an operation does not increase \(\psi\). The effect of the reductions on the pathwidth is bounded by Lemma 4.5, applied to sequences of reduction operations and vertex deletions; recall that the empty graph has pathwidth \(-1\) (Section 4.1).
The potential.
For a graph \(G\) with \(\delta(G)\ge3\) and components \(G_1,\dots,G_t\) put \[\psi^-(G):=\psi(G)-\sum_{i=1}^{t}H_{\delta(G_i)},\] and \(\psi^-(G):=0\) for the empty graph. Each component \(G_i\) contains a vertex of degree \(\delta(G_i)\ge3\), whose weight is \(b_{\delta(G_i)}\ge h_{\delta(G_i)}\ge H_{\delta(G_i)}\), because \(b_{\delta(G_i)-1}\ge0\). Hence \(\psi^-(G)\ge0\), and also \(\psi^-(G_i)\ge0\) for each component, and \(\psi^-\) is additive over components. The negative term is the one of Edwards and McDermid (Edwards and McDermid 2015). It is needed when the deleted vertex lies in a regular component, where no neighbor has smaller degree (Case 1 in the proof of Lemma 9.9).
Basic graphs.
The process stops at components of the following kind.
Definition 9.8 (basic graphs). A connected graph \(J\) with \(\delta(J)\ge3\) is basic if \(\Delta(J)\le k\), or if there is a vertex \(v\in V(J)\) such that some maximal sequence of reduction operations applied to \(J-v\) ends with the empty graph.
The deletion process of Proposition 9.10 below repeats one step: delete a vertex of maximum degree, then reduce. The next lemma shows that this step lowers \(\psi^-\) by at least one. The algorithm of Appendix A.5.9 uses it directly, without testing whether a component is basic.
Lemma 9.9 (one deletion). Let \(G\) be a connected graph with \(\delta(G)\ge3\) and \(\Delta(G)\ge k+1\). Let \(w\) be a vertex of degree \(\Delta(G)\) that has a neighbor of smaller degree, if such a vertex exists, and any vertex of degree \(\Delta(G)\) otherwise. Let \(G^*\) be the final graph of a maximal sequence of reduction operations applied to \(G-w\). If \(G^*\) is nonempty, then \(1+\psi^-(G^*)\le\psi^-(G)\).
Proof. Write \(\Delta:=\Delta(G)\), so \(\Delta\ge k+1\ge4\). Let \(v_1,\dots,v_\Delta\) be the neighbors of \(w\), ordered so that \(d(v_1)\le d(v_2)\le\dots\le d(v_\Delta)\); here and below, \(d(\cdot)\) denotes the degree in \(G\). Let \(G':=G-w\). As \(G^*\) is nonempty, \(\delta(G^*)\ge3\) by (RP3). As \(G\) is connected, the claim reads \[\begin{equation*} \tag{9.5} 1+\psi^-(G^*)\le\psi^-(G)=\psi(G)-H_{\delta(G)}. \end{equation*}\] We bound \(1+\psi^-(G^*)\) from above by \(\psi(G)\) minus four terms \(J_1,\dots,J_4\), and show by cases that \(J_1+\dots+J_4\ge H_{\delta(G)}\).
Rewriting the left side. Every neighbor \(v_i\) of \(w\) loses one degree, from \(d(v_i)\ge3\) to \(d(v_i)-1\), and its weight drops by \(h_{d(v_i)}\). So \[\psi(G')=\psi(G)-b_\Delta-\sum_{i=1}^{\Delta}h_{d(v_i)}.\] Since \(H\ge0\) and some component of \(G^*\) has minimum degree \(\delta(G^*)\), we have \(\psi^-(G^*)\le\psi(G^*)-H_{\delta(G^*)}\). Put \[J_4:=\psi(G')-\psi(G^*)+H_{\delta(G^*)},\] so that \(\psi^-(G^*)\le\psi(G')-J_4\). Since \(\Delta>k\), identity (9.2) gives \(1-b_\Delta=(\Delta-1)H_\Delta+H_{\Delta-1}\). Combining, \[1+\psi^-(G^*)\le\psi(G)+(\Delta-1)H_\Delta+H_{\Delta-1} -\sum_{i=1}^{\Delta}h_{d(v_i)}-J_4 =\psi(G)-(J_1+J_2+J_3+J_4),\] where \[J_1:=h_{d(v_1)}-H_{\Delta-1},\qquad J_2:=h_{d(v_2)}-H_\Delta,\qquad J_3:=\sum_{i=3}^{\Delta}\bigl(h_{d(v_i)}-H_\Delta\bigr).\] Hence (9.5) follows once we show \[\begin{equation*} \tag{9.6} J_1+J_2+J_3+J_4\ge H_{\delta(G)} . \end{equation*}\]
Signs. For \(3\le j\le\Delta\) we have \(h_j\ge H_j\ge H_\Delta\), because \(H\) is nonincreasing. As \(3\le d(v_i)\le\Delta\), this gives \(J_2\ge0\) and \(J_3\ge0\). Similarly \(J_1\ge0\) whenever \(d(v_1)\le\Delta-1\), since then \(h_{d(v_1)}\ge H_{d(v_1)}\ge H_{\Delta-1}\). Finally \(J_4\ge0\): by (RP1), \(\psi(G^*)\le\psi(G')\), and \(H_{\delta(G^*)}\ge0\).
Claim. If some \(u\in V(G')\) has \(d_{G'}(u)=j\ge3\), then \(J_4\ge H_j\).
Indeed, suppose first that \(u\) is a vertex of \(G^*\). By (RP1), \(d_{G^*}(u)\le j\), so \(3\le\delta(G^*)\le j\) and \(H_{\delta(G^*)}\ge H_j\); together with \(\psi(G')-\psi(G^*)\ge0\) this gives \(J_4\ge H_j\). Otherwise \(u\) was removed by a reduction. Every vertex of \(G^*\) has weight in \(G^*\) at most its weight in \(G'\) by (RP1), and every removed vertex has nonnegative weight, so \(\psi(G')-\psi(G^*)\ge b_j\ge h_j\ge H_j\); as \(H_{\delta(G^*)}\ge0\), again \(J_4\ge H_j\).
Case 1: \(G\) is \(\Delta\)-regular. Then \(\delta(G)=\Delta\) and \(J_1=h_\Delta-H_{\Delta-1}\). In \(G'\) the vertex \(v_1\) has degree \(\Delta-1\ge3\), so \(J_4\ge H_{\Delta-1}\) by the claim. Hence \(J_1+J_4\ge h_\Delta\ge H_\Delta=H_{\delta(G)}\), and (9.6) follows from \(J_2,J_3\ge0\).
Case 2: \(G\) is not regular. Since \(G\) is connected, some edge joins a vertex of degree \(\Delta\) to a vertex of smaller degree (on a path from a vertex of degree \(\Delta\) to a vertex of smaller degree, take the first such edge). So \(w\) was chosen with a neighbor of smaller degree, \(d(v_1)\le\Delta-1\), and \(J_1\ge0\). All four terms are now nonnegative.
Case 2a: some \(u\in V(G')\) has \(3\le d_{G'}(u)\le\delta(G)\). By the claim, \(J_1+J_2+J_3+J_4\ge J_4\ge H_{d_{G'}(u)}\ge H_{\delta(G)}\).
Case 2b: no such vertex exists. Since \(\delta(G)<\Delta=d(w)\), there is a vertex \(u\ne w\) of degree \(\delta(G)\), and \(d_{G'}(u)\in\{\delta(G)-1,\delta(G)\}\). If \(\delta(G)\ge4\), then \(3\le d_{G'}(u)\le\delta(G)\), which is Case 2a. Hence \(\delta(G)=3\). Every vertex \(u\) of degree \(3\) is adjacent to \(w\), since otherwise \(d_{G'}(u)=3\), which is Case 2a. In particular \(d(v_1)=3\), and \(H_{\delta(G)}=H_3=h_3\).
Case 2b-i: \(d(v_\Delta)\ge4\). Then \(3\le d_{G'}(v_\Delta)=d(v_\Delta)-1\le\Delta-1\), so by the claim \(J_4\ge H_{d_{G'}(v_\Delta)}\ge H_{\Delta-1}\). With \(J_1=h_3-H_{\Delta-1}\) this gives \(J_1+J_4\ge h_3=H_{\delta(G)}\).
Case 2b-ii: \(d(v_\Delta)=3\). Then all neighbors of \(w\) have degree \(2\) in \(G'\). Let \(u\) be any vertex of the nonempty graph \(G^*\). By (RP1), \(d_{G'}(u)\ge d_{G^*}(u)\ge3\), so \(u\) is not a neighbor of \(w\); hence \(d_{G'}(u)=d(u)\in[3,\Delta]\), and the claim gives \(J_4\ge H_{d(u)}\ge H_\Delta\). With \(J_2=h_3-H_\Delta\) (note \(d(v_2)=3\)) this gives \(J_2+J_4\ge h_3=H_{\delta(G)}\).
The following proposition is the heart of the proof. It deletes vertices until every component is basic, and bounds the number of deleted vertices from above by the decrease of \(\psi^-\).
Proposition 9.10 (deletion process). Every graph \(G\) with \(\delta(G)\ge3\) admits a finite sequence of vertex deletions and reduction operations that transforms \(G\) into a graph \(R\) all of whose components are basic, such that the set \(X\) of deleted vertices satisfies \[|X|+\psi^-(R)\le\psi^-(G).\]
Proof. We argue by induction on \(|V(G)|\). A disconnected graph is handled component by component. For a connected graph that is not basic, we delete one vertex \(w\) of maximum degree, reduce, and apply the induction hypothesis to the result; by Lemma 9.9, this deletion, with the reductions after it, lowers \(\psi^-\) by at least one.
If every component of \(G\) is basic, take the empty sequence.
\(G\) disconnected. Each component \(G_i\) has minimum degree at least \(3\) and fewer vertices than \(G\), so by induction it admits a sequence with deleted set \(X_i\) and final graph \(R_i\) satisfying \(|X_i|+\psi^-(R_i)\le\psi^-(G_i)\). By (RP2), performing these sequences one after the other is a sequence of deletions and reductions on \(G\). Its final graph is the disjoint union \(R\) of the \(R_i\), whose components are all basic, and its deleted set is the disjoint union \(X\) of the \(X_i\). Summing, and using additivity of \(\psi^-\), gives \(|X|+\psi^-(R)\le\psi^-(G)\).
\(G\) connected and not basic. Then \(\Delta:=\Delta(G)\ge k+1\ge4\), since otherwise \(G\) would be basic. Choose a vertex \(w\) of degree \(\Delta\) that has a neighbor of smaller degree, if such a vertex exists, and any vertex of degree \(\Delta\) otherwise, and let \(G^*\) be the final graph of a maximal sequence of reduction operations applied to \(G-w\). Since \(G\) is not basic (take \(v=w\) in Definition 9.8), \(G^*\) is not empty, so \(\delta(G^*)\ge3\) by (RP3). As \(|V(G^*)|<|V(G)|\), the induction hypothesis gives a sequence from \(G^*\) to a graph \(R\) with basic components and deleted set \(X^*\), such that \(|X^*|+\psi^-(R)\le\psi^-(G^*)\). The concatenated sequence (delete \(w\), reduce maximally, then follow the sequence for \(G^*\)) transforms \(G\) into \(R\) and has deleted set \(X=X^*\cup\{w\}\). By Lemma 9.9, \(|X|+\psi^-(R)\le1+\psi^-(G^*)\le\psi^-(G)\). ∎
The pathwidth of a basic graph is bounded either by the hypothesis (9.3) or by Lemma 4.5.
Lemma 9.11 (basic graphs). Let \(J\) be a basic graph with \(N\) vertices. Then \(\psi(J)\le\psi^-(J)+b_3\). If \(\Delta(J)\le k\), then \(\mathop{\mathrm{pw}}(J)\le\psi^-(J)+b_3+\rho(N)\). Otherwise \(\mathop{\mathrm{pw}}(J)\le3\log_2N+1\).
Proof. As \(J\) is connected, \(\psi(J)=\psi^-(J)+H_{\delta(J)}\le\psi^-(J)+b_3\), because \(H_d\le h_3=b_3\) for all \(d\ge3\). If \(\Delta(J)\le k\), then \(\delta(J)\ge3\) and (9.3) give \(\mathop{\mathrm{pw}}(J)\le\psi(J)+\rho(N)\), which with the first claim gives the bound.
Otherwise there is a vertex \(v\) such that a maximal sequence of reductions applied to \(J-v\) ends with the empty graph. Apply Lemma 4.5 to \(F=J\) and the sequence that deletes \(v\) and then performs these reductions: here \(D=\{v\}\) and the final graph is empty, so \(\mathop{\mathrm{pw}}(J)\le1+(-1)+3\log_2N+1\). ∎
Proof of (9.4). Let \(G\) be a graph with \(n\ge1\) vertices. Apply a maximal sequence of reduction operations to \(G\), and let \(R_0\) be its final graph. If \(R_0\) is not empty, then \(\delta(R_0)\ge3\) by (RP3); continue with the sequence of Proposition 9.10 for \(R_0\). Together this is one sequence of deletions and reductions from \(G\) to a graph \(R\), with deleted set \(X\); if \(R_0\) is empty, then \(R=R_0\) and \(X=\emptyset\). We bound the three ingredients.
The potential. By (RP1), \(\psi(R_0)\le\psi(G)\), and \(\psi^-(R_0)\le\psi(R_0)\) because \(H\ge0\). With Proposition 9.10, \(|X|+\psi^-(R)\le\psi^-(R_0)\le\psi(G)\). (If \(R_0\) is empty, both sides of the first inequality are \(0\).)
The final graph. If \(R\) is empty, then \(\mathop{\mathrm{pw}}(R)=-1\). Otherwise every component \(C\) of \(R\) is basic and has at most \(n\) vertices. By Lemma 9.11, monotonicity of \(\rho\) and \(\log_2\), and nonnegativity of \(\psi^-(C)\), \(b_3\) and \(\rho\), \[\mathop{\mathrm{pw}}(C)\le\psi^-(C)+b_3+\rho(n)+3\log_2n+1 .\] The pathwidth of a graph is the maximum over its components (Section 4.1), and \(\psi^-(C)\le\psi^-(R)\) by additivity and nonnegativity. Hence \(\mathop{\mathrm{pw}}(R)\le\psi^-(R)+b_3+\rho(n)+3\log_2n+1\) in all cases.
The reductions. By Lemma 4.5 applied to the whole sequence, with \(D=X\), \(\mathop{\mathrm{pw}}(G)\le|X|+\mathop{\mathrm{pw}}(R)+3\log_2n+1\).
Adding up, \(\mathop{\mathrm{pw}}(G)\le|X|+\psi^-(R)+b_3+\rho(n)+6\log_2n+2\le\psi(G)+b_3+\rho(n)+6\log_2n+2\), and \(\psi(G)=\sum_{d\ge3}b_dn_d\) because \(b_0=b_1=b_2=0\). ∎
Proof of Lemma 9.3. Let \(k\) and \(b_3,\dots,b_k\) be as in Lemma 9.3, and let \(b\) be their bootstrap; it is as in Lemma 9.6. Let \(\rho_0\) be the function \(\rho\) of Lemma 9.3, and let \(\rho:=\bar\rho_0\) be its running maximum (4.2), which is nonnegative, nondecreasing, at least \(\rho_0\), and again \(o(N)\). Then (9.3) holds, so (9.4) holds for every graph with \(n\ge1\) vertices, and its remainder \(b_3+\rho(n)+6\log_2n+2\) is \(o(n)\); the empty graph has pathwidth \(-1\). So \(b\) is a pathwidth sequence. By Lemma 9.6(i), \(b\) is nondecreasing and \(b_d\le1\) for \(d>k\); for \(d\le k\), \(b_d\le b_k\le1-H_k\le1\), because \(H_k\ge0\) by Lemma 9.6. ∎
9.4 Proof of Theorem 1.3
We apply the explicit bound (9.4) with \(k=5\) to the triple \(\mathsf{S}\) of Theorem 7.2. Throughout, \(\sigma=(\sigma_d)_{d\ge0}\) denotes the bootstrap of \(\mathsf{S}\): it has \(\sigma_0=\sigma_1=\sigma_2=0\), \((\sigma_3,\sigma_4,\sigma_5)=\mathsf{S}\), and it is extended by (9.1) with \(k=5\). We write \(h_d\) and \(H_d\) for its increments and their running minima. The seeds are nondecreasing, with increments \(h_3=\frac5{32}\) and \(h_4=h_5=\frac3{32}\); so \(H_5=\frac3{32}\) and \(\sigma_5+H_5=\frac{14}{32}\le1\), and \(\sigma\) is as in Lemma 9.6.
We compute \(\sigma\) exactly up to degree \(8\), and bound it from above by \(1-\frac{111}{28(d+1)}\) from degree \(7\) on and by \(1-\frac{4}{d+1}\) from degree \(11\) on (Proposition 9.13). These two bounds use the following lemma on the recurrence \(d\,u_d=(d-2)\,u_{d-1}+u_{d-2}\). In the concave regime of Lemma 9.7, the deficits \(u_d=1-b_d\) satisfy this recurrence. We use the lemma again in the proofs of Lemma 9.16 and of Corollary 9.5. Its first part says that the recurrence has a conserved quantity \(\lambda\), which reduces it to the first-order rule \(d\,u_d=\lambda-u_{d-1}\); the second part turns this rule into a two-sided bound on the weighted deficits \(w_d=(d+1)\,u_d\).
Lemma 9.12 (weighted deficits). Let \(d_0\ge3\), and let \((u_d)_{d\ge d_0-2}\) be reals with \(d\,u_d=(d-2)\,u_{d-1}+u_{d-2}\) for all \(d\ge d_0\). Put \(w_d:=(d+1)\,u_d\) and \(\lambda:=(d_0-1)\,u_{d_0-1}+u_{d_0-2}\). Then:
(i) \(d\,u_d+u_{d-1}=\lambda\) for all \(d\ge d_0-1\);
(ii) if \(\lambda>0\) and \(\frac{d_1+1}{d_1+2}\,\lambda<w_{d_1}<\lambda\) for some \(d_1\ge d_0-1\), then \[\Bigl(1-\frac1{d^2}\Bigr)\lambda<w_d<\lambda\qquad\text{for every }d>d_1 .\]
Proof. (i) For \(d\ge d_0\), \((d\,u_d+u_{d-1})-\bigl((d-1)\,u_{d-1}+u_{d-2}\bigr)=d\,u_d-(d-2)\,u_{d-1}-u_{d-2}=0\).
(ii) For \(d\ge d_0\), the rule \(d\,u_d=\lambda-u_{d-1}\) of (i) and \(u_{d-1}=w_{d-1}/d\) give \[w_d=\frac{d+1}{d}\Bigl(\lambda-\frac{w_{d-1}}{d}\Bigr),\qquad\text{so}\qquad w_d-\lambda=\frac{d\,\lambda-(d+1)\,w_{d-1}}{d^2} .\] We argue by induction on \(d>d_1\) under the hypothesis \(\frac{d}{d+1}\lambda<w_{d-1}<\lambda\), which is the assumption for \(d=d_1+1\); note that \(d\ge d_0\) throughout. The lower bound on \(w_{d-1}\) makes the numerator negative, so \(w_d<\lambda\). The upper bound gives \(w_d-\lambda>\frac{d\lambda-(d+1)\lambda}{d^2}=-\frac{\lambda}{d^2}\). Finally \(1-\frac1{d^2}\ge\frac{d+1}{d+2}\) because \(d^2\ge d+2\) for \(d\ge2\); hence \(\frac{d+1}{d+2}\lambda<w_d<\lambda\), which is the hypothesis for \(d+1\). ∎
The next statement computes \(\sigma\), records where the threshold \(d\ge11\) of Theorem 1.3 comes from and that it is sharp, and shows \(\sigma_d\le a_d\) for every \(d\ge3\).
Proposition 9.13 (the bootstrap of \(\mathsf{S}\)). The bootstrap \(\sigma\) of \(\mathsf{S}\) satisfies \(\sigma_d=\frac{3d-4}{32}\) for \(3\le d\le6\), \[1-\frac{129}{32\,(d+1)}<\sigma_d<1-\frac{129}{32\,(d+1)}+\frac{129}{32\,d^2(d+1)} \qquad(d\ge5),\] and, for \(d\ge3\), \(\sigma_d\le1-\frac{4}{d+1}\) if and only if \(d\ge11\). Moreover, \(\sigma_d\le a_d\) for every \(d\ge3\), where \(a_d\) are the coefficients of Theorem 1.3.
Proof. Steps 1 and 2 compute \(\sigma\) up to degree \(6\) and show that from degree \(7\) on it satisfies the recurrence of Edwards and McDermid. Steps 3 and 4 apply Lemma 9.12 to the deficits \(u_d=1-\sigma_d\) and give the two closed-form bounds. The last paragraph collects the remaining claims.
Step 1: degrees up to \(6\). At \(d=6\), \(\theta_6=(1-\sigma_5-H_5)/6=\frac{18/32}{6}=\frac3{32}=H_5\). By Lemma 9.6(iv), \(\sigma_6\) is the first term of the maximum and \(h_6=H_6=\frac3{32}\); so \(\sigma_6=\frac{11}{32}+\frac3{32}=\frac7{16}\). (The second term \(1-6H_5=\frac7{16}\) is equal.) Hence \[\sigma_d=\frac{3d-4}{32}\qquad(3\le d\le6).\]
Step 2: the recurrence from degree \(7\). We have \(j=6>k=5\) and \(H_6=H_5=\frac3{32}\), so \(H_6\le H_5\le3H_6\); also \(h_6=H_6\). By Lemma 9.7, \[d\,\sigma_d=(d-2)\,\sigma_{d-1}+\sigma_{d-2}+1\qquad(d\ge7).\] For example, \(\sigma_7=\frac{5\cdot\frac{14}{32}+\frac{11}{32}+1}{7}=\frac{113}{224}\) and \(\sigma_8=\frac{6\cdot\frac{113}{224}+\frac{98}{224}+1}{8}=\frac{125}{224}\).
Step 3: the bound \(1-\frac{111}{28(d+1)}\). Put \(u_d:=1-\sigma_d\) and \(w_d:=(d+1)\,u_d\). Since \(d=(d-2)+1+1\), the recurrence of Step 2 is equivalent to \(d\,u_d=(d-2)\,u_{d-1}+u_{d-2}\) for \(d\ge7\); it also holds at \(d=6\), because \(6\sigma_6=\frac{21}8=4\sigma_5+\sigma_4+1\). So Lemma 9.12(i) applies with \(d_0=6\) and \(\lambda=5u_5+u_4=\frac{105}{32}+\frac{24}{32}\): \[d\,u_d+u_{d-1}=\tfrac{129}{32}\qquad(d\ge5).\] Moreover \(w_5=w_6=\frac{63}{16}=\frac{126}{32}\) and \(\frac78\cdot\frac{129}{32}=\frac{903}{256}<\frac{126}{32}<\frac{129}{32}\), so Lemma 9.12(ii) applies with \(d_1=6\): \[\begin{equation*} \tag{9.7} \Bigl(1-\frac1{d^2}\Bigr)\frac{129}{32}<w_d<\frac{129}{32}\qquad(d\ge7). \end{equation*}\] Now \(w_7=8\cdot\frac{111}{224}=\frac{111}{28}\), and for \(d\ge8\), \(w_d>\frac{63}{64}\cdot\frac{129}{32}=\frac{8127}{2048}>\frac{111}{28}\). Hence \(w_d\ge\frac{111}{28}\) for every \(d\ge7\), that is, \[\sigma_d\le1-\frac{111}{28\,(d+1)}\qquad(d\ge7),\] with equality at \(d=7\).
Step 4: the bound \(1-\frac{4}{d+1}\). The inequality \(\sigma_d\le1-\frac4{d+1}\) is \(w_d\ge4\). For \(d\ge12\), (9.7) gives \(w_d>\bigl(1-\frac1{144}\bigr)\frac{129}{32}=\frac{18447}{4608}>4\), as \(18447>4\cdot4608=18432\). For \(d=11\), the rule \(u_d=(\frac{129}{32}-u_{d-1})/d\) gives \(u_7=\frac{111}{224}\), \(u_8=\frac{99}{224}\), \(u_9=\frac{67}{168}\), \(u_{10}=\frac{2441}{6720}\) and \(u_{11}=\frac{24649}{73920}\), so \(w_{11}=\frac{24649}{6160}>4\) because \(4\cdot6160=24640\). Hence \[\sigma_d\le1-\frac{4}{d+1}\qquad(d\ge11).\]
The remaining claims. The two-sided bound is (9.7) for \(d\ge7\), and for \(d\in\{5,6\}\) it reads \(\bigl(1-\frac1{d^2}\bigr)\frac{129}{32}\le\frac{35}{36}\cdot\frac{129}{32} =\frac{4515}{1152}<\frac{126}{32}=w_d<\frac{129}{32}\). Step 4 gives \(\sigma_d\le1-\frac4{d+1}\) for \(d\ge11\). Conversely, \(w_3=4\cdot\frac{27}{32}=\frac{27}8\), \(w_4=5\cdot\frac34=\frac{15}4\), and the values of Step 4 give \[(w_5,\dots,w_{10})=\Bigl(\tfrac{63}{16},\tfrac{63}{16},\tfrac{111}{28}, \tfrac{891}{224},\tfrac{335}{84},\tfrac{26851}{6720}\Bigr),\] all below \(4\) (for the last, \(4\cdot6720=26880>26851\)), so \(\sigma_d>1-\frac4{d+1}\) for \(3\le d\le10\). Finally, Steps 1, 3 and 4 give \(\sigma_d\le a_d\) for every \(d\ge3\). ∎
The statement of Theorem 1.3 rounds the coefficients \(\sigma_d\) for \(d\ge7\) up to closed forms. The proof above gives \(\sigma_7=\frac{113}{224}\), \(\sigma_8=\frac{125}{224}\), \(\sigma_9=\frac{101}{168}\) and \(\sigma_{10}=\frac{4279}{6720}\), which Table 7 compares with \(a_d\).
Proof of Theorem 1.3. By Theorem 7.2 with the triple \(\mathsf{S}\), there is a function \(\rho_0\) with \(\rho_0(N)=o(N)\) such that every graph \(J\) with \(\Delta(J)\le5\), in particular every \(J\) with \(\delta(J)\ge3\) and \(\Delta(J)\le5\), satisfies \(\mathop{\mathrm{pw}}(J)\le\sigma_3n_3(J)+\sigma_4n_4(J)+\sigma_5n_5(J)+\rho_0(|V(J)|)\). Its running maximum \(\rho:=\bar\rho_0\) of (4.2) is nonnegative, nondecreasing, at least \(\rho_0\) and again \(o(N)\), so (9.3) holds with \(\rho\). As \(\sigma\) is as in Lemma 9.6, (9.4) gives, for every graph \(G\) with \(n\ge1\) vertices, \[\begin{equation*} \tag{9.8} \mathop{\mathrm{pw}}(G)\le\sum_{d\ge3}\sigma_d\,n_d+\rho_4(n),\qquad \rho_4(n):=\tfrac5{32}+\rho(n)+6\log_2n+2 . \end{equation*}\] The function \(\rho_4\) is nondecreasing and \(\rho_4(n)=o(n)\). By Proposition 9.13, \(\sigma_d\le a_d\) for every \(d\ge3\), so \(\mathop{\mathrm{pw}}(G)\le\sum_{d\ge3}a_dn_d+\rho_4(n)\) for every graph \(G\). ∎
9.5 Edges and average degree
This subsection derives the bound in terms of edges (Corollary 1.4) and a bound in terms of the average degree (Corollary 9.15) from Theorem 1.3, and compares the latter with the bound of Edwards and McDermid. Throughout, \(a_d\) (\(d\ge3\)) are the coefficients of Theorem 1.3, and \(a_0=a_1=a_2:=0\). The edge bound follows from Theorem 1.3 because no coefficient \(a_d\) exceeds \(\frac7{48}\cdot\frac d2\); the maximum ratio \(2a_d/d\) is attained at \(d=6\).
Proof of Corollary 1.4. We first show that \[\begin{equation*} \tag{9.9} a_d\le\frac7{48}\cdot\frac d2\qquad\text{for every }d\ge3, \end{equation*}\] with equality only at \(d=6\), and that \(2a_d/d\le\frac{113}{784}\) for \(d\ne6\). For \(3\le d\le6\), \(a_d=\frac{3d-4}{32}\le\frac{7d}{96}\) is equivalent to \(9d-12\le7d\), that is, to \(d\le6\), and \(2a_d/d=\frac3{16}-\frac1{4d}\le\frac{11}{80}<\frac{113}{784}\) for \(d\le5\). For \(d\ge7\) we have \(a_d\le1-\frac{111}{28(d+1)}\): with equality for \(7\le d\le10\); for \(d\ge11\) because \(4>\frac{111}{28}\). Moreover \[\frac{113}{784}\cdot\frac d2-\Bigl(1-\frac{111}{28\,(d+1)}\Bigr) =\frac{(d-7)(113d-664)}{1568\,(d+1)}\ge0\qquad(d\ge7),\] with equality at \(d=7\), and \(\frac{113}{784}<\frac7{48}\). This proves both claims.
Now let \(G\) be a graph with \(m\) edges. Summing (9.9) over the vertices of \(G\) of degree at least \(3\), and using that vertices of degree at most \(2\) contribute nonnegative amounts to the right side, \[\sum_{d\ge3}a_d\,n_d\le\frac7{96}\sum_{v\in V(G)}d_G(v)=\frac7{48}\,m .\] So Theorem 1.3 gives \(\mathop{\mathrm{pw}}(G)\le\frac7{48}m+o(n)\). ∎
Remark 9.14 (remainder in \(m\)). The remainder of Corollary 1.4 can also be taken as a function of \(m\): \(\mathop{\mathrm{pw}}(G)\le\frac7{48}m+\rho(m+1)\) for every graph \(G\) with \(m\) edges, where \(\rho\) is the remainder of Theorem 1.3, taken nondecreasing by (4.2). Indeed, the computation above applied to a component \(H\) of \(G\) gives \(\mathop{\mathrm{pw}}(H)\le\frac7{48}|E(H)|+\rho(|V(H)|)\le\frac7{48}m+\rho(m+1)\), since \(|V(H)|\le|E(H)|+1\le m+1\), and \(\mathop{\mathrm{pw}}(G)\) is the maximum of \(\mathop{\mathrm{pw}}(H)\) over the components. Taking the maximum over components is essential: a sum of remainders over many small components would not be \(o(m)\). The same step shows that every bound of the form \(\sum_d b_dn_d+o(n)\) with \(b_d\le\beta d/2\) for all \(d\) yields \(\mathop{\mathrm{pw}}(G)\le\beta m+o(m)\). The algorithms of Theorem 10.1 compute path decompositions of width at most \(\frac7{48}m+\rho(2m)\), a remainder in \(m\) as well.
The same coefficients give a bound in terms of the average degree \(\bar d=2m/n\). Let \(A\colon[0,\infty)\to\mathbb{R}\) be given by \(A(x):=\frac7{96}x\) for \(0\le x\le6\) and, on \([d,d+1]\) for each integer \(d\ge6\), by linear interpolation between \(A(d)=a_d\) and \(A(d+1)=a_{d+1}\); the two definitions agree at \(6\), since \(a_6=\frac7{16}\).
Corollary 9.15 (average degree). Every graph \(G\) with \(n\ge1\) vertices and average degree \(\bar d\) satisfies \(\sum_{d\ge3}a_dn_d\le A(\bar d)\,n\), and hence \(\mathop{\mathrm{pw}}(G)\le A(\bar d)\,n+o(n)\), where \(A(\bar d)\le1-\frac{111}{28(\bar d+1)}\) if \(\bar d\ge7\) and \(A(\bar d)\le1-\frac{4}{\bar d+1}\) if \(\bar d\ge11\). If \(\delta(G)\ge2\), then \(\mathop{\mathrm{pw}}(G)\le\frac{3m-2n}{16}+o(n)\).
Proof. We first show that \(A\) is concave and lies above every coefficient \(a_d\), and apply Jensen’s inequality. The closed-form bounds on \(A(\bar d)\) then follow by comparing \(A\) with concave functions, and the bound for \(\delta(G)\ge2\) follows from \(a_d\le\frac{3d-4}{32}\).
The function \(A\) is continuous and piecewise linear. Its slopes are \(\frac7{96}\) on \([0,6]\), \(a_7-a_6=\frac{15}{224}\) on \([6,7]\), \(a_{d+1}-a_d=\frac{111}{28(d+1)(d+2)}\) on \([d,d+1]\) for \(7\le d\le9\), \(a_{11}-a_{10}=\frac{25}{924}\) on \([10,11]\), and \(a_{d+1}-a_d=\frac{4}{(d+1)(d+2)}\) on \([d,d+1]\) for \(d\ge11\). These slopes are nonincreasing, because \(\frac7{96}>\frac{15}{224}>\frac{111}{28\cdot72}\), the third expression decreases in \(d\) to \(\frac{111}{3080}>\frac{25}{924}\) at \(d=9\), \(\frac{25}{924}>\frac4{156}\), and the last expression decreases in \(d\). Hence \(A\) is concave. Moreover \(A(d)\ge a_d\) for every integer \(d\ge0\): for \(d\le2\) because \(a_d=0\), for \(3\le d\le5\) by (9.9), and for \(d\ge6\) with equality. Since the weights \(n_d/n\) sum to \(1\), Jensen’s inequality gives \[\sum_{d\ge3}a_dn_d=\sum_{d\ge0}a_dn_d\le\sum_{d\ge0}A(d)\,n_d \le n\,A\Bigl(\sum_{d\ge0}d\,\frac{n_d}{n}\Bigr)=n\,A(\bar d),\] and Theorem 1.3 gives \(\mathop{\mathrm{pw}}(G)\le A(\bar d)\,n+o(n)\). For \(\bar d\ge7\), let \(q(x):=1-\frac{111}{28(x+1)}\); it is concave on \([0,\infty)\), and \(a_d\le q(d)\) for \(d\ge7\) (with equality for \(d\le10\)). On each interval \([d,d+1]\) with \(d\ge7\), \(A\) is the chord through \((d,a_d)\) and \((d+1,a_{d+1})\), which lies below the chord of the concave function \(q\) and hence below \(q\). So \(A(\bar d)\le q(\bar d)\). The same argument with the concave function \(1-\frac4{x+1}\), which equals \(a_d\) for every \(d\ge11\), gives \(A(\bar d)\le1-\frac4{\bar d+1}\) for \(\bar d\ge11\).
For the last bound, note that \(a_d\le\frac{3d-4}{32}\) for every \(d\ge3\): with equality for \(d\le6\), and for \(d\ge7\) because \(A\) is concave with slope \(\frac{15}{224}<\frac3{32}\) on \([6,7]\), so that \(a_d=A(d)\le a_6+\frac{15}{224}(d-6)\le\frac{3d-4}{32}\). So every graph satisfies \(\mathop{\mathrm{pw}}(G)\le\sum_{d\ge3}\frac{3d-4}{32}\,n_d+o(n)\). Now let \(\delta(G)\ge2\), and write \(n_{\ge3}\) for the number of vertices of degree at least \(3\). As \(3d-4=2+3(d-2)\), \(\sum_{d\ge2}n_d=n\) and \(\sum_{d\ge2}d\,n_d=2m\), \[\sum_{d\ge3}a_dn_d\le\sum_{d\ge3}\frac{3d-4}{32}\,n_d =\frac{2n_{\ge3}+3\sum_{d\ge2}(d-2)\,n_d}{32}=\frac{n_{\ge3}+3(m-n)}{16} \le\frac{3m-2n}{16},\] and Theorem 1.3 completes the proof. ∎
For \(\bar d\le6\) its main term is that of Corollary 1.4, since \(A(\bar d)\,n=\frac7{96}\bar d\,n=\frac7{48}m\). For graphs with \(\delta(G)\ge2\) and \(\bar d<6\), the bound \(\frac{3m-2n}{16}\) is smaller. The condition \(\delta(G)\ge2\) cannot be dropped from it, since adding isolated vertices makes \(3m-2n\) negative without changing the pathwidth.
Edwards and McDermid prove \(\mathop{\mathrm{pw}}(G)\le\bigl(g_{1/6}(\bar d)+o(1)\bigr)n\) for connected graphs and for graphs with \(\bar d\ge5\), with \(g_{1/6}\) interpolated linearly (Edwards and McDermid 2015 Theorem 5.3). For \(\bar d\ge6\), Corollary 9.15 is smaller, since both \(A\) and \(g_{1/6}\) interpolate linearly between consecutive integers there and \(a_d<g_{1/6}(d)\) for every \(d\ge3\) by the following lemma.
Lemma 9.16 (comparison with the previous coefficients). Let \(g_{1/6}(2)=0\), \(g_{1/6}(3)=\frac16\) and \(d\,g_{1/6}(d)=(d-2)\,g_{1/6}(d-1)+g_{1/6}(d-2)+1\) for \(d\ge4\), the per-degree coefficients of Edwards and McDermid (Edwards and McDermid 2015, sec. 3.1.1 and Corollary 5.2); for \(3\le d\le6\) they are \(\frac16,\frac13,\frac{13}{30},\frac{23}{45}\), those of Fomin, Gaspers, Saurabh and Stepanov (Fomin et al. 2009 Lemma 1). Then the coefficients \(a_d\) of Theorem 1.3 satisfy \(a_d<g_{1/6}(d)\) and \((d+1)\bigl(1-g_{1/6}(d)\bigr)<\frac72\) for every \(d\ge3\).
Proof. Let \(u_d:=1-g_{1/6}(d)\) and \(\omega_d:=(d+1)u_d\). For \(d\le6\) the inequality \(a_d<g_{1/6}(d)\) follows from the exact values: \(\frac5{32}<\frac16\), \(\frac14<\frac13\), \(\frac{11}{32}<\frac{13}{30}\) and \(\frac7{16}<\frac{23}{45}\). The numbers \(u_d\) satisfy \(d\,u_d=(d-2)\,u_{d-1}+u_{d-2}\) for \(d\ge5\), with \(u_3=\frac56\) and \(u_4=\frac23\). By Lemma 9.12(i) with \(d_0=5\), \(d\,u_d+u_{d-1}=4u_4+u_3=\frac72\) for all \(d\ge4\), and since \(\frac56\cdot\frac72=\frac{35}{12}<\omega_4=\frac{10}3<\frac72\), Lemma 9.12(ii) with \(d_1=4\) gives \[\Bigl(1-\frac1{d^2}\Bigr)\frac72<\omega_d<\frac72\qquad(d\ge5),\] which is the asymptotic form of Edwards and McDermid with an explicit error term. Hence \(\omega_d<\frac72<\frac{111}{28}\le(d+1)(1-a_d)\) for \(d\ge7\), where \((d+1)(1-a_d)\) is \(\frac{111}{28}\) for \(7\le d\le10\) and \(4\) for \(d\ge11\). So \(1-g_{1/6}(d)<1-a_d\), that is, \(a_d<g_{1/6}(d)\), for all \(d\ge7\). Finally, \(\omega_3=\omega_4=\frac{10}3<\frac72\), so \(\omega_d<\frac72\) for every \(d\ge3\). ∎