7 The plain sweep: maximum degree 4 and 5
This section bounds the pathwidth of graphs of maximum degree \(4\) and \(5\) by a weighted count of their vertices of degree \(3\), \(4\) and \(5\), up to a term \(o(n)\). The two theorems below are its results. In them, \(n_d\) is the number of vertices of degree \(d\), and \(F_3\) and \(F_4\) are the maxima of the ideal star functions \(f_{3,r_{33}}\) and \(f_{4,r_{44}}\) (Definition 6.7).
Theorem 7.1 (maximum degree \(4\)). Every graph \(G\) with \(\Delta(G)\le 4\) satisfies \(\mathop{\mathrm{pw}}(G)\le a_3\,n_3+a_4\,n_4+o(n)\) for each of the pairs
(a) \((a_3,a_4)=(F_4,\,F_4)\), and in particular \(\mathop{\mathrm{pw}}(G)\le F_4\,n+o(n)\);
(b) \((a_3,a_4)=(F_3,\,0.2575)\);
(c) \((a_3,a_4)=\bigl(\tfrac{5}{32},\,\tfrac14\bigr)\).
Lean proof, (a) under H1 and (b), (c) under H2: T2.target2a, T2.target2b, T2.target2c (what is formalised)
Theorem 7.2 (maximum degree \(5\)). Every graph \(G\) with \(\Delta(G)\le 5\) satisfies \(\mathop{\mathrm{pw}}(G)\le a_3\,n_3+a_4\,n_4+a_5\,n_5+o(n)\) for each of the triples
\(\mathsf{P}\) \((a_3,a_4,a_5)=(F_3,\,0.2575,\,0.3667)\);
\(\mathsf{R}\) \((a_3,a_4,a_5)=(0.1455,\,0.2530,\,0.3600)\);
\(\mathsf{S}\) \((a_3,a_4,a_5)=\bigl(\tfrac{5}{32},\,\tfrac14,\,\tfrac{11}{32}\bigr)\).
Lean proof under H3: T3.target3P, T3.target3R, T3.target3S (what is formalised)
Parts (b) and (c) of Theorem 7.1 are the cases \(\mathsf{P}\) and \(\mathsf{S}\) of Theorem 7.2 for graphs without vertices of degree \(5\); we state them separately because later sections use them in this form. With the bootstrap of Section 9, the two theorems give the sequences \(\mathsf{F}\), \(\mathsf{P}\), \(\mathsf{R}\) and \(\mathsf{S}\) of Theorem 9.2.
The method is the plain sweep: draw the Gaussian labels of Section 5, order the vertices by label, and take the layout of Lemma 4.1, whose width is the largest outer frontier \(|\partial^{+}S_\tau|\) over all thresholds \(\tau\). It therefore suffices to find one realization of the labels in which every outer frontier has at most \(\sum_da_dn_d+o(n)\) vertices. The proof has three parts.
(1) Expected frontier at a fixed threshold. A vertex lies in \(\partial^{+}S_\tau\) exactly when the frontier event of its star occurs. So \(\mathbb{E}|\partial^{+}S_\tau|\) is a sum of star probabilities, each bounded by the center bound of Lemma 6.2. The center bound depends on the degree of the vertex and on the degrees of its neighbors, which we record as its type. A vertex of degree \(3\) next to vertices of higher degree has weaker correlation bounds than one in a cubic region, and its center bound exceeds \(a_3\). The excess is moved along the edges to the neighbors of higher degree (Lemma 7.4). Checking that after these transfers the bound at every vertex is at most the coefficient of its degree, at every threshold, is a finite but large computation: the certificate of Proposition 7.5.
(2) Removing the correlation loss. The labels give the correlation lower bounds only up to a factor \(1-\varepsilon_R\), where \(R\) is the parameter of the labels. The explicit continuity of the center bound (Lemma 6.3) turns this factor into an additive error that vanishes as \(R\to\infty\), uniformly in the threshold.
The proof of Theorem 7.1(a) has the same three parts, with the padded labels of degree \(4\) instead of the mixed labels used for the other bounds (Definition 5.2). There all vertices are treated alike: the frontier probability of every vertex is at most the ideal star function \(f_{4,r}\) (Corollary 6.8), so no charging and no certificate are needed.
Setting.
In Sections 7.1, 7.2 and 7.3, \(H\) is a graph with \(\delta(H)\ge3\) and \(\Delta(H)\le5\), and \(Y=(Y_v)_{v\in V(H)}\) are the mixed labels of Definition 5.2(b) with parameter \(R\). We use two facts from Section 5.
(L1) For every edge \(uv\) of \(H\) with \(d(u)=i\) and \(d(v)=j\), \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_{ij}(1-\varepsilon_R)\), where \(r_{ij}=\mathop{\mathrm{sech}}(\frac14\ln((i-1)(j-1)))\) and \(\varepsilon_R=\frac{4\ln2}{R-2\ln2}\) for \(R>2\ln2\) (Lemma 5.5 with \(\Delta_0=5\)); in particular \(\varepsilon_R\to0\) as \(R\to\infty\).
(L2) The labels are pairwise distinct with probability \(1\), and each \(Y_v\) is a function of \((Z_w)_{w\in B_{\varrho_R}(v)}\), where \(\varrho_R:=\lfloor2R/\ln2\rfloor\) is the locality radius \(\rho\) of Lemma 5.6 for mixed labels.
Since \(\mathop{\mathrm{sech}}\) is decreasing on \([0,\infty)\), the largest of the numbers \(r_{ij}\) with \(3\le i,j\le5\) is \(r_{33}=\frac{2\sqrt2}3\).
7.1 Vertex types and the charging scheme
The center bound of a vertex depends only on its degree and on the degrees of its neighbors. We record this dependence as a type, define the redistribution of the excess, and isolate the inequalities that a coefficient vector must satisfy.
Definition 7.3 (types, reference bounds and admissible coefficients). Let \(D\) be \(\{3,4\}\) or \(\{3,4,5\}\).
(i) A \(D\)-type is a tuple \(T=(d;k_3,k_4,k_5)\) of nonnegative integers with \(d\in D\), \(k_3+k_4+k_5=d\), and \(k_j=0\) for \(j\notin D\). In a graph whose degrees all lie in \(D\), the type of a vertex \(v\) is \(T(v)=(d(v);k_3,k_4,k_5)\), where \(k_j\) is the number of neighbors of \(v\) of degree \(j\).
(ii) The reference bounds of \(T\) are the vector \(r_T\in(0,1)^d\) consisting of \(k_3\) copies of \(r_{d3}\), \(k_4\) copies of \(r_{d4}\) and \(k_5\) copies of \(r_{d5}\), and the reference star bound of \(T\) is \(C_T(\tau):=C_d(\tau;r_T)\), the center bound (6.2).
(iii) For a transfer vector \(t=(t_{34},t_{35},t_{45})\in\mathbb{R}^3\), the transfer term of \(T\) is \[\lambda_T(t)=\begin{cases} -k_4t_{34}-k_5t_{35}, & d=3,\\ k_3t_{34}-k_5t_{45}, & d=4,\\ k_3t_{35}+k_4t_{45}, & d=5. \end{cases}\]
(iv) Coefficients \((a_d)_{d\in D}\) are admissible for \(D\) if for every \(\tau\in[-3,3]\) there is a transfer vector \(t\) with \[C_T(\tau)+\lambda_T(t)\le a_d\qquad\text{for every $D$-type $T=(d;k_3,k_4,k_5)$.}\]
Thus a vertex of degree \(i\) sends the amount \(t_{ij}\) along each edge to a neighbor of degree \(j>i\). Admissibility says that, at every threshold in \([-3,3]\), some choice of these transfers makes the reference star bound plus the transfer term of every type at most the coefficient of its degree. There are \(10\) types of degree \(3\), \(15\) of degree \(4\) and \(21\) of degree \(5\), so \(46\) types for \(D=\{3,4,5\}\) and \(9\) for \(D=\{3,4\}\). The pure cubic type \(T_0=(3;3,0,0)\) has \(C_{T_0}=f_{3,r_{33}}\le F_3\) by (6.6) and Definition 6.7, and \(\lambda_{T_0}=0\).
Lemma 7.4 (charging). Let \(D\) be as in Definition 7.3, let \(H\) be a graph all of whose degrees lie in \(D\), and let \(t\in\mathbb{R}^3\). Then \(\sum_{v\in V(H)}\lambda_{T(v)}(t)=0\). Consequently, if real numbers \(x_v\) (\(v\in V(H)\)) and \(e\ge0\) satisfy \(x_v+\lambda_{T(v)}(t)\le a_{d(v)}+e\) for every \(v\), then \[\sum_{v\in V(H)}x_v\ \le\ \sum_{d\in D}a_dn_d(H)+e\,|V(H)| .\]
Proof. Write \(\lambda_{T(v)}(t)\) as a sum over the edges at \(v\): by the definition, an edge \(vu\) with \(d(v)=i\) and \(d(u)=j\) contributes \(-t_{ij}\) if \(i<j\), \(+t_{ji}\) if \(i>j\), and \(0\) if \(i=j\). So each edge joining degrees \(i<j\) contributes \(-t_{ij}\) at its end of degree \(i\) and \(+t_{ij}\) at its end of degree \(j\), and each edge joining equal degrees contributes nothing. Summing over all vertices therefore gives \(0\). Summing the inequalities \(x_v\le a_{d(v)}+e-\lambda_{T(v)}(t)\) over \(v\) gives the second claim. ∎
7.2 The certified coefficients
Admissibility is a statement about all thresholds in \([-3,3]\) and about \(46\) types at once, each with a reference star bound that is an integral of an infimum over correlation matrices. We verify it for three coefficient vectors by a computer-assisted proof in ball arithmetic and exact rational arithmetic.
Proposition 7.5 (certified admissibility). Each of the triples \[\mathsf{P}=(F_3,\,0.2575,\,0.3667),\qquad \mathsf{R}=(0.1455,\,0.2530,\,0.3600),\qquad \mathsf{S}=\bigl(\tfrac5{32},\,\tfrac14,\,\tfrac{11}{32}\bigr)\] is admissible for \(D=\{3,4,5\}\).
Code: certify_star_bounds_arb_owen.py, check_star_bound_cells.py, star-bound-arb-owen/, run_all.sh
If \((a_3,a_4,a_5)\) is admissible for \(\{3,4,5\}\), then \((a_3,a_4)\) is admissible for \(\{3,4\}\): every \(\{3,4\}\)-type is a \(\{3,4,5\}\)-type with the same reference star bound, and its transfer term, \(-k_4t_{34}\) for \(d=3\) and \(k_3t_{34}\) for \(d=4\), is the same function of the same transfer vector. In particular \((F_3,0.2575)\) and \((\frac5{32},\frac14)\) are admissible for \(\{3,4\}\).
What is certified. For each of the three triples, the accompanying code partitions \([-3,3]\) into finitely many cells \([t_0,t_1]\). For each cell it stores one transfer vector \(t\) with \(|t_{ij}|\le1\) and, for each type \(T\), a rational number \(I^{\rm lo}_T(t_1)\). It then verifies, in exact rational arithmetic, that \[\begin{equation*} \tag{7.1} \widehat\Phi(-t_0)-I^{\rm lo}_T(t_1)+\lambda_T(t)<a_d\qquad\text{for every type $T\ne T_0$,} \end{equation*}\] where \(\widehat\Phi(-t_0)\) is a rational upper bound for \(\Phi(-t_0)\). The numbers \(I^{\rm lo}_T(t_1)\) are lower bounds for a Riemann sum of the integral in (6.2) at \(\tau=t_1\), in which \(P_{\min}\) is replaced by a lower bound: the bound of Lemma A.1, or, for the seven degree-\(3\) types with unequal reference bounds, the larger of that bound and the arc bound of Lemma A.2. Appendix A.2 proves that (7.1) implies \(C_T(\tau)+\lambda_T(t)\le a_d\) for every \(\tau\in[t_0,t_1]\) (Lemmas A.6 and A.7). The pure cubic type \(T_0\) is not checked: \(C_{T_0}\le F_3\le a_3\) for all three triples, and \(\lambda_{T_0}=0\).
How. Every value of \(\varphi\), \(\Phi\), \(S_d\) and of the arc bound that enters \(I^{\rm lo}\) is a lower or upper bound obtained from an enclosure in Arb ball arithmetic (Johansson 2017), rounded outward. The arc bound is evaluated through a closed form in Owen’s \(T\) function (Owen 1956) (Lemma A.8). A separate program rechecks (7.1) for all cells in exact rational arithmetic. Floating point is used only to make choices, such as the transfer vectors; no floating-point value enters (7.1). For \(\mathsf{P}\), whose coefficient at degree \(3\) is \(F_3\) itself, the recheck uses the lower bound of \(F_3\) in Proposition 6.9 in place of \(a_3\). For \(\mathsf{R}\) and \(\mathsf{S}\), the upper bound of \(F_3\) there gives \(F_3\le a_3\). Appendices A.2.4 and A.2.5 give the details, the numbers of cells and the smallest slacks.
Proof of Proposition 7.5. Fix one of the triples and \(\tau\in[-3,3]\); let \([t_0,t_1]\) be a cell of the certificate containing \(\tau\) (the cells tile \([-3,3]\), which the code checks), and \(t\) its stored transfer vector. For \(T=T_0\), \(C_{T_0}(\tau)+\lambda_{T_0}(t)\le F_3\le a_3\). For every other type \(T\) of degree \(d\), Lemmas A.6 and A.7 and the construction of \(I^{\rm lo}_T\) described in Appendix A.2 give \(C_T(\tau)\le\Phi(-t_0)-I^{\rm lo}_T(t_1)\), and (7.1) gives \(C_T(\tau)+\lambda_T(t)<a_d\). ∎
Remark 7.6 (how close to the method’s limit). The certified coefficients are slightly larger than what the star bounds allow pointwise, because a cell bound loses a term of first order in the cell width. For orientation, floating-point quadrature at sampled thresholds (not certified) gives the following values. For \(D=\{3,4\}\) with \(a_3=F_3\), the smallest possible \(a_4\) is about \(0.25659\); it is attained near \(\tau\approx-0.089\) by a degree-\(4\) vertex all of whose neighbors have degree \(3\). For \(D=\{3,4,5\}\) with \(a_3=F_3\), the binding configuration is a degree-\(5\) vertex with five neighbors of degree \(3\), near \(\tau\approx-0.105\), and the smallest \(a_5\) is about \(0.36621\). The triple \(\mathsf{S}\) lies about \(5\cdot10^{-4}\) inside the corresponding floating-point optimum.
The method does not appear able to bring the coefficient of \(n_4\) down to \(F_4\). On \((3,4)\)-biregular graphs of large girth, every edge joins a vertex of degree \(3\) to one of degree \(4\). A numerical evaluation of the frontier density of the sweep on such graphs, with \(a_3=F_3\), requires a coefficient of about \(0.2533\) at degree \(4\), above \(F_4\approx0.2458\).
7.3 Expected frontier sizes
We now combine the star bounds, the certificate and the correlation estimate of Section 5. The explicit continuity estimate of Lemma 6.3, which is uniform in the threshold, turns the factor \(1-\varepsilon_R\) in (L1) into an additive error of \(205\,\varepsilon_R\) per vertex; no slack of the certificate is needed for this step.
Lemma 7.7 (expected frontiers in the mixed case). Let \((a_3,a_4,a_5)\) be one of \(\mathsf{P},\mathsf{R},\mathsf{S}\), let \(H\) be a graph all of whose degrees lie in \(\{3,4,5\}\), put \(\beta(H)=a_3n_3(H)+a_4n_4(H)+a_5n_5(H)\), and let \(R\) be such that \(\varepsilon_R<1\). Then for every \(\tau\in[-3,3]\), \[\mathbb{E}\,|\partial^{+}S_\tau|\ \le\ \beta(H)+205\,\varepsilon_R\,|V(H)| .\]
Proof. Let \(v\) be a vertex of type \(T=(d;k_3,k_4,k_5)\), with neighbors \(u_1,\dots,u_d\). The vector \((Y_v,Y_{u_1},\dots,Y_{u_d})\) is centered Gaussian with unit variances, and by (L1) it is a \(d\)-star with lower bounds \(r'_T:=(1-\varepsilon_R)r_T\), after ordering the neighbors as in \(r_T\). The event \(\{v\in\partial^{+}S_\tau\}\) is its frontier event. By Lemma 6.2, \[\mathbb{P}(v\in\partial^{+}S_\tau)\le C_d(\tau;r'_T).\] Every entry of \(r_T\) and of \(r'_T\) lies in \((0,r_{33}]\), and the entries differ by \(\varepsilon_R(r_T)_i\le\varepsilon_R\). By Lemma 6.3(b), since \(|\tau|\le3\) and \(d\le5\), \[\mathbb{P}(v\in\partial^{+}S_\tau)\le C_T(\tau)+205\,\varepsilon_R .\] By Proposition 7.5 there is a transfer vector \(t\) with \(C_T(\tau)+\lambda_T(t)\le a_d\) for every \(\{3,4,5\}\)-type \(T\). Hence \(\mathbb{P}(v\in\partial^{+}S_\tau)+\lambda_{T(v)}(t)\le a_{d(v)}+205\,\varepsilon_R\) for every vertex \(v\), and Lemma 7.4 with \(x_v=\mathbb{P}(v\in\partial^{+}S_\tau)\) and \(e=205\,\varepsilon_R\) gives the claim, since \(\mathbb{E}|\partial^{+}S_\tau|=\sum_v\mathbb{P}(v\in\partial^{+}S_\tau)\). ∎
7.4 Concentration
Three lemmas turn bounds on expectations at finitely many thresholds into a bound for one realization at all thresholds. The first (Lemma 7.8) is deterministic: it bounds a frontier at any threshold by the frontier at a neighboring grid point plus the number of labels between the two, and outside the grid by the number of labels beyond its ends. The plain sweep uses only its statements about outer frontiers; the median-switched sweep of Section 8 also uses those about inner frontiers.
Lemma 7.8 (grid). Let \(y\) be any labeling of a graph \(G\), let \(\tau_0<\tau_1<\dots<\tau_K\), and for \(0\le j<K\) let \(N_j=|\{v:\tau_j<y_v\le\tau_{j+1}\}|\).
(i) If \(\tau_j\le\tau<\tau_{j+1}\), then \(|\partial^{+}S_\tau|\le|\partial^{+}S_{\tau_{j+1}}|+N_j\) and \(|\partial^{-}S_\tau|\le|\partial^{-}S_{\tau_j}|+N_j\).
(ii) If \(\tau<\tau_0\), then \(|\partial^{+}S_\tau|\le\Delta(G)\cdot|\{v:y_v\le\tau_0\}|\) and \(|\partial^{-}S_\tau|\le|\{v:y_v\le\tau_0\}|\).
(iii) If \(\tau\ge\tau_K\), then \(|\partial^{+}S_\tau|\le|\{v:y_v>\tau_K\}|\).
Proof. Let \(v\in\partial^{+}S_\tau\), so \(y_v>\tau\) and some neighbor \(u\) (a witness) has \(y_u\le\tau\). (i) If \(y_v>\tau_{j+1}\), then \(v\in\partial^{+}S_{\tau_{j+1}}\) with the same witness, because \(y_u\le\tau<\tau_{j+1}\). Otherwise \(\tau_j\le\tau<y_v\le\tau_{j+1}\), and \(v\) is counted by \(N_j\). For the inner frontier, let \(u\in\partial^{-}S_\tau\), with a neighbor \(x\) such that \(y_u\le\tau<y_x\). If \(y_u\le\tau_j\), then \(u\in S_{\tau_j}\) and \(y_x>\tau\ge\tau_j\), so \(u\in\partial^{-}S_{\tau_j}\). Otherwise \(\tau_j<y_u\le\tau<\tau_{j+1}\), and \(u\) is counted by \(N_j\). (ii) Map \(v\) to a witness \(u\). Then \(y_u\le\tau<\tau_0\), and each \(u\) is the image of at most \(d(u)\le\Delta(G)\) vertices. For the inner frontier, \(\partial^{-}S_\tau\subseteq S_\tau\subseteq S_{\tau_0}\). (iii) \(y_v>\tau\ge\tau_K\). ∎
The second lemma is the concentration step shared by all sweeps of this paper. It combines the variance bound of Lemma 4.10, Chebyshev’s inequality and a union bound over the finitely many counts. The counts of a sweep are frontier sizes, window counts \(|\{v:\tau_j<Y_v\le\tau_{j+1}\}|\) and tail counts. Each is a sum over the vertices \(v\) of indicators that depend only on the labels on \(N[v]\), hence on \((Z_w)_{w\in B_{\rho+1}(v)}\), where \(\rho\) is the locality radius of Lemma 5.6.
Lemma 7.9 (concentration of local counts). Let \(G\) be a graph with \(N\) vertices and \(\Delta(G)\le\Delta\), where \(\Delta\ge2\), let \((Y_v)\) be labels of \(G\) as in Definition 5.2 with underlying variables \((Z_w)_{w\in V(G)}\), let \(\varrho\ge0\) be an integer, and let \(W_1,\dots,W_\mu\) be sums over \(v\in V(G)\) of \([0,1]\)-valued measurable functions of \((Z_w)_{w\in B_\varrho(v)}\). If \(\lambda>0\) and \(\mu N\Delta^{2\varrho}<2\lambda^2\), then some realization of \((Z_w)\) has pairwise distinct labels and \(|W_i-\mathbb{E}W_i|<\lambda\) for all \(i\).
Proof. By Lemma 4.10 with \(a=1\) and \(A_v=B_\varrho(v)\), each \(W_i\) satisfies \(\mathbb{P}(|W_i-\mathbb{E}W_i|\ge\lambda)\le N\Delta^{2\varrho}/(2\lambda^2)\). By the union bound, the probability that some \(W_i\) deviates from its mean by at least \(\lambda\) is at most \(\mu N\Delta^{2\varrho}/(2\lambda^2)<1\). By Lemma 5.6(ii) the labels are pairwise distinct with probability \(1\). So the event that the labels are pairwise distinct and every \(W_i\) lies within \(\lambda\) of its mean has positive probability, and in particular it is nonempty. ∎
The third lemma is the plain sweep itself: bounds on the expected outer frontiers at the thresholds in \([-3,3]\) give a path decomposition. In it, \(\beta\) is the target width, \(e\) is the error per vertex in the expected frontiers, and the grid of thresholds has \(K\) points per unit length. The hypothesis \(\Delta\,\Phi(-3)\,N\le\beta\) covers the thresholds outside \([-3,3]\), and the last hypothesis is the condition of Lemma 7.9 for the \(12K+2\) counts used in the proof, with \(\lambda=N^{7/8}\).
Lemma 7.10 (plain sweep from expected frontiers). Let \(G\) be a graph with \(N\) vertices and \(\Delta(G)\le\Delta\) for some \(\Delta\ge2\), let \((Y_v)\) be labels of \(G\) as in Definition 5.2 with locality radius \(\rho\) (Lemma 5.6), let \(K\ge1\) be an integer, and let \(\beta,e\ge0\). Suppose that \(\mathbb{E}|\partial^{+}S_\tau|\le\beta+eN\) for every \(\tau\in[-3,3]\), that \(\Delta\,\Phi(-3)\,N\le\beta\), and that \((12K+2)\,\Delta^{2\rho+2}<2N^{3/4}\). Then \[\mathop{\mathrm{pw}}(G)\ \le\ \beta+\Bigl(e+\frac{\varphi(0)}K\Bigr)N+\Delta\,N^{7/8}.\]
Proof. We fix a realization in which the counts at a grid of thresholds are all close to their means, and then bound the outer frontier at every threshold by Lemma 7.8. Let \(\tau_j=-3+j/K\) for \(0\le j\le6K\), and consider the \(12K+2\) counts \[\begin{gather*} A_j=|\partial^{+}S_{\tau_j}|\ \ (1\le j\le6K),\qquad N_j=|\{v:\tau_j<Y_v\le\tau_{j+1}\}|\ \ (0\le j<6K),\\ C_-=|\{v:Y_v\le-3\}|,\qquad C_+=|\{v:Y_v>3\}| . \end{gather*}\] Each is a sum over \(v\) of indicators that depend only on the labels on \(N[v]\), hence on \((Z_w)_{w\in B_{\rho+1}(v)}\) (Lemma 5.6(iii),(iv)). The last hypothesis is the condition of Lemma 7.9 with \(\varrho=\rho+1\), \(\mu=12K+2\) and \(\lambda=N^{7/8}\), so some realization has pairwise distinct labels and every count within \(N^{7/8}\) of its mean. Fix it. Since each \(Y_v\) is standard normal, \(\mathbb{E}N_j\le N\varphi(0)/K\) and \(\mathbb{E}C_\pm=N\Phi(-3)\), and \(\mathbb{E}A_j\le\beta+eN\) by hypothesis. Let \(\tau\in\mathbb{R}\).
If \(\tau\in[\tau_j,\tau_{j+1})\) for some \(j<6K\), then by Lemma 7.8(i), \(|\partial^{+}S_\tau|\le A_{j+1}+N_j\le\beta+(e+\varphi(0)/K)N+2N^{7/8}\).
If \(\tau<-3\), then by Lemma 7.8(ii), \(|\partial^{+}S_\tau|\le\Delta\,C_-\le\Delta\,\Phi(-3)N+\Delta N^{7/8}\le\beta+\Delta N^{7/8}\).
If \(\tau\ge3\), then by Lemma 7.8(iii), \(|\partial^{+}S_\tau|\le C_+\le\Phi(-3)N+N^{7/8}\le\beta+N^{7/8}\).
Since \(\Delta\ge2\), every outer frontier has at most \(\beta+(e+\varphi(0)/K)N+\Delta N^{7/8}\) vertices, and Lemma 4.1 for the injective labeling of the fixed realization gives the claim (\(N\ge1\) by the last hypothesis). ∎
7.5 Proofs of Theorems 7.1 and 7.2
We first prove the mixed bounds for graphs of minimum degree at least \(3\), then remove this assumption with the reductions of Definition 4.2, and finally prove Theorem 7.1(a).
Proposition 7.11 (mixed bounds for minimum degree \(3\)). Let \((a_3,a_4,a_5)\) be one of \(\mathsf{P},\mathsf{R},\mathsf{S}\). There is a function \(\rho^*(N)=o(N)\) such that every graph \(H\) on \(N\) vertices all of whose degrees lie in \(\{3,4,5\}\) satisfies \[\mathop{\mathrm{pw}}(H)\ \le\ a_3n_3(H)+a_4n_4(H)+a_5n_5(H)+\rho^*(N).\]
Proof. We let the label parameter \(R\) grow slowly with \(N\) and apply Lemma 7.10 to the expected frontiers of Lemma 7.7. Write \(\beta(H)=a_3n_3(H)+a_4n_4(H)+a_5n_5(H)\). Fix \(R_0\) with \(\varepsilon_R<1\) for \(R\ge R_0\), and for \(N\ge1\) let \[R(N):=\max\Bigl\{R\in\{R_0,\dots,N\}:\ (12R+2)\,25^{\varrho_R+1}\le N^{1/2}\Bigr\},\] with \(R(N):=0\) if the set is empty. For each fixed \(R\ge R_0\) the condition holds for all large \(N\), so \(R(N)\to\infty\) as \(N\to\infty\). Put \[\rho^*(N):=\begin{cases} \bigl(205\,\varepsilon_{R(N)}+\varphi(0)/R(N)\bigr)N+5N^{7/8}, & R(N)\ge R_0,\\ N, & \text{otherwise.} \end{cases}\] Since \(\varepsilon_R\to0\) and \(R(N)\to\infty\), \(\rho^*(N)=o(N)\). If \(R(N)=0\) the claim holds because \(\mathop{\mathrm{pw}}(H)\le N-1\). So let \(R:=R(N)\ge R_0\) and use the labels with parameter \(R\). By Lemma 7.7, \(\mathbb{E}|\partial^{+}S_\tau|\le\beta(H)+205\,\varepsilon_RN\) for every \(\tau\in[-3,3]\). Every vertex of \(H\) has degree at least \(3\), and \(a_5\ge a_4\ge a_3\ge F_3>0.14\) for all three triples (Proposition 6.9), so \(\beta(H)\ge0.14N>5\Phi(-3)N\), as \(5\Phi(-3)<0.0068\). Finally \((12R+2)\,25^{\varrho_R+1}\le N^{1/2}<2N^{3/4}\). Hence Lemma 7.10 applies with \(\Delta=5\), the locality radius \(\varrho_R\) of (L2), \(K=R\), \(\beta=\beta(H)\) and \(e=205\,\varepsilon_R\), and gives \(\mathop{\mathrm{pw}}(H)\le\beta(H)+(205\,\varepsilon_R+\varphi(0)/R)N+5N^{7/8}=\beta(H)+\rho^*(N)\). ∎
Proof of Theorem 7.2 and of Theorem 7.1(b),(c). Let \((a_3,a_4,a_5)\) be one of \(\mathsf{P},\mathsf{R},\mathsf{S}\), and put \(a_0=a_1=a_2=0\); then \(0=a_0\le a_1\le\dots\le a_5\) in all three cases. Let \(\bar\rho\) be the running maximum (4.2) of the function \(\rho^*\) of Proposition 7.11, with \(\rho^*(0):=0\); it is nonnegative, nondecreasing and \(o(n)\). By Proposition 7.11, every graph \(J\) with \(\delta(J)\ge3\) and \(\Delta(J)\le5\) satisfies \(\mathop{\mathrm{pw}}(J)\le\sum_da_dn_d(J)+\bar\rho(|V(J)|)\). Then Corollary 4.6 with \(k=5\) gives, for every nonempty graph \(G\) with \(\Delta(G)\le5\), \[\mathop{\mathrm{pw}}(G)\le a_3n_3+a_4n_4+a_5n_5+\bar\rho(n)+3\log_2n+1,\] which is Theorem 7.2; the remainder depends only on \(n\). (That corollary reduces \(G\) by a maximal sequence of the operations of Definition 4.2 and applies Lemma 4.5 without deletions.)
Theorem 7.1(b) and (c) are the cases \(\mathsf{P}\) and \(\mathsf{S}\) of Theorem 7.2 for graphs with \(\Delta(G)\le4\), for which \(n_5=0\). In such graphs no vertex type involves degree \(5\), so only the certified inequalities of the \(\{3,4\}\)-types and the transfer \(t_{34}\) are used; in particular the case \(d=5\) of Lemma 6.5 is not needed for Theorem 7.1. ∎
For Theorem 7.1(a) we use the padded labels of degree \(4\) (Definition 5.2(a) with \(p=4\)) with an integer radius \(R\ge2\). Every arc has length \(\frac12\ln3\), so that \(X_v=\sum_{w:\,\mathop{\mathrm{dist}}(v,w)\le R}3^{-\mathop{\mathrm{dist}}(v,w)/2}Z_w\) and \(Y_v=X_v/\sqrt{\mathop{\mathrm{Var}}X_v}\). By Lemma 5.4, every edge \(uv\) of a graph with \(\Delta\le4\) has \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_R:=r_{44}(1-1/R)\), and by Lemma 5.6 the locality radius is \(\rho=R\). The bound \(F_4n+o(n)\) needs no reductions: vertices of every degree from \(0\) to \(4\) are handled by padding the star (Corollary 6.8).
Proposition 7.12 (fixed radius). Let \(R\ge2\) be an integer and let \(G\) be a graph with \(\Delta(G)\le4\) and \(n\ge3^{8R}\) vertices. Then \[\mathop{\mathrm{pw}}(G)\le\Bigl(F_4+\frac{179}R\Bigr)n+4n^{7/8}.\]
Proof. We apply Lemma 7.10 with the ideal star bound. Use the padded labels with radius \(R\). For a vertex \(v\) of degree \(k\le4\), the vector \((Y_v;Y_u,u\in N(v))\) has unit variances and incident correlations at least \(r_R\). By Corollary 6.8 with \(d=4\), (6.6) and Lemma 6.3(b) with \(\bar r=r_{33}>r_{44}\) and \(\varepsilon=r_{44}-r_R=r_{44}/R\), for every \(\tau\in[-3,3]\), \[\mathbb{P}(v\in\partial^{+}S_\tau)\le f_{4,r_R}(\tau)\le f_{4,r_{44}}(\tau)+\frac{205\,r_{44}}R\le F_4+\frac{178}R ,\] so \(\mathbb{E}|\partial^{+}S_\tau|\le(F_4+178/R)n\) for every \(\tau\in[-3,3]\). We check the remaining hypotheses of Lemma 7.10 with \(\Delta=4\), \(\rho=R\), \(K=R\), \(\beta=F_4n\) and \(e=178/R\). First, \(4\Phi(-3)n<0.0055\,n<F_4n\) by Proposition 6.9. Second, \(8(12R+2)<45^R\) for every \(R\ge2\) (at \(R=2\) this reads \(208<2025\), and the left side less than doubles when \(R\) grows by one), so \((12R+2)\,16^{R+1}<2\cdot45^R\cdot16^R\le2\cdot729^R=2\cdot3^{6R}\le2n^{3/4}\), since \(n\ge3^{8R}\). Hence Lemma 7.10 gives \(\mathop{\mathrm{pw}}(G)\le F_4n+(178+\varphi(0))n/R+4n^{7/8}\le(F_4+179/R)n+4n^{7/8}\), using \(\varphi(0)<0.399\). ∎
Proof of Theorem 7.1(a). For \(n\ge3^{16}\) put \(R(n)=\lfloor\frac18\log_3n\rfloor\ge2\), so that \(n\ge3^{8R(n)}\), and \(\rho(n)=\frac{179}{R(n)}n+4n^{7/8}\); for \(n<3^{16}\) put \(\rho(n)=n\). Since \(R(n)\to\infty\), \(\rho(n)=o(n)\), and so is its running maximum \(\bar\rho\) (4.2). By Proposition 7.12 with \(R=R(n)\) for \(n\ge3^{16}\) and trivially otherwise, \(\mathop{\mathrm{pw}}(G)\le F_4n+\rho(n)\) for every graph \(G\) with \(\Delta(G)\le4\), which is the bound \(F_4n+o(n)\). For the bound with coefficients \((F_4,F_4)\), let \(J\) be a graph with \(\delta(J)\ge3\) and \(\Delta(J)\le4\); then \(|V(J)|=n_3(J)+n_4(J)\), so \(\mathop{\mathrm{pw}}(J)\le F_4\bigl(n_3(J)+n_4(J)\bigr)+\bar\rho(|V(J)|)\). Corollary 4.6 with \(k=4\) and \((a_0,\dots,a_4)=(0,0,0,F_4,F_4)\) gives \(\mathop{\mathrm{pw}}(G)\le F_4n_3+F_4n_4+\bar\rho(n)+3\log_2n+1\) for every nonempty graph \(G\) with \(\Delta(G)\le4\). ∎