4 Preliminaries
This section fixes notation and collects the tools that all later sections share. Two of them shape the whole of Part I. The layout lemma turns a labeling of the vertices into a path decomposition; it is the only way in which path decompositions are built in Part I (Section 4.2). The reductions on vertices of degree at most two let the main proofs assume minimum degree at least three, at an additive loss of \(O(\log n)\) in the pathwidth (Section 4.3).
Of the remaining subsections, Section 4.1 fixes the notation for graphs, decompositions and remainders \(o(n)\), Section 4.4 the Gaussian notation and comparison tools, and Section 4.5 proves a variance bound for sums of locally dependent variables, which makes frontier sizes concentrate.
4.1 Graphs, decompositions and remainders
Graphs are finite and simple. We follow Diestel’s notation: \(V(G)\) and \(E(G)\) are the vertex and edge sets, \(uv\in E(G)\) is an edge, \(d_G(v)\) or \(d(v)\) is the degree, \(N(v)\) and \(N[v]=N(v)\cup\{v\}\) are the open and closed neighborhoods, \(N(S)=\bigcup_{v\in S}N(v)\) for \(S\subseteq V(G)\), and \(\delta(G)\), \(\Delta(G)\) are the minimum and maximum degree. \(G[U]\) is the subgraph induced by \(U\) and \(G-U\) is obtained by deleting \(U\). We write \(n=|V(G)|\), \(m=|E(G)|\) and \(n_d=n_d(G)\) for the number of vertices of degree \(d\). The graph distance \(\mathop{\mathrm{dist}}(v,w)\in\mathbb{N}\cup\{\infty\}\) is the number of edges of a shortest \(v\)–\(w\) path, and \(B_k(v)=\{w:\mathop{\mathrm{dist}}(v,w)\le k\}\) is the ball of radius \(k\). The sizes of these balls enter the variance bound of Lemma 4.10 and the analysis of the algorithms. If \(\Delta(G)\le\Delta\) with \(\Delta\ge2\), then \[\begin{equation*} \tag{4.1} |B_k(v)|\le 1+\sum_{i=1}^{k}\Delta(\Delta-1)^{i-1}\le\sum_{i=0}^{k}\Delta^{i}\le 2\Delta^{k}, \end{equation*}\] because a vertex at distance \(i\ge1\) from \(v\) has at most \(\Delta-1\) neighbors at distance \(i+1\), and \(\sum_{i=0}^k\Delta^i=(\Delta^{k+1}-1)/(\Delta-1)\le2\Delta^k\) for \(\Delta\ge2\). For the maximum degrees \(3\), \(4\) and \(5\), which occur most often below, evaluating the middle sum gives the sharper bounds \[\begin{aligned} |B_k(v)|&\le3\cdot2^k-2&&\text{if }\Delta=3,\\ |B_k(v)|&\le2\cdot3^k-1&&\text{if }\Delta=4,\\ |B_k(v)|&\le\tfrac13\bigl(5\cdot4^k-2\bigr)\le2\cdot4^k&&\text{if }\Delta=5. \end{aligned}\]
Decompositions.
A tree decomposition of \(G\) is a pair \((T,(W_t)_{t\in V(T)})\) of a tree \(T\) and bags \(W_t\subseteq V(G)\) such that every edge of \(G\) lies in some bag and, for every vertex \(x\), the nodes \(t\) with \(x\in W_t\) induce a nonempty subtree \(T_x\) of \(T\). Its width is \(\max_t|W_t|-1\), and the treewidth \(\mathop{\mathrm{tw}}(G)\) is the minimum width. Path decompositions, pathwidth and cutwidth are as in Section 3; a path decomposition is a tree decomposition whose tree is a path. The empty graph has \(\mathop{\mathrm{pw}}=\mathop{\mathrm{tw}}=-1\). We use the following elementary facts without further mention: \(\mathop{\mathrm{tw}}(G)\le\mathop{\mathrm{pw}}(G)\); both widths are monotone under taking subgraphs; the pathwidth of a disjoint union is the maximum over its parts (concatenate the decompositions); and adding a set \(X\) of vertices to every bag of a path decomposition of \(G-X\) gives a path decomposition of \(G\), so \(\mathop{\mathrm{pw}}(G)\le\mathop{\mathrm{pw}}(G-X)+|X|\). A path decomposition is given in interval form if it is described by the number \(s\) of bags and, for each vertex, the indices of the first and the last bag containing it; the algorithms of Section 10 output their decompositions in this form.
Remainders.
Every remainder \(o(n)\) in a statement about a class \(\mathcal G\) of graphs means the following: there is a function \(\rho\colon\mathbb{N}\to\mathbb{R}\) with \(\rho(n)/n\to0\) such that the statement holds with \(o(n)\) replaced by \(\rho(|V(G)|)\) for every \(G\in\mathcal G\). So the remainder depends on \(n\) only, and not on the graph. The same convention applies to \(o(m)\). The running maximum of a function \(\rho\colon\mathbb{N}\to\mathbb{R}\) is \[\begin{equation*} \tag{4.2} \bar\rho(x):=\max\bigl(\{0\}\cup\{\rho(k):k\in\mathbb{N},\ k\le x\}\bigr)\qquad(x\ge0). \end{equation*}\] It is nonnegative, nondecreasing and at least \(\rho\) on \(\mathbb{N}\). If \(\rho(n)=o(n)\), then \(\bar\rho(x)=o(x)\): for \(\varepsilon>0\) there is \(N\) with \(\rho(k)\le\varepsilon k\) for \(k\ge N\), so \(\bar\rho(x)\le\max\{\bar\rho(N),\varepsilon x\}\) for \(x\ge N\), which is at most \(\varepsilon x\) for all large \(x\). Hence every remainder may be assumed nonnegative and nondecreasing.
4.2 Layouts from labelings
A labeling of \(G\) is a map \(y\colon V(G)\to\mathbb{R}\), \(v\mapsto y_v\); it is injective if all labels are distinct. For \(t\in\mathbb{R}\) let \(S_t=\{v:y_v\le t\}\) be the sublevel set, and define its outer and inner frontiers \[\partial^{+}S_t=N(S_t)\setminus S_t=\{v:\ y_v>t,\ \exists u\in N(v):\ y_u\le t\},\qquad \partial^{-}S_t=\{u\in S_t:\ N(u)\not\subseteq S_t\}.\] The same notation \(\partial^{+}S=N(S)\setminus S\) and \(\partial^{-}S=\{u\in S:N(u)\not\subseteq S\}\) is used for arbitrary sets \(S\subseteq V(G)\). Every later bound on pathwidth comes from the following lemma, applied to a random labeling whose frontiers are small at every threshold. The maxima over \(t\) in the lemma are attained, since \(S_t\) takes at most \(n+1\) values.
Lemma 4.1 (layout). Let \(G\) be a nonempty graph and \(y\) an injective labeling of \(G\), let \(v_1,\dots,v_n\) be the vertices in increasing order of their labels, and let \(T_i=\{v_1,\dots,v_i\}\). Then the bags \(W_i=\{v_i\}\cup\partial^{+}T_i\) (\(1\le i\le n\)) form a path decomposition of \(G\) of width \(\max_i|\partial^{+}T_i|\). Moreover, \(\mathop{\mathrm{pw}}(G)\le\max_{t\in\mathbb{R}}|\partial^{+}S_t|\) and \(\mathop{\mathrm{pw}}(G)\le\max_{t\in\mathbb{R}}|\partial^{-}S_t|\).
The quantity \(\max_i|\partial^{-}T_i|\), minimized over all orderings, is the vertex separation number of \(G\), and Kinnersley proved that it equals the pathwidth (Kinnersley 1992 Theorem 3.1). The bound by inner frontiers is the easy direction of that theorem, and the bound by outer frontiers is the same statement for the reversed order. The algorithms of Section 10 use the explicit bags.
Proof. The proof of Lemma 3.2 shows that the bags \(W_i\) form a path decomposition of width \(\max_i|\partial^{+}T_i|\), since \(\partial^{+}T_i=N(T_i)\setminus T_i\); it uses neither the labels nor a degree bound. By injectivity \(T_i=S_{y_{v_i}}\), so \(\max_i|\partial^{+}T_i|\le\max_t|\partial^{+}S_t|\); in fact a bound \(|\partial^{+}S_t|\le w\) for all \(t\) in any set of thresholds that contains all labels already gives \(\mathop{\mathrm{pw}}(G)\le w\).
For the bound by inner frontiers, apply the bound by outer frontiers to the injective labeling \(-y\). Its sublevel sets are the sets \(\{v:y_v\ge-t\}=V(G)\setminus A\), where \(A=\{v:y_v<-t\}\) is either empty or equal to \(S_s\) for \(s=\max\{y_v:y_v<-t\}\). For every \(A\subseteq V(G)\) we have \(\partial^{+}(V(G)\setminus A)=\{a\in A:N(a)\not\subseteq A\}=\partial^{-}A\), and \(\partial^{-}\emptyset=\emptyset\). Hence the outer frontiers for \(-y\) are inner frontiers for \(y\), which gives the claim. ∎
4.3 Reductions on vertices of degree at most two
The pathwidth bounds of this paper are proved for graphs of minimum degree at least three and then transferred to all graphs. The transfer uses the classical series–parallel reductions, which remove vertices of degree at most two. Reduction rules of this kind are used in the pathwidth bounds of Kneis, Mölle, Richter and Rossmanith (Kneis et al. 2009) and of Edwards and McDermid (Edwards and McDermid 2015). The reduction theorem of Edwards and McDermid (Edwards and McDermid 2015 Theorem 3.2) interleaves the reductions with vertex deletions and bounds the effect of all reductions on the pathwidth once, at the end. Edwards and McDermid take two facts from (Kneis et al. 2009): that reductions commute with deletions, and that undoing all reductions increases the pathwidth by at most \(O(\log n)\). Lemma 4.5 below replaces both facts by a single self-contained statement, which needs no uniqueness of the reduced graph. We first define the reductions and prove two auxiliary facts about treewidth, then prove Lemma 4.5 and derive the transfer from minimum degree three to all graphs (Corollary 4.6).
Definition 4.2 (reduction operations). The reduction operations on a graph \(H\) are:
(R1) delete an isolated vertex;
(R2) delete a vertex of degree \(1\);
(R3) for a vertex \(v\) of degree \(2\) whose neighbors \(x,y\) are not adjacent, delete \(v\) and add the edge \(xy\) (suppression);
(R4) delete a vertex of degree \(2\) whose two neighbors are adjacent.
A sequence of reduction operations is maximal if no reduction operation applies to the final graph.
We use three properties of the reduction operations throughout.
(RP1) Each operation removes one vertex, produces a simple graph, and does not increase the degree of any remaining vertex: (R1), (R2) and (R4) only delete a vertex, and in (R3) the vertices \(x\) and \(y\) each lose the neighbor \(v\) and gain one new neighbor.
(RP2) Whether an operation applies at a vertex \(v\), and its effect, depend only on \(v\), its neighbors and the adjacency among them. So operations inside one component of a graph are operations on the whole graph.
The proof of Lemma 4.5 needs two standard facts about graphs of bounded treewidth (Bodlaender 1998).
Lemma 4.3. Let \(G=G_1\cup G_2\) where \(V(G_1)\cap V(G_2)=K\) and \(K\) is either a single vertex or the two ends of an edge that belongs to both \(G_1\) and \(G_2\). Then \(\mathop{\mathrm{tw}}(G)\le\max\{\mathop{\mathrm{tw}}(G_1),\mathop{\mathrm{tw}}(G_2)\}\).
Proof. Join tree decompositions of \(G_1\) and \(G_2\) of minimum width by an edge between a bag of each that contains \(K\). ∎
Lemma 4.4. Let \(k\ge0\) and let \(H\) be a graph with \(N\ge1\) vertices and \(\mathop{\mathrm{tw}}(H)\le k\). Then \(\mathop{\mathrm{pw}}(H)\le(k+1)\lfloor\log_2N\rfloor\).
Proof. Some bag \(X\) of a tree decomposition of width at most \(k\) leaves only components with at most \(N/2\) vertices (the standard balanced-separator argument). Decompose these components by induction, concatenate the decompositions and add \(X\) to every bag.
∎
The next lemma is the bookkeeping device of the paper. Suppose that an arbitrary interleaving of reduction operations and vertex deletions is applied to a graph. Then the pathwidth of the original graph exceeds that of the final graph by at most the number of deleted vertices plus \(O(\log n)\), however many reductions were made. The lemma is used for the passage from minimum degree three to all graphs (Corollary 4.6) and in the deletion process of Section 9. Its part (b) describes how \(F-D\) attaches to the final graph; Appendix A.5.6 uses it to compute the decomposition.
Lemma 4.5 (undoing reductions). Let \(F\) be a nonempty graph. Apply to \(F\) any finite sequence of steps, each of which is a reduction operation or the deletion of a vertex of the current graph. Let \(D\) be the set of vertices removed by deletions and \(R\) the final graph. Then:
(a) \(\mathop{\mathrm{pw}}(F)\le|D|+\mathop{\mathrm{pw}}(R)+3\log_2|V(F)|+1\);
(b) every edge of \(F-D\) with both ends in \(V(R)\) is an edge of \(R\), and for every component \(C\) of \((F-D)-V(R)\), the set \(N_{F-D}(C)\) is empty, a single vertex, or the two ends of an edge of \(R\), and \(\mathop{\mathrm{tw}}(F[C])\le2\).
The proof is in Appendix A.1.
In the simplest application no vertex is deleted and the sequence of reduction operations is maximal, so the final graph is empty or has minimum degree at least three by (RP3). For coefficients that are nondecreasing in the degree, this transfers every bound for minimum degree three to all graphs.
Corollary 4.6. Let \(k\in\{3,4,\dots\}\cup\{\infty\}\), let \(0=a_0=a_1=a_2\le a_3\le a_4\le\cdots\) (up to \(a_k\)), and let \(\rho\colon\mathbb{N}\to\mathbb{R}_{\ge0}\) be nondecreasing. Suppose that every graph \(J\) with \(\delta(J)\ge3\) and \(\Delta(J)\le k\) satisfies \(\mathop{\mathrm{pw}}(J)\le\sum_da_dn_d(J)+\rho(|V(J)|)\). Then every nonempty graph \(G\) with \(\Delta(G)\le k\) satisfies \[\mathop{\mathrm{pw}}(G)\le\sum_da_dn_d(G)+\rho(n)+3\log_2n+1 .\]
Proof. Apply a maximal sequence of reduction operations to \(G\) and let \(R\) be the final graph. Degrees do not increase, so \(\Delta(R)\le k\), and either \(R\) is empty or \(\delta(R)\ge3\). Since the \(a_d\) are nonnegative and nondecreasing in \(d\), and every vertex of \(R\) has degree in \(R\) at most its degree in \(G\), \[\sum_da_dn_d(R)=\sum_{v\in V(R)}a_{d_R(v)}\le\sum_{v\in V(R)}a_{d_G(v)}\le\sum_{v\in V(G)}a_{d_G(v)}=\sum_da_dn_d(G).\] If \(R\) is nonempty, the hypothesis and the monotonicity of \(\rho\) give \(\mathop{\mathrm{pw}}(R)\le\sum_da_dn_d(G)+\rho(n)\); if \(R\) is empty, \(\mathop{\mathrm{pw}}(R)=-1\) satisfies the same bound. Lemma 4.5 with \(D=\emptyset\) completes the proof. ∎
4.4 Gaussian notation and comparison tools
The star bounds of Section 6 and the switch lemma of Section 8 compare orthant probabilities, probabilities of the form \(\mathbb{P}(Y_i>t_i\ \forall i)\), or in the switch lemma combinations of them, of Gaussian vectors \(Y\) with different correlation matrices. This subsection fixes the Gaussian notation and states the three classical tools that these comparisons use: Plackett’s identity, Slepian’s inequality and Sheppard’s formula.
We write \(\varphi\) and \(\Phi\) for the standard normal density and distribution function, \(N(\mu,\sigma^2)\) for the normal distribution, and \[\varphi_2(x,y;\rho)=\frac{1}{2\pi\sqrt{1-\rho^2}}\exp\Bigl(-\frac{x^2-2\rho xy+y^2}{2(1-\rho^2)}\Bigr)\] for the standard bivariate normal density with correlation \(\rho\in(-1,1)\). Note that \(\varphi_2(x,y;\rho)\le(2\pi\sqrt{1-\rho^2})^{-1}\).
A random vector is centered Gaussian if every linear combination of its coordinates is a centered normal variable (possibly degenerate); its distribution \(N(0,\Sigma)\) is determined by its covariance matrix \(\Sigma\), which may be singular. A correlation matrix is a positive semidefinite matrix with unit diagonal. Every \(k\times k\) correlation matrix \(C\) is the Gram matrix \(C_{ij}=\langle v_i,v_j\rangle\) of unit vectors \(v_1,\dots,v_k\in\mathbb{R}^k\) (for instance the columns of \(C^{1/2}\)), and then \(U_i=\langle v_i,G\rangle\) with \(G\sim N(0,I_k)\) defines a centered Gaussian vector with correlation matrix \(C\).
For \(r\in[-1,1]\) we write \(s_r=\sqrt{1-r^2}\). In Part I the letter \(r\) always denotes a correlation level. If \((Y_1,\dots,Y_k)\) is centered Gaussian with \(\mathop{\mathrm{Var}}Y_i>0\) for all \(i\), then \(\mathbb{P}(Y_i=t_i)=0\) for every \(i\) and every \(t_i\in\mathbb{R}\), so strict and weak inequalities between coordinates and constants may be exchanged in all probabilities below.
The comparison tool used throughout is Slepian’s inequality: raising the correlations of a Gaussian vector, with its variances fixed, raises its orthant probabilities. We state it with arbitrary thresholds and singular covariance matrices allowed, because both cases occur (the ideal stars of Section 6 have singular covariance). It is derived from Plackett’s identity, which also bounds how fast an orthant probability can change with the correlations.
Lemma 4.7 (Plackett’s identity (Plackett 1954)). Let \(k\ge2\) and \(t\in\mathbb{R}^k\), and for a positive definite \(k\times k\) correlation matrix \(\Sigma\) let \(P(\Sigma)=\mathbb{P}(Y_i>t_i\ \forall i)\) with \(Y\sim N(0,\Sigma)\). Then \(P\) is continuously differentiable in the off-diagonal entries \(\Sigma_{ij}=\Sigma_{ji}\) (\(i<j\)) on the open set of positive definite correlation matrices, and \[\frac{\partial P}{\partial\Sigma_{ij}} =\varphi_2(t_i,t_j;\Sigma_{ij})\cdot\mathbb{P}\bigl(Y_l>t_l\ \forall l\notin\{i,j\}\bigm|Y_i=t_i,\ Y_j=t_j\bigr),\] where the conditional probability refers to the nondegenerate Gaussian conditional distribution and equals \(1\) if \(k=2\). In particular \(0\le\partial P/\partial\Sigma_{ij}\le(2\pi\sqrt{1-\Sigma_{ij}^2})^{-1}\).
The identity is classical (Plackett 1954); for a proof see (Adler and Taylor 2007, sec. 2.2) and the survey (Li and Shao 2001). It gives Slepian’s inequality, and it is used in the lemma on two exceedances in the proof of the switch lemma (Lemma 8.11).
For \(k=3\), \(\{i,j,l\}=\{1,2,3\}\) and equal thresholds \(t_i=t_j=t_l=h\), the conditional distribution in Lemma 4.7 is explicit: the distribution of \(Y_l\) given \(Y_i=Y_j=h\) is normal with \[\begin{equation*} \tag{4.3} \text{mean}\ \ h\,\frac{\Sigma_{il}+\Sigma_{jl}}{1+\Sigma_{ij}}\qquad\text{and variance}\ \ \frac{\det\Sigma}{1-\Sigma_{ij}^2}>0 . \end{equation*}\] Indeed, the Gaussian conditioning formula gives the conditional mean \((\Sigma_{il},\Sigma_{jl})\bigl(\begin{smallmatrix}1&\Sigma_{ij}\\\Sigma_{ij}&1\end{smallmatrix}\bigr)^{-1} \bigl(\begin{smallmatrix}h\\h\end{smallmatrix}\bigr)\), and \((1,1)^{\mathsf T}\) is an eigenvector of the \(2\times2\) matrix with eigenvalue \(1+\Sigma_{ij}\); the conditional variance is the Schur complement of that matrix in \(\Sigma\), which is \(\det\Sigma/(1-\Sigma_{ij}^2)\) and positive because \(\Sigma\) is positive definite. Section 8 uses this formula in the preparation of Lemma 8.11.
Lemma 4.8 (Slepian’s inequality (Slepian 1962)). Let \(Y=(Y_1,\dots,Y_k)\) and \(Y'=(Y'_1,\dots,Y'_k)\) be centered Gaussian vectors with \(\mathop{\mathrm{Var}}Y_i=\mathop{\mathrm{Var}}Y'_i>0\) for all \(i\) and \(\mathop{\mathrm{Cov}}(Y_i,Y_j)\ge\mathop{\mathrm{Cov}}(Y'_i,Y'_j)\) for all \(i\ne j\). Then, for every \(t\in\mathbb{R}^k\), \[\mathbb{P}(Y_i>t_i\ \forall i)\ge\mathbb{P}(Y'_i>t_i\ \forall i) \qquad\text{and}\qquad \mathbb{P}(Y_i\le t_i\ \forall i)\ge\mathbb{P}(Y'_i\le t_i\ \forall i).\]
Proof. For positive definite covariance matrices this is Slepian’s inequality (Slepian 1962) (Adler and Taylor 2007, sec. 2.2): after scaling to unit variances, integrate Lemma 4.7 along the segment from the correlation matrix of \(Y'\) to that of \(Y\). For singular covariance matrices, apply it to \(\sqrt{1-\eta}\,Y+\sqrt\eta\,\xi\) and \(\sqrt{1-\eta}\,Y'+\sqrt\eta\,\xi'\) with independent standard Gaussian vectors \(\xi,\xi'\), and let \(\eta\to0\); the probabilities converge by dominated convergence, since \(\mathbb{P}(Y_i=t_i)=0\). The second inequality is the first one for \(-Y\), \(-Y'\) and \(-t\).
∎
Sheppard’s formula evaluates orthant probabilities at threshold zero. We use it for two and three coordinates.
Lemma 4.9 (Sheppard’s formula (Sheppard 1899)). Let \((X_1,X_2,X_3)\) be centered Gaussian with unit variances and put \(\vartheta_{ij}=\arccos\mathop{\mathrm{Corr}}(X_i,X_j)\in[0,\pi]\). Then \[\mathbb{P}(\operatorname{sgn}X_1\ne\operatorname{sgn}X_2)=\frac{\vartheta_{12}}{\pi},\qquad \mathbb{P}(X_1>0,\ X_2>0)=\frac12-\frac{\vartheta_{12}}{2\pi}=\frac14+\frac{\arcsin\mathop{\mathrm{Corr}}(X_1,X_2)}{2\pi},\] and \[\mathbb{P}(X_1>0,\ X_2>0,\ X_3>0)=\frac12-\frac{\vartheta_{12}+\vartheta_{13}+\vartheta_{23}}{4\pi}.\]
Proof. Each \(X_i\) is nonzero with probability \(1\). The first formula is Lemma 3.3(a), whose proof applies to any centered Gaussian pair with unit variances (write it as a pair of unit-norm sums of independent standard normals; the case \(\mathop{\mathrm{Corr}}(X_1,X_2)=-1\) is trivial). Since \(X\) and \(-X\) have the same distribution, the two coordinates are both positive and both negative with equal probabilities, which gives the second; the last expression follows from \(\arcsin x=\frac\pi2-\arccos x\).
For three coordinates, three nonzero signs have either \(0\) or \(2\) disagreeing pairs. Hence \(\mathbb{E}\#\{\text{disagreeing pairs}\}=2\mathbb{P}(\text{not all signs equal})\), so by the first formula \(\mathbb{P}(\text{all signs equal})=1-(\vartheta_{12}+\vartheta_{13}+\vartheta_{23})/(2\pi)\), and symmetry under \(X\mapsto-X\) halves this. ∎
4.5 Local dependence and concentration
The labels of Section 5 are functions of independent variables attached to the vertices, and each label depends only on the variables in a ball of bounded radius. Counts such as frontier sizes are then sums of locally dependent indicators, whose variance is linear in \(n\). The plain sweep (Section 7), the cubic sweep (Section 8) and the algorithms (Section 10) combine the following bound with Chebyshev’s inequality.
Lemma 4.10 (local variance). Let \(G\) be a graph with \(n\) vertices, let \((Z_w)_{w\in V(G)}\) be independent random variables, and for every vertex \(v\) let \(A_v\subseteq V(G)\) and let \(I_v\) be a random variable with values in \([0,a]\) that is a measurable function of \((Z_w)_{w\in A_v}\). Put \(W=\sum_vI_v\). Then \[\mathop{\mathrm{Var}}W\le\frac{a^2}4\cdot\#\bigl\{(u,v)\in V(G)^2:\ A_u\cap A_v\ne\emptyset\bigr\}.\] If moreover \(\Delta(G)\le\Delta\) for some \(\Delta\ge2\) and \(A_v\subseteq B_\rho(v)\) for every \(v\), then \(\mathop{\mathrm{Var}}W\le\frac{a^2}{4}\,n\max_v|B_{2\rho}(v)|\le\frac{a^2}2\,n\Delta^{2\rho}\) and \(\mathbb{P}(|W-\mathbb{E}W|\ge\lambda)\le a^2n\Delta^{2\rho}/(2\lambda^2)\) for every \(\lambda>0\).
Proof. The first bound is proved as Lemma 3.5: \(\mathop{\mathrm{Cov}}(I_u,I_v)=0\) if \(A_u\cap A_v=\emptyset\), and \(|\mathop{\mathrm{Cov}}(I_u,I_v)|\le a^2/4\) otherwise. If \(A_v\subseteq B_\rho(v)\) for all \(v\), then \(A_u\cap A_v\ne\emptyset\) implies \(v\in B_{2\rho}(u)\), so there are at most \(n\max_u|B_{2\rho}(u)|\le2n\Delta^{2\rho}\) such pairs by (4.1). The last claim is Chebyshev’s inequality. ∎