8 The median-switched sweep: maximum degree 3 and 4
This section proves the following two theorems, where \(c_{3}=\frac{3}{4\pi}\arccos\frac56\approx0.1398\). With the bootstrap of Section 9 they give the sequences \(\mathsf{C}\) and \(\mathsf{M}\) of Theorem 9.2.
Theorem 8.1 (maximum degree \(3\)). Every graph \(G\) with \(\Delta(G)\le 3\) satisfies \(\mathop{\mathrm{pw}}(G)\le c_{3}\, n+o(n)\).
Lean proof: C3.c3MainClaim (what is formalised)
Theorem 8.2 (maximum degree \(4\)). Every graph \(G\) with \(\Delta(G)\le 4\) satisfies \(\mathop{\mathrm{pw}}(G)\le c_{3}\, n_3+0.2627\,n_4+o(n)\).
Lean proof under H6, H7: Sw4.targetThm62 (what is formalised)
Theorem 8.2 contains Theorem 8.1, but its proof needs more: a switch lemma for stars with unequal correlation bounds (Lemma A.10), which we prove with a computer-assisted certificate (Appendix A.3.2), and a computer-assisted charging at nonzero thresholds (Proposition A.13). The proof of Theorem 8.1 uses no computation.
Compared with the plain sweep of Section 7, only the layout changes (Section 2.4): vertices still enter in increasing order of their geometric labels, but the layout keeps inner frontiers while the threshold is negative and outer frontiers while it is positive, and passes from one to the other at threshold zero by a short sequence of bags, the connector.
After the notation of Section 8.1, the proof of Theorem 8.1 has four steps. Section 8.2 constructs the layout (Lemma 8.4), with an ordering lemma for the connector (Lemma 8.3). Section 8.3 bounds the frontier probabilities away from threshold zero (Proposition 8.8). Section 8.4 bounds the expected values of \(L_0\) and \(L'_0\), which control the connector bags at threshold zero (the switch lemma, Lemma 8.9). Section 8.5 adds the concentration argument and completes the proof. The proof does not use Slepian’s inequality: at nonnegative thresholds a pointwise coupling suffices, and negative thresholds are reduced to nonnegative ones by the symmetry \(Y\mapsto-Y\).
The proof of Theorem 8.2, in Appendix A.3.1, uses the same layout with a larger set at threshold zero, together with the mixed labels and the charging of Section 7. Finally, Section 10 turns the proof of Theorem 8.1 into an algorithm, and Appendix A.6 that of Theorem 8.2.
8.1 Setting
Throughout, \(G\) is a finite simple graph with \(\Delta(G)\le3\); it may be disconnected and may have vertices of degree \(0\), \(1\) or \(2\). Recall \(r_*=r_{33}=\frac{2\sqrt2}3\) and \(s_r=\sqrt{1-r^2}\), and put \[\begin{equation*} \tag{8.1} b(r)=\frac{3r^2-1}2,\qquad \kappa(r)=\frac3{4\pi}\arccos b(r)\qquad(0<r<1). \end{equation*}\] For \(r\in(0,1)\) we have \(b(r)\in(-\frac12,1)\), so \(\kappa\) is well defined and continuous on \((0,1)\). Since \(b(r_*)=\frac{3\cdot\frac89-1}2=\frac56\), we have \(\kappa(r_*)=c_{3}\). By Lemma 8.6 below, \(\kappa(r)\) is the value at threshold zero of the ideal star function \(f_{3,r}\).
Labels.
Fix an integer \(R\ge2\) and let \((Y_v)_{v\in V(G)}\) be the geometric labels at radius \(R\), that is, the padded labels of degree \(3\) (Definition 5.2(a) with \(p=3\)): for i.i.d. standard normal \((Z_w)_{w\in V(G)}\), \(X_v=\sum_{w:\,\mathop{\mathrm{dist}}(v,w)\le R}2^{-\mathop{\mathrm{dist}}(v,w)/2}Z_w\) and \(Y_v=X_v/\sqrt{\mathop{\mathrm{Var}}X_v}\). Put \(r_R=r_*(1-\frac1R)\in(0,r_*)\). We use three properties.
(L1) The vector \((Y_v)_v\) is centered Gaussian with unit variances, and every edge \(uv\) satisfies \(\mathop{\mathrm{Corr}}(Y_u,Y_v)\ge r_R\) (Lemma 5.4, cubic case).
(We take \(R\ge2\) only so that \(r_R>0\).) Since \(-Y\) is again centered Gaussian with the same covariance, \(-Y\) has the same distribution as \(Y\); we call this sign symmetry. Every label has a continuous distribution, so for each fixed \(t\) the events \(\{Y_v=t\}\) are null.
Threshold zero.
For a labeling \(y\colon V(G)\to\mathbb{R}\), the sublevel sets \(S_t=\{v:y_v\le t\}\) and their frontiers \(\partial^{+}S_t\), \(\partial^{-}S_t\) are as in Section 4.2. Put \(U=\partial^{-}S_0\) and \(W=\partial^{+}S_0\), and let \(D\) be the set of vertices of degree \(3\) all of whose neighbors lie on the other side of zero, that is, vertices \(v\) with \(d(v)=3\) and either \(y_v\le0<\min_{x\in N(v)}y_x\) or \(y_v>0\ge\max_{x\in N(v)}y_x\). A vertex of \(D\) with \(y_v\le0\) has a neighbor above zero and lies in \(U\); one with \(y_v>0\) has a neighbor at or below zero and lies in \(W\). Hence \(D\subseteq U\cup W\). Put \(U'=U\setminus D\), \(W'=W\setminus D\) and \[\begin{equation*} \tag{8.2} L_0=|U|+|D\cap W|=|U'|+|D|,\qquad L_0'=|W|+|D\cap U|=|W'|+|D|. \end{equation*}\] The two expressions agree because \(U\) and \(W\) are disjoint and \(D=(D\cap U)\cup(D\cap W)\). At threshold zero, the width of the median-switched layout of Section 8.2 is controlled by \(\max(L_0,L_0')\) (Lemma 8.4).
8.2 The median-switched layout
This subsection proves the deterministic part of Theorem 8.1: a path decomposition whose width is controlled by inner frontiers below zero, outer frontiers above zero, and \(\max(L_0,L_0')\) at zero (Lemma 8.4). The connector at zero needs an ordering lemma, which we state abstractly. Think of the elements of \(Q\) below as the vertices of \(W'\), to be added one at a time, and of the items as the vertices of \(U'\), each of which can be dropped once its at most two neighbors in \(W'\) are present.
Lemma 8.3 (connector order). Let \(Q\) be a finite set with \(k\) elements and let \(P\) be a finite set of items, each item \(p\) having a nonempty set \(e(p)\subseteq Q\) of at most two endpoints. For an ordering \(q_1,\dots,q_k\) of \(Q\) and \(0\le j\le k\), let \(c(j)\) be the number of items \(p\) with \(e(p)\subseteq\{q_1,\dots,q_j\}\). Then some ordering satisfies \[\begin{equation*} \tag{8.3} j-c(j)\le\max(0,\,k-|P|)+1\qquad\text{for all }0\le j\le k. \end{equation*}\]
Proof. We use induction on \(k\). If some nonempty proper subset of \(Q\) is closed (defined below), the instance splits into two smaller ones, which we order one after the other, the one with smaller excess first (Case 1). Otherwise each new element can be chosen to complete an item whose other endpoint is already present (Case 2).
If \(k=0\), then \(P=\emptyset\) because endpoint sets are nonempty, and (8.3) reads \(0\le1\). Let \(k\ge1\). Call a set \(Y\subseteq Q\) closed if every item \(p\) satisfies \(e(p)\subseteq Y\) or \(e(p)\subseteq Q\setminus Y\). For a closed set \(A\) let \(P_A=\{p:e(p)\subseteq A\}\) and define its excess \(\operatorname{ex}(A)=|A|-|P_A|\); thus \(\operatorname{ex}(Q)=k-|P|\).
Case 1: some nonempty proper subset \(Y\) of \(Q\) is closed. Then \(Q\setminus Y\) is closed as well, and since endpoint sets are nonempty, every item lies in exactly one of \(P_Y\) and \(P_{Q\setminus Y}\). Let \(A\) be the one of \(Y,Q\setminus Y\) with the smaller excess (either one if they are equal) and \(B\) the other, so that \[\operatorname{ex}(Q)=\operatorname{ex}(A)+\operatorname{ex}(B)\ge2\operatorname{ex}(A).\] The pairs \((A,P_A)\) and \((B,P_B)\) satisfy the hypotheses of the lemma with fewer than \(k\) elements, so by induction they have orderings \(a_1,\dots,a_{|A|}\) and \(b_1,\dots,b_{|B|}\) with counting functions \(c_A\), \(c_B\) satisfying (8.3) with \(\operatorname{ex}(A)\), respectively \(\operatorname{ex}(B)\), in place of \(k-|P|\). Order \(Q\) as \(a_1,\dots,a_{|A|},b_1,\dots,b_{|B|}\).
For \(j\le|A|\), an item covered by \(\{a_1,\dots,a_j\}\) has an endpoint in \(A\) and hence lies in \(P_A\), so \(c(j)=c_A(j)\) and \(j-c(j)\le\max(0,\operatorname{ex}(A))+1\). If \(\operatorname{ex}(A)\le0\) this is at most \(1\); otherwise \(\operatorname{ex}(Q)\ge2\operatorname{ex}(A)>\operatorname{ex}(A)\). In both cases \(j-c(j)\le\max(0,\operatorname{ex}(Q))+1\).
For \(j=|A|+j'\) with \(1\le j'\le|B|\), all items of \(P_A\) are covered, and an item of \(P_B\) is covered exactly when \(e(p)\subseteq\{b_1,\dots,b_{j'}\}\). Hence \(c(j)=|P_A|+c_B(j')\) and \[j-c(j)=\operatorname{ex}(A)+\bigl(j'-c_B(j')\bigr) \le\operatorname{ex}(A)+\max(0,\operatorname{ex}(B))+1 .\] If \(\operatorname{ex}(B)\ge0\), the right side is \(\operatorname{ex}(Q)+1\le\max(0,\operatorname{ex}(Q))+1\). If \(\operatorname{ex}(B)<0\), then \(\operatorname{ex}(A)\le\operatorname{ex}(B)<0\) and the right side is less than \(1\). This proves (8.3) in Case 1.
Case 2: no nonempty proper subset of \(Q\) is closed. Choose \(q_1\in Q\) arbitrarily. Suppose \(q_1,\dots,q_j\) have been chosen with \(1\le j<k\), and let \(X=\{q_1,\dots,q_j\}\). Since \(X\) is nonempty and proper, it is not closed, so some item \(p\) has endpoints both in \(X\) and in \(Q\setminus X\). As \(|e(p)|\le2\), we have \(e(p)=\{x,y\}\) with \(x\in X\) and \(y\notin X\); put \(q_{j+1}=y\). Then \(p\) is covered by \(\{q_1,\dots,q_{j+1}\}\) but not by \(X\), so \(c(j+1)\ge c(j)+1\). Since \(c(1)\ge0\), we get \(c(j)\ge j-1\) for every \(1\le j\le k\), and \(c(0)=0\). Hence \(j-c(j)\le1\) for all \(j\), which implies (8.3). ∎
The layout itself has three phases. The inner phase is the vertex separation layout of Kinnersley (Kinnersley 1992): each bag consists of the new vertex and the inner frontier of the preceding prefix. The outer phase is the layout of Lemma 4.1. The connector between them is new.
Lemma 8.4 (median-switched layout). Let \(G\) be a graph with \(\Delta(G)\le3\), let \(y\colon V(G)\to\mathbb{R}\) be injective, and let \(w\ge0\) be a real number such that
(i) \(|\partial^{-}S_t|\le w\) for every \(t<0\);
(ii) \(|\partial^{+}S_t|\le w\) for every \(t>0\); and
(iii) \(\max(L_0,L_0')+1\le w\), with \(L_0,L_0'\) as in (8.2).
Then \(\mathop{\mathrm{pw}}(G)\le w\).
The proof builds the bags from any ordering of \(W'\) that satisfies (8.3), not only from that of Lemma 8.3, because the algorithm of Appendix A.5.8 uses another one.
The bags.
Let \(G\) be a graph with \(\Delta(G)\le3\) and let \(y\colon V(G)\to\mathbb{R}\) be injective. Let \(v_1,\dots,v_n\) be the vertices in increasing order of \(y\), let \(\ell=|S_0|\), and write \(T_i=\{v_1,\dots,v_i\}\) for \(0\le i\le n\). Let \(P\) be the set of vertices \(u\in U'\) for which \(e(u):=N(u)\cap W'\) is nonempty; these are the items, and \(e(u)\) is the set of endpoints of \(u\). Let \(k=|W'|\), and let \(q_1,\dots,q_k\) be an ordering of \(W'\). The inner bags are \(A_i=\{v_i\}\cup\partial^{-}T_{i-1}\) for \(1\le i\le\ell\), the outer bags are \(A_i=\{v_i\}\cup\partial^{+}T_i\) for \(\ell<i\le n\), and the connector bags are \[C_{-1}=U\cup(D\cap W),\qquad C_j=D\cup\bigl\{u\in P:e(u)\not\subseteq\{q_1,\dots,q_{j-1}\}\bigr\}\cup\{q_1,\dots,q_j\} \quad(0\le j\le k).\] In words, the connector starts from \(C_{-1}=U'\cup D\) and drops the vertices of \(U'\) without neighbors in \(W'\). It then adds the vertices of \(W'\) one at a time and drops each item one step after its last endpoint has been added. The vertices of \(D\) stay in every connector bag.
Lemma 8.5 (the bags of the layout). Let \(G\), \(y\), \(P\) and \(q_1,\dots,q_k\) be as above. Then \(|e(u)|\le2\) for every \(u\in P\). If moreover \(w\) satisfies (i)–(iii) of Lemma 8.4 and the ordering \(q_1,\dots,q_k\) of \(W'\) satisfies (8.3) for \(Q=W'\) and the items \(P\), then \(A_1,\dots,A_\ell,C_{-1},C_0,\dots,C_k,A_{\ell+1},\dots,A_n\) is a path decomposition of \(G\) of width at most \(w\).
Proof. A vertex \(u\in U'\) is not in \(D\), so either \(d(u)\le2\) or \(u\) has a neighbor at or below zero; in both cases \(u\) has at most two neighbors above zero, and \(|e(u)|\le2\).
For the second claim we check the size bound and the three axioms of a path decomposition (every vertex in a bag, every edge in a bag, the bags containing a vertex consecutive). Note that \(T_i=S_t\) for every \(t\) with \(y_{v_i}\le t<y_{v_{i+1}}\) (with \(y_{v_0}=-\infty\) and \(y_{v_{n+1}}=+\infty\)), and \(v_i\in S_0\) if and only if \(i\le\ell\).
Inner bags. For \(1\le i\le\ell\) we have \(y_{v_i}\le0\), so \(T_{i-1}=S_t\) for some \(t<y_{v_i}\le0\), and \(|A_i|\le w+1\) by (i).
Connector bags. A vertex of \(D\) lies in all connector bags, a vertex \(q_j\) of \(W'\) in \(C_j,\dots,C_k\), an item \(u\in P\) in \(C_{-1},\dots,C_J\), where \(J\ge1\) is the largest position of an element of \(e(u)\) (so \(u\) is dropped one step after its last endpoint has been added), every other vertex of \(U\) in \(C_{-1}\) only, and no other vertex in any connector bag. So the connector bags containing a vertex of \(U\) form a prefix of \(C_{-1},C_0,\dots,C_k\), and those containing a vertex of \(W\) form a suffix.
We have \(|C_{-1}|=L_0\), and \(|C_0|=|D|+|P|\le|D|+|U'|=L_0\). For \(1\le j\le k\), the number of items still present in \(C_j\) is \(|P|-c(j-1)\), where \(c\) is the counting function of Lemma 8.3 for the ordering \(q_1,\dots,q_k\), so by (8.3) at \(j-1\), \[|C_j|=|D|+|P|-c(j-1)+j\le|D|+|P|+\max(0,k-|P|)+2=|D|+\max(|P|,|W'|)+2 .\] Since \(|P|\le|U'|\), this is at most \(\max(L_0,L_0')+2\le w+1\) by (iii).
Outer bags. For \(\ell<i\le n\) we have \(y_{v_i}>0\), so \(T_i=S_t\) for some \(t\ge y_{v_i}>0\), and \(|A_i|\le w+1\) by (ii).
Every vertex \(v_i\) lies in \(A_i\). If \(\ell=0\) or \(\ell=n\), then \(U=W=D=\emptyset\) and the connector bags are empty; the arguments below remain valid.
Intervals for lower vertices. Let \(u=v_a\) with \(a\le\ell\), and let \(b\) be the largest index of a neighbor of \(u\) (\(b=0\) if \(u\) is isolated). For \(i\le\ell\) we have \(u\in A_i\) if and only if \(i=a\) or \(a\le i-1<b\), so the inner bags containing \(u\) are \(A_a,\dots,A_{\min(\max(a,b),\ell)}\). No outer bag contains \(u\), because \(u\in T_i\) for every \(i>\ell\). If \(u\notin U\), then \(b\le\ell\) and \(u\) is in no connector bag, so its bags are consecutive. If \(u\in U\), then \(b>\ell\), so its bags are \(A_a,\dots,A_\ell\) followed by a prefix of the connector bags.
Intervals for upper vertices. Let \(x=v_c\) with \(c>\ell\), and let \(a\) be the smallest index of a neighbor of \(x\) (\(a=\infty\) if \(x\) is isolated). No inner bag contains \(x\). For \(i>\ell\) we have \(x\in A_i\) if and only if \(i=c\), or \(i<c\) and \(x\) has a neighbor in \(T_i\), that is, \(a\le i<c\); so the outer bags containing \(x\) are \(A_{\max(a,\ell+1)},\dots,A_c\) if \(a<c\), and \(A_c\) alone otherwise. If \(x\notin W\), then \(a>\ell\) and \(x\) lies in no connector bag, so its bags are consecutive. If \(x\in W\), then \(a\le\ell\), so its bags are a suffix of the connector bags followed by \(A_{\ell+1},\dots,A_c\).
Edges. Let \(v_av_b\) be an edge with \(a<b\). If \(b\le\ell\), then \(v_a\in\partial^{-}T_{b-1}\), because \(v_a\in T_{b-1}\) and its neighbor \(v_b\) is not, so both ends lie in \(A_b\). If \(a>\ell\), then \(v_b\in\partial^{+}T_a\), because \(v_b\notin T_a\) and its neighbor \(v_a\) is in \(T_a\), so both ends lie in \(A_a\). Otherwise \(u=v_a\in U\) and \(x=v_b\in W\). If \(x\in D\cap W\), both ends lie in \(C_{-1}\). If \(u\in D\cap U\), both ends lie in \(C_k\), which contains \(D\) and all of \(W'\). Otherwise \(u\in U'\) and \(x\in W'\), so \(u\in P\) and \(x=q_j\in e(u)\) for some \(j\); then \(e(u)\not\subseteq\{q_1,\dots,q_{j-1}\}\), so \(u\in C_j\), and \(x\in C_j\).
Hence the sequence of bags is a path decomposition with all bags of size at most \(w+1\), that is, of width at most \(w\). ∎
Proof of Lemma 8.4. By Lemma 8.5, every item \(u\in P\) has one or two endpoints \(e(u)\subseteq W'\), so Lemma 8.3 applies to \(Q=W'\) and the items \(P\) and gives an ordering of \(W'\) that satisfies (8.3). For this ordering, Lemma 8.5 gives a path decomposition of \(G\) of width at most \(w\), so \(\mathop{\mathrm{pw}}(G)\le w\). ∎
8.3 The star comparison at nonnegative thresholds
This subsection bounds the probability that a vertex lies in an outer frontier at a threshold \(t\ge0\) by \(\kappa(r)\) (Proposition 8.8). By sign symmetry the same bound applies to inner frontiers at thresholds \(t\le0\). The proof has three ingredients. A pointwise coupling lowers the incident correlations to \(r\); the simplex theorem for three variables (Lemma 6.5) handles the neighbor residuals; and two facts about the ideal star function \(f_{3,r}\) give the value \(\kappa(r)\): its value at zero (Lemma 8.6) and its maximality at zero among nonnegative thresholds (Lemma 8.7).
The ideal \(3\)-star.
We use the ideal \(3\)-star of Definition 6.7. Let \(U^*=(U^*_1,U^*_2,U^*_3)\) be the regular simplex vector in three variables (Section 6): centered, with unit variances and all pairwise correlations \(-\frac12\), so that \(S_3(a)=\mathbb{P}(U^*_i>a\ \forall i)\). It is realized as the projections of a standard planar Gaussian vector onto three unit vectors at mutual angles \(\frac{2\pi}3\); in particular \(U^*_1+U^*_2+U^*_3=0\). For \(r\in(0,1)\) the ideal \(3\)-star at correlation \(r\) is \[Y^*_0\sim N(0,1)\ \text{independent of }U^*,\qquad Y^*_i=rY^*_0+s_rU^*_i\quad(i=1,2,3).\] Its incident correlations are \(r\), its neighbor-pair correlations are \(r^2-\frac12s_r^2=b(r)\), and \[\begin{equation*} \tag{8.4} Y^*_1+Y^*_2+Y^*_3=3rY^*_0 . \end{equation*}\] The difference of any two coordinates of the ideal star has positive variance, as \(r<1\) and \(s_r>0\), and each coordinate has a continuous distribution. So ties among the coordinates, or with a fixed threshold, have probability zero, and strict and non-strict inequalities may be exchanged in all events below. In particular the ideal star function \(f_{3,r}\) of Definition 6.7, given by (6.5) with \(d=3\), satisfies \(f_{3,r}(t)=\mathbb{P}(Y^*_0\ge t,\ \min_iY^*_i\le t)\).
Both lemmas on \(f_{3,r}\) below use Sheppard’s formula (Lemma 4.9).
Lemma 8.6. For every \(r\in(0,1)\), \(f_{3,r}(0)=\kappa(r)\).
Proof. If \(Y^*_i>0\) for all \(i\), then \(3rY^*_0>0\) by (8.4), so \(Y^*_0>0\). Hence the event \(\{\min_iY^*_i>0\}\) is contained in \(\{Y^*_0\ge0\}\), and \[f_{3,r}(0)=\mathbb{P}(Y^*_0\ge0)-\mathbb{P}(Y^*_0\ge0,\ \min_iY^*_i>0) =\frac12-\mathbb{P}(Y^*_1,Y^*_2,Y^*_3>0).\] The three neighbor coordinates have pairwise angles \(\arccos b(r)\), so Lemma 4.9 gives \(f_{3,r}(0)=\frac12-\bigl(\frac12-\frac{3\arccos b(r)}{4\pi}\bigr)=\kappa(r)\). ∎
The next lemma shows that, among nonnegative thresholds, the ideal star function is largest at the median \(0\). Its proof needs no derivative and no numerical evaluation, and holds for every \(r\in(0,1)\).
Lemma 8.7. For every \(r\in(0,1)\) and every \(t\ge0\), \(f_{3,r}(t)\le f_{3,r}(0)\).
Proof. We write \(f_{3,r}(0)-f_{3,r}(t)\) as a difference of two probabilities and bound the event that the smallest neighbor coordinate lies in \((0,t]\) by splitting according to which coordinate attains the minimum.
Let \(M=\min_iY^*_i\). If \(M>t\ge0\), then \(3rY^*_0>3t\) by (8.4), so \(Y^*_0>t/r\ge t\). Hence \(\{M>t\}\subseteq\{Y^*_0\ge t\}\), and since \(f_{3,r}(t)=\mathbb{P}(Y^*_0\ge t,\ M\le t)\), we get \(f_{3,r}(t)=\mathbb{P}(Y^*_0\ge t)-\mathbb{P}(M>t)\) for all \(t\ge0\) and \[f_{3,r}(0)-f_{3,r}(t)=\mathbb{P}(0\le Y^*_0<t)-\mathbb{P}(0<M\le t).\] It remains to show \(\mathbb{P}(0<M\le t)\le\mathbb{P}(0<Y^*_0\le t)\); the two probabilities \(\mathbb{P}(0\le Y^*_0<t)\) and \(\mathbb{P}(0<Y^*_0\le t)\) are equal because \(Y^*_0\) has a continuous distribution.
If \(0<M\le t\), then some coordinate attains the minimum, so the event is contained in the union of the three events \(A_k=\{0<Y^*_k\le t,\ Y^*_k\le Y^*_j\text{ for all }j\in\{1,2,3\}\}\). Fix \(k\) and write \(b=b(r)\in(-\frac12,1)\). For \(j\ne k\) put \(R_j=Y^*_j-bY^*_k\). Then \(\mathop{\mathrm{Cov}}(R_j,Y^*_k)=b-b=0\), so the pair \((R_j)_{j\ne k}\) is independent of \(Y^*_k\). On \(A_k\) we have \(R_j\ge Y^*_k-bY^*_k=(1-b)Y^*_k>0\) for both \(j\ne k\). Hence \[\mathbb{P}(A_k)\le\mathbb{P}(0<Y^*_k\le t)\cdot\mathbb{P}(R_j>0\text{ for both }j\ne k).\] The two residuals have variance \(1-b^2>0\) and covariance \(b-2b^2+b^2=b-b^2\), so their correlation is \(\rho=\frac{b-b^2}{1-b^2}=\frac b{1+b}\). The function \(b\mapsto\frac b{1+b}=1-\frac1{1+b}\) is increasing on \((-1,\infty)\) and equals \(\frac12\) at \(b=1\), so \(\rho<\frac12\) and \(\arccos\rho>\frac\pi3\). By Lemma 4.9, applied to the residuals divided by their common standard deviation (which does not change their signs), \(\mathbb{P}(R_j>0\text{ for both }j\ne k)<\frac12-\frac16=\frac13\). Since \(Y^*_k\) and \(Y^*_0\) are both standard normal, \(\mathbb{P}(A_k)\le\frac13\mathbb{P}(0<Y^*_0\le t)\), and summing over \(k\) gives the claim. ∎
We now compare an arbitrary star with the ideal one. The case \(d=3\) of the simplex theorem (Lemma 6.5) states that every centered Gaussian vector \((\eta_1,\eta_2,\eta_3)\) with unit variances, possibly with a singular correlation matrix, satisfies \(\mathbb{P}(\eta_i>\theta\ \forall i)\ge S_3(\theta)\) for every \(\theta\in\mathbb{R}\); equivalently, \(\mathbb{P}(\min_i\eta_i\le\theta)\le\mathbb{P}(\min_iU^*_i\le\theta)\). The proof below uses it for a vector with a repeated coordinate.
Proposition 8.8 (star bound at nonnegative thresholds). Let \(r\in(0,1)\), let \(0\le d\le3\), and let \((Y_0,Y_1,\dots,Y_d)\) be a centered Gaussian vector with unit variances and \(\mathop{\mathrm{Corr}}(Y_0,Y_i)\ge r\) for \(1\le i\le d\). Then for every \(t\ge0\), \[\mathbb{P}\bigl(Y_0\ge t,\ \exists i\in\{1,\dots,d\}:\ Y_i\le t\bigr)\le f_{3,r}(t)\le\kappa(r).\]
Proof. The second inequality is Lemmas 8.7 and 8.6. For the first, we lower the incident correlations to \(r\) by a pointwise coupling, condition on \(Y_0\), and apply the simplex theorem to the residuals. Put \(a_i=\mathop{\mathrm{Corr}}(Y_0,Y_i)\ge r\). If \(a_i=1\) then \(Y_i=Y_0\) with probability \(1\), and \(\{Y_0\ge t\ge Y_i\}\) is contained in the null event \(\{Y_0=t\}\); we discard such indices. If no index remains (in particular if \(d=0\)), the probability is \(0\le f_{3,r}(t)\). Otherwise, for each remaining \(i\) put \(\eta_i=(Y_i-a_iY_0)/s_{a_i}\). The variables \(\eta_i\) are standard normal, jointly Gaussian with \(Y_0\), and uncorrelated with \(Y_0\), so the vector of the \(\eta_i\) is independent of \(Y_0\). If fewer than three indices remain, repeat one of the \(\eta_i\) until there are three coordinates \((\eta_1,\eta_2,\eta_3)\); repetition does not change the event \(\{\exists i:\eta_i\le c\}\) for any \(c\).
On the event \(\{Y_0\ge t\}\) consider \(g(a)=(t-aY_0)/\sqrt{1-a^2}\) for \(a\in[r,1)\). Its derivative is \[g'(a)=\frac{-Y_0(1-a^2)+a(t-aY_0)}{(1-a^2)^{3/2}}=\frac{at-Y_0}{(1-a^2)^{3/2}}\le0,\] because \(at\le t\le Y_0\) (here \(t\ge0\) is used). Hence \(g(a_i)\le g(r)\), and \[Y_i\le t\iff\eta_i\le g(a_i)\ \Longrightarrow\ \eta_i\le g(r)=\frac{t-rY_0}{s_r}.\] By the independence of \(\eta\) and \(Y_0\) (Fubini) and Lemma 6.5 with \(d=3\), \[\begin{align*} \mathbb{P}(Y_0\ge t,\ \exists i:Y_i\le t) &\le\int_t^\infty\varphi(z)\mathbb{P}\Bigl(\min_i\eta_i\le\frac{t-rz}{s_r}\Bigr)dz\\ &\le\int_t^\infty\varphi(z)\Bigl(1-S_3\Bigl(\frac{t-rz}{s_r}\Bigr)\Bigr)dz =f_{3,r}(t), \end{align*}\] the last equality by (6.5). ∎
For \(t<0\) the monotonicity of \(g\) fails on part of the event \(\{Y_0\ge t\}\). This is why the plain sweep needs the general star comparison of Section 6. The median-switched layout uses outer frontiers only at \(t>0\) and inner frontiers only at \(t<0\), so it needs only the pointwise coupling above.
8.4 Level zero: the switch lemma
This subsection proves the switch lemma: if all incident correlations are at least \(r\), each vertex contributes, in expectation, at most \(\kappa(r)\) to the quantity \(L_0\) of (8.2), which controls the connector bags at threshold zero. Applied to the negated labels, the lemma gives the same bound for \(L_0'\). This is the same bound \(\kappa(r)\) as at nonzero thresholds (Proposition 8.8). For a vertex \(v\) of degree \(d\) with neighbors \(x_1,\dots,x_d\), the events \(v\in U\) and \(v\in D\cap W\) are \(\{Y_v\le0<\max_iY_{x_i}\}\) and \(\{d=3,\ Y_v>0\ge\max_iY_{x_i}\}\), so the following lemma bounds the contribution of \(v\) to \(\mathbb{E}L_0\).
Lemma 8.9 (switch lemma). Let \(r\in(0,1)\), let \(0\le d\le3\), and let \((Y_0,Y_1,\dots,Y_d)\) be a centered Gaussian vector with unit variances and \(\mathop{\mathrm{Corr}}(Y_0,Y_i)\ge r\) for \(1\le i\le d\). Then \[\mathbb{P}\bigl(Y_0\le0,\ \exists i:\ Y_i>0\bigr) +\mathbf{1}_{d=3}\mathbb{P}\bigl(Y_0>0,\ Y_i\le0\text{ for all }i\bigr)\le\kappa(r).\]
Idea of the proof.
By sign symmetry the second term equals \(\mathbb{P}(Y_0\le0<\min_iY_i)\), so the left side is \(\mathbb{E}\bigl[\mathbf{1}\{Y_0\le0\}\lceil N/2\rceil\bigr]\), where \(N\) is the number of neighbors with positive label. After conditioning on \(Y_0=z<0\) and lowering the incident correlations to \(r\) as in Proposition 8.8, it remains to show that, among all correlation matrices of three standard normal residuals, the probability that at least two of them exceed a level \(h>0\) is smallest for the equilateral matrix of \(U^*\) (Lemma 8.11). We prove this by a deformation. The smallest pairwise angles of the residual configuration are raised simultaneously (“water-filling”) until the angles sum to \(2\pi\). Plackett’s identity shows that the probability does not increase along the way. At the end the configuration is planar, and an exact formula and convexity finish the argument. The simplex theorem cannot be used here: the event “at least two exceed \(h\)” is not an orthant event, and the comonotone and countermonotone extremes pull in opposite directions.
We first record the tools: which angle triples are realizable, and Plackett’s identity in the form needed here; the planar formula is part of the proof of Lemma 8.11.
Lemma 8.10 (angles of three unit vectors). Let \(\alpha,\beta,\gamma\in[0,\pi]\) and let \(C\) be the symmetric \(3\times3\) matrix with unit diagonal and off-diagonal entries \(C_{23}=\cos\alpha\), \(C_{13}=\cos\beta\), \(C_{12}=\cos\gamma\). Then \[\begin{equation*} \tag{8.5} \det C=\bigl(\cos\alpha-\cos(\beta+\gamma)\bigr)\bigl(\cos(\beta-\gamma)-\cos\alpha\bigr). \end{equation*}\] Moreover, \(C\) is positive semidefinite if and only if \(\alpha\le\beta+\gamma\), \(\beta\le\alpha+\gamma\), \(\gamma\le\alpha+\beta\) and \(\alpha+\beta+\gamma\le2\pi\), and positive definite if and only if these four inequalities are strict.
Proof. The identity is a direct expansion. That the four inequalities suffice follows from the signs of the two factors in (8.5), and that they are necessary from the triangle inequality for angles between unit vectors.
Expanding, \(\det C=1-\cos^2\alpha-\cos^2\beta-\cos^2\gamma+2\cos\alpha\cos\beta\cos\gamma\). For the right side of (8.5), use \(\cos(\beta+\gamma)+\cos(\beta-\gamma)=2\cos\beta\cos\gamma\) and \(\cos(\beta+\gamma)\cos(\beta-\gamma)=\cos^2\beta\cos^2\gamma-\sin^2\beta\sin^2\gamma =\cos^2\beta+\cos^2\gamma-1\); then the product equals \(\cos\alpha\cdot2\cos\beta\cos\gamma-\cos^2\alpha-(\cos^2\beta+\cos^2\gamma-1)\), which is the expansion.
Assume the four inequalities and put \(m=\min(\beta+\gamma,2\pi-\beta-\gamma)\in[0,\pi]\), so that \(\cos(\beta+\gamma)=\cos m\) and \(|\beta-\gamma|\le\alpha\le m\). Since \(\cos\) is strictly decreasing on \([0,\pi]\), the first factor \(\cos\alpha-\cos m\) of (8.5) is nonnegative, and positive exactly when \(\alpha<m\), that is, when \(\alpha<\beta+\gamma\) and \(\alpha+\beta+\gamma<2\pi\); the second factor \(\cos|\beta-\gamma|-\cos\alpha\) is nonnegative, and positive exactly when \(|\beta-\gamma|<\alpha\), that is, when \(\beta<\alpha+\gamma\) and \(\gamma<\alpha+\beta\). So \(\det C\ge0\), with equality exactly when one of the four inequalities is an equality. The \(2\times2\) principal minors are \(\sin^2\ge0\) and the diagonal entries are \(1\), so all principal minors are nonnegative and \(C\) is positive semidefinite.
Conversely, let \(C\) be positive semidefinite. Then \(C\) is the Gram matrix of unit vectors \(v_1,v_2,v_3\) (for instance the columns of \(C^{1/2}\)), and \(\alpha,\beta,\gamma\) are the angles between them. The angle between unit vectors is a metric on the sphere, which gives the three triangle inequalities, and applying the triangle inequality to \(v_1\), \(-v_3\), \(v_2\) gives \(\gamma\le(\pi-\beta)+(\pi-\alpha)\), the fourth inequality.
Finally, a positive semidefinite matrix is positive definite exactly when its determinant is positive. By the two preceding paragraphs, \(C\) is therefore positive definite exactly when the four inequalities hold and \(\det C>0\), that is, when they hold strictly. ∎
The second tool is Plackett’s identity (Lemma 4.7), with \(\varphi_2(\cdot,\cdot;c)\) the density of a pair of standard normals with correlation \(c\in(-1,1)\). For positive definite \(3\times3\) correlation matrices \(C\), a level \(h\in\mathbb{R}\) and \(\eta\sim N(0,C)\), put \(P_{ij}(C)=\mathbb{P}_C(\eta_i>h,\eta_j>h)\) and \(P_{123}(C)=\mathbb{P}_C(\eta_1,\eta_2,\eta_3>h)\), as functions of the three off-diagonal entries. Let \(\{i,j,k\}=\{1,2,3\}\). The pair probabilities \(P_{ik}\) and \(P_{jk}\) depend only on the distributions of \((\eta_i,\eta_k)\) and \((\eta_j,\eta_k)\), hence not on \(C_{ij}\). Lemma 4.7, applied to the two coordinates \((\eta_i,\eta_j)\) and to all three coordinates, gives \[\begin{equation*} \tag{8.6} \frac{\partial P_{ij}}{\partial C_{ij}}=\varphi_2(h,h;C_{ij}),\qquad \frac{\partial P_{123}}{\partial C_{ij}} =\varphi_2(h,h;C_{ij})\mathbb{P}_C\bigl(\eta_k>h\bigm|\eta_i=\eta_j=h\bigr), \end{equation*}\] and both derivatives are continuous in \(C\). By (4.3), the conditional distribution of \(\eta_k\) given \(\eta_i=\eta_j=h\) is normal with mean \(h\,\frac{C_{ik}+C_{jk}}{1+C_{ij}}\) and positive variance.
For a correlation matrix \(C\) (positive semidefinite, unit diagonal) and \(h>0\) let \[\Pi_C(h)=\mathbb{P}_C\bigl(\text{at least two of }\eta_1,\eta_2,\eta_3\text{ exceed }h\bigr), \qquad\eta\sim N(0,C),\] and let \(C_{\mathrm{eq}}\) be the correlation matrix of \(U^*\) (all off-diagonal entries \(-\frac12\)). The map \(C\mapsto\Pi_C(h)\) is continuous on the set of all correlation matrices: if \(C_n\to C\), then \(N(0,C_n)\to N(0,C)\) weakly (by characteristic functions), and the boundary of the event is contained in the union of the hyperplanes \(\{x_i=h\}\), which are null under \(N(0,C)\) because every coordinate is standard normal.
Lemma 8.11 (two exceedances). For every \(3\times3\) correlation matrix \(C\) and every \(h>0\), \(\Pi_C(h)\ge\Pi_{C_{\mathrm{eq}}}(h)\).
Proof. We reduce to positive definite \(C\), deform \(C\) by raising its smallest angles until the angles sum to \(2\pi\), show that \(\Pi\) does not increase along this path, and compare the planar endpoint with \(C_{\mathrm{eq}}\).
Reduction to positive definite \(C\). For \(\xi\in(0,1]\), the matrix \((1-\xi)C+\xi I\) is a positive definite correlation matrix, and it tends to \(C\) as \(\xi\downarrow0\). By the continuity of \(\Pi\), it suffices to prove the claim for positive definite \(C\), which we now assume.
The water-filling path. Write \(C_{ij}=\cos\theta_{ij}\) with \(\theta_{ij}\in[0,\pi]\). By Lemma 8.10 and positive definiteness, the three triangle inequalities and the inequality \(\theta_{12}+\theta_{13}+\theta_{23}\le2\pi\) hold strictly. For \(s\ge0\) let \(\theta_{ij}(s)=\max(\theta_{ij},s)\) and \(\Sigma(s)=\sum_{i<j}\theta_{ij}(s)\). The function \(\Sigma\) is continuous and nondecreasing, \(\Sigma(0)<2\pi\) and \(\Sigma(\frac{2\pi}3)\ge2\pi\); let \(s^*\in(0,\frac{2\pi}3]\) be the smallest \(s\) with \(\Sigma(s)=2\pi\), and let \(C(s)\) be the matrix with off-diagonal entries \(\cos\theta_{ij}(s)\). On \([0,s^*]\) all angles lie in \([0,\pi]\).
For \(0\le s<s^*\), the matrix \(C(s)\) is positive definite. Indeed \(\Sigma(s)<2\pi\). For a triangle inequality \(\theta_{ij}(s)<\theta_{ik}(s)+\theta_{jk}(s)\): if \(\theta_{ij}(s)=\theta_{ij}\), it follows from \(\theta_{ij}<\theta_{ik}+\theta_{jk}\le\theta_{ik}(s)+\theta_{jk}(s)\); otherwise \(\theta_{ij}(s)=s>0\), and the right side is at least \(2s>s\). Lemma 8.10 gives positive definiteness. Thus \(C(s)\) moves within the positive definite matrices for \(s<s^*\), and reaches a matrix \(C(s^*)\) with angle sum exactly \(2\pi\), which is positive semidefinite by Lemma 8.10 (the non-strict inequalities persist by continuity).
Monotonicity along the path. The breakpoints \(\{\theta_{12},\theta_{13}, \theta_{23}\}\) divide \([0,s^*]\) into finitely many intervals. On the interior of each, the set of moving pairs, those with \(\theta_{ij}<s\), is fixed; the moving pairs have \(C_{ij}(s)=\cos s\), and the other entries are constant. By inclusion and exclusion, \[\Pi_C(h)=P_{12}(C)+P_{13}(C)+P_{23}(C)-2P_{123}(C),\] because the indicator of “at least two” equals the number of exceeding pairs minus twice the indicator of “all three” (check \(N=2\): \(1-0\); \(N=3\): \(3-2\)). By (8.6), for \(s<s^*\) and each pair \(\{i,j\}\) with third index \(k\), \[\frac{\partial\Pi_{C(s)}(h)}{\partial C_{ij}} =\varphi_2(h,h;C_{ij}(s))\Bigl(1-2\mathbb{P}_{C(s)}\bigl(\eta_k>h\bigm|\eta_i=\eta_j=h\bigr)\Bigr).\] For a moving pair, \(\theta_{ij}(s)=s\le\theta_{ik}(s),\theta_{jk}(s)\), so \(C_{ik}(s),C_{jk}(s)\le C_{ij}(s)\), and \(C_{ij}(s)=\cos s\ge-\frac12\). Since \(h>0\), the conditional mean satisfies \[h\,\frac{C_{ik}(s)+C_{jk}(s)}{1+C_{ij}(s)}\le h\,\frac{2C_{ij}(s)}{1+C_{ij}(s)}\le h,\] the last step because \(2c\le1+c\) for \(c\le1\) and \(1+c>0\). A normal distribution with mean at most \(h\) gives probability at most \(\frac12\) to \((h,\infty)\), so the partial derivative is nonnegative for every moving pair. By the chain rule, on the interior of each interval \[\frac{d}{ds}\Pi_{C(s)}(h)=\sum_{\text{moving }\{i,j\}} \frac{\partial\Pi_{C(s)}(h)}{\partial C_{ij}}\cdot(-\sin s)\le0 ,\] since \(\sin s\ge0\) for \(s\in[0,\pi]\). The function \(s\mapsto\Pi_{C(s)}(h)\) is continuous on \([0,s^*]\) (by the continuity of \(\Pi\)), so by the mean value theorem on each interval it is nonincreasing on \([0,s^*]\), and \(\Pi_C(h)\ge\Pi_{C(s^*)}(h)\).
The planar endpoint. Let \(v_1,v_2,v_3\) be unit vectors with Gram matrix \(C(s^*)\), and let \(\theta_{ij}=\theta_{ij}(s^*)\) from now on. By (8.5) with angle sum \(2\pi\), \(\cos(\beta+\gamma)=\cos(2\pi-\alpha)=\cos\alpha\), so \(\det C(s^*)=0\) and the vectors lie in a two-dimensional subspace; identify it with \(\mathbb{R}^2\). If \(\Gamma\) is a standard Gaussian vector in \(\mathbb{R}^2\), then \((\langle v_i,\Gamma\rangle)_i\sim N(0,C(s^*))\). Order the directions of the \(v_i\) around the circle and let \(g_1,g_2,g_3\ge0\) be the three circular gaps between consecutive directions, \(g_1+g_2+g_3=2\pi\), labeled so that \(g_k\) is the gap between the directions of \(v_i\) and \(v_j\) that does not contain the direction of \(v_k\). The angle between \(v_i\) and \(v_j\) is \(\theta_{ij}=\min(g_k,2\pi-g_k)\le g_k\); since the angles sum to \(2\pi=\sum_kg_k\), equality holds throughout, so \(g_k=\theta_{ij}\le\pi\) for every \(k\).
Write \(\Gamma=\varrho(\cos\omega,\sin\omega)\) with \(\varrho\ge0\) and \(\omega\) uniform on the circle, independent of \(\varrho\). Given \(\varrho\), the projection on \(v_i\) exceeds \(h\) if and only if \(\varrho>h\) and \(\omega\) lies within angular distance \(\lambda=\arccos(h/\varrho)\in(0,\frac\pi2)\) of the direction of \(v_i\). An arc of half-width \(\lambda\) around each direction gives three arcs of length \(2\lambda<\pi\). No point lies in all three arcs: otherwise the three directions would lie in an arc of length \(2\lambda<\pi\), and the complementary gap would exceed \(\pi\). Two arcs around directions separated by the gap \(g_k\) overlap in an arc of length \((2\lambda-g_k)_+\) on that side, and not at all on the other side, whose length is \(2\pi-g_k\ge\pi>2\lambda\). Therefore \[\Pi_{C(s^*)}(h)=\mathbb{E}\Bigl[\mathbf{1}\{\varrho>h\}\,\frac1{2\pi} \sum_{k=1}^3\bigl(2\lambda(\varrho)-g_k\bigr)_+\Bigr].\] The function \(g\mapsto(2\lambda-g)_+\) is convex, so by Jensen’s inequality \(\sum_k(2\lambda-g_k)_+\ge3(2\lambda-\frac{2\pi}3)_+\), which is the value of the sum for the equal gaps \(\frac{2\pi}3\) of the configuration of \(U^*\). The same formula applies to \(C_{\mathrm{eq}}\), so \(\Pi_{C(s^*)}(h)\ge\Pi_{C_{\mathrm{eq}}}(h)\). Together with the monotonicity, \(\Pi_C(h)\ge\Pi_{C_{\mathrm{eq}}}(h)\). ∎
Proof of Lemma 8.9. Reduction to \(d=3\). If \(d<3\), the second term is absent. Add coordinates \(Y_j=rY_0+s_r\eta_j\) for \(d<j\le3\), with fresh independent standard normal \(\eta_j\). The extended vector satisfies the hypotheses with \(d=3\), its first event contains the original one, and its second term is nonnegative; so it suffices to treat \(d=3\).
The functional. Let \(d=3\) and \(N=\#\{i:Y_i>0\}\). By sign symmetry, \(\mathbb{P}(Y_0>0,\ Y_i\le0\ \forall i)=\mathbb{P}(Y_0<0,\ Y_i\ge0\ \forall i) =\mathbb{P}(Y_0\le0,\ N=3)\), the last step because the events differ by null events. Since \(\lceil N/2\rceil=\mathbf{1}\{N\ge1\}+\mathbf{1}\{N=3\}\) for \(N\in\{0,1,2,3\}\), the left side of the lemma equals \[\begin{equation*} \tag{8.7} \Psi=\mathbb{E}\bigl[\mathbf{1}\{Y_0\le0\}\lceil N/2\rceil\bigr]. \end{equation*}\] We shall also use \(\lceil N/2\rceil=N-\mathbf{1}\{N\ge2\}\), valid for the same values.
Coupling. Put \(a_i=\mathop{\mathrm{Corr}}(Y_0,Y_i)\ge r\) and \(s_i=\sqrt{1-a_i^2}\). For \(s_i>0\) let \(\eta_i=(Y_i-a_iY_0)/s_i\), and for \(s_i=0\) let \(\eta_i\) be an auxiliary standard normal variable independent of everything else. Then \(\eta=(\eta_1,\eta_2,\eta_3)\) is a centered Gaussian vector with unit variances, independent of \(Y_0\); let \(C\) be its correlation matrix. On \(\{Y_0<0\}\) (the event \(Y_0=0\) is null): if \(s_i=0\), then \(Y_i=Y_0<0\) with probability \(1\); if \(s_i>0\), then \(Y_i>0\) if and only if \(\eta_i>|Y_0|a_i/s_i\). The function \(a\mapsto a/\sqrt{1-a^2}\) is increasing on \((0,1)\), so \(|Y_0|a_i/s_i\ge|Y_0|r/s_r\). Hence, with probability \(1\) on \(\{Y_0<0\}\), \[\begin{equation*} \tag{8.8} N\le N_{h}:=\#\{i:\eta_i>h\},\qquad h=h(Y_0)=\frac{r|Y_0|}{s_r}>0 . \end{equation*}\] Since \(n\mapsto\lceil n/2\rceil\) is nondecreasing and \(\lceil n/2\rceil=n-\mathbf{1}\{n\ge2\}\), independence and Fubini give \[\begin{equation*} \tag{8.9} \Psi\le\int_{-\infty}^0\varphi(z)\,\mathbb{E}\lceil N_{h(z)}/2\rceil\,dz =\int_{-\infty}^0\varphi(z)\Bigl(3\Phi\bigl(-h(z)\bigr)-\Pi_C\bigl(h(z)\bigr)\Bigr)dz, \qquad h(z)=\frac{r|z|}{s_r}. \end{equation*}\]
Comparison and the ideal value. By Lemma 8.11, \(\Pi_C(h)\ge\Pi_{C_{\mathrm{eq}}}(h)\) for every \(h>0\), so \[\begin{equation*} \tag{8.10} \Psi\le\int_{-\infty}^0\varphi(z)\Bigl(3\Phi\bigl(-h(z)\bigr)-\Pi_{C_{\mathrm{eq}}}\bigl(h(z)\bigr)\Bigr)dz . \end{equation*}\] For the ideal star \((Y^*_0,\dots,Y^*_3)\) the coupling is an identity: its residuals are \(U^*\), its incident correlations are \(r\), and \(Y^*_i>0\) if and only if \(U^*_i>h(Y^*_0)\) on \(\{Y^*_0<0\}\). So the right side equals \(\Psi\) for the ideal star, namely \[\mathbb{P}(Y^*_0\le0<\max_iY^*_i)+\mathbb{P}(Y^*_0\le0<\min_iY^*_i).\] The second probability is \(0\): by (8.4), \(\min_iY^*_i>0\) forces \(Y^*_0>0\). By sign symmetry of the ideal star and the absence of ties, the first probability equals \(\mathbb{P}(Y^*_0\ge0,\ \min_iY^*_i\le0)=f_{3,r}(0)\), which is \(\kappa(r)\) by Lemma 8.6. Hence \(\Psi\le\kappa(r)\). ∎
8.5 Concentration and the proof of Theorem 8.1
We can now bound, at each fixed threshold, the expected sizes of the inner frontiers below zero and of the outer frontiers above zero, and the expected values of \(L_0\) and \(L_0'\) at zero. To control all thresholds at once we use a finite grid of thresholds, the concentration of the finitely many grid counts (Lemma 7.9), and the deterministic interpolation of Lemma 7.8 between grid points, both for inner and for outer frontiers.
Proof of Theorem 8.1. We prove the following uniform statement: for every \(\varepsilon>0\) there is \(N(\varepsilon)\) such that every graph \(G\) with \(\Delta(G)\le3\) and \(n\ge N(\varepsilon)\) vertices satisfies \(\mathop{\mathrm{pw}}(G)\le(c_{3}+\varepsilon)n\). This implies Theorem 8.1: let \(\rho(n)\) be the maximum of \(\max(0,\mathop{\mathrm{pw}}(G)-c_{3}n)\) over all graphs \(G\) with \(\Delta(G)\le3\) on \(n\) vertices (a finite set up to isomorphism); then \(\rho(n)\le\varepsilon n\) for \(n\ge N(\varepsilon)\), so \(\rho(n)=o(n)\), and \(\mathop{\mathrm{pw}}(G)\le c_{3}n+\rho(n)\) for every such \(G\).
For fixed \(\varepsilon\), we choose the radius \(R\) and a grid of thresholds, bound the means of finitely many counts, fix a realization in which every count is close to its mean, and check the three conditions of Lemma 8.4.
Fix \(\varepsilon>0\). Since \(\kappa\) is continuous on \((0,1)\) and \(r_R\to r_*\) as \(R\to\infty\), choose an integer \(R\ge2\) with \(\kappa(r_R)\le c_{3}+\frac\varepsilon 3\). Choose an integer \(K_0\ge1\) with \(\varphi(0)/K_0\le\frac\varepsilon 3\), and use the grid \(\tau_j=-2+j/K_0\) for \(0\le j\le K:=4K_0\). It contains \(\tau_{2K_0}=0\) and \(\tau_K=2\). Both \(R\) and \(K_0\) depend only on \(\varepsilon\). Let \(G\) have \(\Delta(G)\le3\) and \(n\) vertices, and let \(Y\) be the labels at radius \(R\).
Counts. Consider the following \(8K_0+4\) random variables, each a sum over \(v\in V(G)\) of indicator variables:
\(|\partial^{-}S_{\tau_j}|\) for \(0\le j<2K_0\) (thresholds \(\tau_j<0\));
\(|\partial^{+}S_{\tau_j}|\) for \(2K_0<j\le4K_0\) (thresholds \(\tau_j>0\));
\(L_0\) and \(L_0'\) from (8.2), with indicators \(\mathbf{1}\{v\in U\}+\mathbf{1}\{v\in D\cap W\}\) and \(\mathbf{1}\{v\in W\}+\mathbf{1}\{v\in D\cap U\}\) (each at most \(1\), as the two events are disjoint);
the window counts \(M_j:=\#\{v:\tau_j<Y_v\le\tau_{j+1}\}\) for \(0\le j<4K_0\) (the counts \(N_j\) of Lemma 7.8); and
\(\#\{v:Y_v\le-2\}\) and \(\#\{v:Y_v>2\}\).
The indicator for \(v\) in each count is determined by the degree of \(v\) and the labels on \(N[v]\), hence by (L3) by \((Z_w)_{w\in B_{R+1}(v)}\).
Means. Fix \(v\) with neighbors \(x_1,\dots,x_d\), \(d\le3\). By (L1), \((Y_v,Y_{x_1},\dots,Y_{x_d})\) and its negative are centered Gaussian vectors with unit variances and incident correlations at least \(r_R\). The events \(v\in\partial^{+}S_\tau\) for \(\tau>0\) and \(v\in\partial^{-}S_\tau\) for \(\tau<0\) are contained in the events of Proposition 8.8 for this vector at \(\tau\) and for its negative at \(-\tau\). Up to the null events \(\{Y_x=0\}\) with \(x\in N[v]\), the two events in the indicator of \(L_0\) are the two events of Lemma 8.9 for this vector, and those of \(L_0'\) are the same events for its negative. So each of these indicators has mean at most \(\kappa(r_R)\). Since moreover \(\mathbb{P}(\tau_j<Y_v\le\tau_{j+1})\le\varphi(0)/K_0\) and \(\mathbb{P}(Y_v\le-2)=\mathbb{P}(Y_v>2)=\Phi(-2)<0.023\), summing over \(v\) shows that every inner or outer grid count and both \(L_0\) and \(L_0'\) have mean at most \(\kappa(r_R)n\), every \(M_j\) has mean at most \(\varphi(0)n/K_0\), and both tail counts have mean at most \(0.023n\).
Concentration. Choose \(N(\varepsilon)\) so large that, for \(n\ge N(\varepsilon)\), \[(8K_0+4)\,9^{R+1}<2n^{1/2},\qquad 2n^{3/4}\le\tfrac\varepsilon 3n,\qquad n^{3/4}+1\le\tfrac\varepsilon 3n,\qquad 0.023n+n^{3/4}\le c_{3}n;\] the last condition is possible because \(0.023<c_{3}\). All of these conditions depend only on \(\varepsilon\). Let \(n\ge N(\varepsilon)\). The first condition is the hypothesis of Lemma 7.9 for the \(8K_0+4\) counts, with \(\Delta=3\), \(\varrho=R+1\) and \(\lambda=n^{3/4}\), so some realization of \(Z\) has pairwise distinct labels and every count within \(n^{3/4}\) of its mean. Fix it and let \(y=Y\) for this realization.
Bounds at every threshold. Let \(w=(c_{3}+\varepsilon)n\). For \(t\in[-2,0)\), let \(j\) be such that \(t\in[\tau_j,\tau_{j+1})\); then \(j<2K_0\), so \(\tau_j<0\), and Lemma 7.8(i) gives \[|\partial^{-}S_t|\le|\partial^{-}S_{\tau_j}|+M_j\le\kappa(r_R)n+\frac{\varphi(0)}{K_0}n+2n^{3/4} \le\bigl(c_{3}+\tfrac{2\varepsilon}3\bigr)n+2n^{3/4}\le w .\] For \(t\in(0,2)\), let \(j\) be such that \(t\in[\tau_j,\tau_{j+1})\); then \(j\ge2K_0\), so \(\tau_{j+1}>0\), and the same computation with the outer count at \(\tau_{j+1}\) gives \(|\partial^{+}S_t|\le w\). For \(t<-2\) and \(t\ge2\), Lemma 7.8(ii),(iii) give (inner, respectively outer) frontiers of size at most \(0.023n+n^{3/4}\le c_{3}n\le w\). Finally \(\max(L_0,L_0')+1\le\kappa(r_R)n+n^{3/4}+1\le(c_{3}+\frac{2\varepsilon}3)n\le w\).
Conclusion. The labeling \(y\) is injective, and conditions (i)–(iii) of Lemma 8.4 hold with \(w=(c_{3}+\varepsilon)n\). Hence \(\mathop{\mathrm{pw}}(G)\le(c_{3}+\varepsilon)n\) for every graph \(G\) with \(\Delta(G)\le3\) and \(n\ge N(\varepsilon)\). ∎
Every path decomposition is a tree decomposition, so the same bound holds for treewidth. The proof is existential; Section 10 turns it into an algorithm.