6 Star bounds
A vertex \(v\) lies in the outer frontier \(\partial^{+}S_\tau\) of the sweep exactly when \(Y_v>\tau\) and some neighbor \(u\) of \(v\) has \(Y_u\le\tau\). This section bounds the probability of this event from above in terms of lower bounds on the correlations between \(Y_v\) and the labels \(Y_u\) of the neighbors alone, which is all that the labels of Section 5 provide. These bounds for a single vertex are the input of the plain sweep (Section 7), of the cubic sweep (Section 8) and of the certificate (Appendix A.2). The technical overview explains the route (Section 2.3).
Section 6.1 defines stars and bounds the frontier probability by the center bound (Lemma 6.2), an integral over the label of the center whose integrand involves the infimum \(P_{\min}\) of an orthant probability over all correlation matrices. Section 6.2 shows that for equal thresholds and three to five coordinates this infimum is attained by the regular simplex vector (the simplex theorem, Lemma 6.5), and Section 6.3 defines the ideal stars and encloses \(F_3\) and \(F_4\) (Definition 6.7 and Proposition 6.9). The bounds on \(P_{\min}\) for unequal thresholds (Lemmas A.1 and A.2), the simplex recursion (Lemma A.3) and the proof of Proposition 6.9 are in Appendices A.2.1 and A.2.2.
The notation and conventions of Section 4.4 are in force; in particular \(s_r=\sqrt{1-r^2}\). All coordinates below are standard normal, so strict and weak inequalities between a coordinate and a constant may be exchanged.
6.1 Stars and the reduction to the center
Definition 6.1 (stars). Let \(d\ge1\) and \(r=(r_1,\dots,r_d)\in(0,1)^d\). A \(d\)-star with lower bounds \(r\) is a centered Gaussian vector \((Y_0,Y_1,\dots,Y_d)\) with \(\mathop{\mathrm{Var}}Y_k=1\) for \(0\le k\le d\) and \(\mathop{\mathrm{Corr}}(Y_0,Y_i)\ge r_i\) for \(1\le i\le d\). The coordinate \(Y_0\) is the center. For a threshold \(\tau\in\mathbb{R}\), the frontier event of the star is \(\{Y_0>\tau,\ \min_{1\le i\le d}Y_i\le\tau\}\).
No assumption is made on the correlations \(\mathop{\mathrm{Corr}}(Y_i,Y_j)\) between two non-central coordinates; they may be negative, and the covariance matrix may be singular. In the sweep, \(Y_0\) is the label of a vertex and \(Y_1,\dots,Y_d\) are the labels of its neighbors; the frontier event is the event that the vertex lies in \(\partial^{+}S_\tau\).
Since \(\{Y_0>\tau\}\) is the disjoint union of the frontier event and the event \(\{Y_k>\tau\ \text{for}\ 0\le k\le d\}\), \[\begin{equation*} \tag{6.1} \mathbb{P}\bigl(Y_0>\tau,\ \min_iY_i\le\tau\bigr) =\Phi(-\tau)-\mathbb{P}\bigl(Y_k>\tau\ \text{for}\ 0\le k\le d\bigr). \end{equation*}\] So an upper bound on the frontier probability is the same as a lower bound on the probability that the whole star lies above \(\tau\). We now fix notation for the quantities that the lower bound will involve. For lower bounds \(r\in(0,1)^d\), a threshold \(\tau\) and \(z\in\mathbb{R}\), put \[s_i=\sqrt{1-r_i^2},\qquad a_i(z)=a_i(z;\tau,r)=\frac{\tau-r_iz}{s_i}\qquad(1\le i\le d).\] Each \(a_i(z)\) is strictly decreasing in \(z\), because \(r_i>0\). For \(a\in\mathbb{R}^d\) let \[P_{\min}(a)=P^{(d)}_{\min}(a):=\inf\Bigl\{\mathbb{P}\bigl(U_i>a_i\ \text{for}\ 1\le i\le d\bigr)\Bigr\},\] where the infimum is over all centered Gaussian vectors \(U=(U_1,\dots,U_d)\) with unit variances (equivalently, over all \(d\times d\) correlation matrices, singular ones included). Finally, the center bound is \[\begin{equation*} \tag{6.2} C_d(\tau;r):=\Phi(-\tau)-\int_\tau^\infty\varphi(z)\,P_{\min}\bigl(a(z;\tau,r)\bigr)\,dz . \end{equation*}\] By Lemma 6.3(a) below, \(P_{\min}\) is continuous, so the integrand is continuous in \(z\) and the integral is well defined.
Lemma 6.2 (reduction to the center). Let \((Y_0,\dots,Y_d)\) be a \(d\)-star with lower bounds \(r\in(0,1)^d\), and let \(\tau\in\mathbb{R}\). There is a centered Gaussian vector \(U=(U_1,\dots,U_d)\) with unit variances such that \[\begin{equation*} \tag{6.3} \mathbb{P}\bigl(Y_k>\tau\ \text{for}\ 0\le k\le d\bigr)\ \ge\ \int_\tau^\infty\varphi(z)\,\mathbb{P}\bigl(U_i>a_i(z;\tau,r)\ \text{for}\ 1\le i\le d\bigr)\,dz . \end{equation*}\] Consequently \[\mathbb{P}\bigl(Y_0>\tau,\ \min_{1\le i\le d}Y_i\le\tau\bigr)\le C_d(\tau;r).\]
The proof has three steps. A coupling replaces each neighbor label by one whose correlation with the center equals its lower bound; this lowers the correlations between neighbors as well. By Slepian’s inequality, the probability that the whole star lies above \(\tau\) can then only decrease. Conditioning on the center finally gives (6.3). A separate lower bound for each neighbor is needed for graphs with several degrees, where the edges at one vertex have different correlation bounds.
Proof. Put \(Z=Y_0\) and \(\rho_i=\mathop{\mathrm{Corr}}(Y_0,Y_i)\), so \(0<r_i\le\rho_i\le1\).
Coupling. Take independent standard normal variables \(\xi_1,\dots,\xi_d\), independent of \(Y\), and put \[Y'_0=Z,\qquad Y'_i=Y_i-(\rho_i-r_i)\,Z+\sqrt{\rho_i^2-r_i^2}\;\xi_i\qquad(1\le i\le d).\] The square root is real because \(\rho_i\ge r_i>0\). The vector \(Y'\) is centered Gaussian. A direct computation gives \[\begin{align*} \mathop{\mathrm{Var}}Y'_i&=1-2(\rho_i-r_i)\rho_i+(\rho_i-r_i)^2+(\rho_i^2-r_i^2)=1,\\ \mathop{\mathrm{Cov}}(Y'_0,Y'_i)&=\rho_i-(\rho_i-r_i)=r_i\le\rho_i=\mathop{\mathrm{Cov}}(Y_0,Y_i),\\ \mathop{\mathrm{Cov}}(Y'_i,Y'_j)&=\mathop{\mathrm{Cov}}(Y_i,Y_j)-\rho_i\rho_j+r_ir_j\le\mathop{\mathrm{Cov}}(Y_i,Y_j)\qquad(i\ne j), \end{align*}\] the last inequality because \(0<r_i\le\rho_i\) and \(0<r_j\le\rho_j\). The correlations \(\mathop{\mathrm{Cov}}(Y_i,Y_j)\) between neighbors, which may be negative, enter only through the common term.
Comparison. The vectors \(Y\) and \(Y'\) have the same variances, and every off-diagonal covariance of \(Y\) is at least the corresponding one of \(Y'\). By Slepian’s inequality (Lemma 4.8; singular covariance matrices are allowed), \[\mathbb{P}(Y_k>\tau\ \forall k)\ \ge\ \mathbb{P}(Y'_k>\tau\ \forall k).\]
Conditioning on the center. Put \(U_i=(Y'_i-r_iZ)/s_i\). Since \(Y'_i-r_iZ=Y_i-\rho_iZ+\sqrt{\rho_i^2-r_i^2}\,\xi_i\) has variance \((1-\rho_i^2)+(\rho_i^2-r_i^2)=s_i^2\) and is uncorrelated with \(Z\), the vector \(U=(U_1,\dots,U_d)\) is centered Gaussian with unit variances, \((Z,U)\) is jointly Gaussian, and \(U\) is independent of \(Z\). As \(Y'_i=r_iZ+s_iU_i\), Fubini’s theorem gives \[\mathbb{P}(Y'_k>\tau\ \forall k)=\int_\tau^\infty\varphi(z)\, \mathbb{P}\bigl(r_iz+s_iU_i>\tau\ \forall i\bigr)\,dz =\int_\tau^\infty\varphi(z)\,\mathbb{P}\bigl(U_i>a_i(z;\tau,r)\ \forall i\bigr)\,dz .\] This proves (6.3). The integrand is at least \(\varphi(z)P_{\min}(a(z;\tau,r))\) by the definition of \(P_{\min}\), and the second claim follows from (6.1). ∎
The center bound depends continuously on the lower bounds, with an explicit modulus. The labels of Section 5 give the lower bounds only up to a factor \(1-\varepsilon_R\) (Lemma 5.5), and the following estimate is how this factor is removed in the limit \(R\to\infty\).
Lemma 6.3 (continuity of the center bound). Let \(d\ge1\) and write \(P_{\min}=P^{(d)}_{\min}\). Then:
(a) \(P_{\min}\) is nonincreasing in each coordinate, and \(|P_{\min}(a)-P_{\min}(a')|\le\varphi(0)\sum_{i=1}^d|a_i-a'_i|\) for all \(a,a'\in\mathbb{R}^d\).
(b) Let \(\bar r\in(0,1)\), let \(r,r'\in(0,\bar r]^d\) with \(|r_i-r'_i|\le\varepsilon\) for all \(i\), and let \(\tau\in\mathbb{R}\). Then \[|C_d(\tau;r)-C_d(\tau;r')|\le d\,\varphi(0)\,(1-\bar r^2)^{-3/2} \Bigl(|\tau|+\sqrt{2/\pi}\Bigr)\,\varepsilon.\] In particular, if \(d\le5\), \(\bar r=r_{33}=\frac{2\sqrt2}{3}\) and \(|\tau|\le3\), then \(|C_d(\tau;r)-C_d(\tau;r')|\le205\,\varepsilon\).
Proof. (a) Fix a centered Gaussian vector \(U\) with unit variances. Raising a threshold shrinks the event \(\{U_i>a_i\ \forall i\}\), so its probability is nonincreasing in each \(a_i\); and the two events for \(a\) and \(a'\) differ only on \(\bigcup_i\{U_i\ \text{lies between}\ a_i\ \text{and}\ a'_i\}\), which has probability at most \(\sum_i|\Phi(a_i)-\Phi(a'_i)|\le\varphi(0)\sum_i|a_i-a'_i|\). An infimum of functions that are all nonincreasing in each coordinate and all satisfy the same Lipschitz bound has the same two properties.
(b) For \(\rho\in(0,\bar r]\) and fixed \(\tau,z\), the map \(\rho\mapsto(\tau-\rho z)/\sqrt{1-\rho^2}\) has derivative \((\rho\tau-z)/(1-\rho^2)^{3/2}\), whose absolute value is at most \((1-\bar r^2)^{-3/2}(|\tau|+|z|)\). By the mean value theorem, \(|a_i(z;\tau,r)-a_i(z;\tau,r')|\le(1-\bar r^2)^{-3/2}(|\tau|+|z|)\,\varepsilon\) for each \(i\). By part (a), \[\begin{align*} |C_d(\tau;r)-C_d(\tau;r')| &\le\int_\tau^\infty\varphi(z)\,d\,\varphi(0)\,(1-\bar r^2)^{-3/2}(|\tau|+|z|)\,\varepsilon\,dz\\ &\le d\,\varphi(0)\,(1-\bar r^2)^{-3/2}\bigl(|\tau|+\mathbb{E}|N|\bigr)\varepsilon, \end{align*}\] where \(N\) is standard normal and \(\mathbb{E}|N|=\sqrt{2/\pi}\). For \(\bar r=2\sqrt2/3\) we have \(1-\bar r^2=\frac19\) and \((1-\bar r^2)^{-3/2}=27\). With \(d\le5\) and \(|\tau|\le3\) the constant is at most \(5\cdot0.39895\cdot27\cdot(3+0.79789)<204.6\). ∎
6.2 The simplex theorem
The infimum \(P_{\min}\) in the center bound is over all correlation matrices. For equal thresholds it is attained by the most “spread out” matrix, that of the regular simplex. This subsection defines the regular simplex vector and states this claim for three to five coordinates (Lemma 6.5), as cases of a theorem of Mulgund (Mulgund 2026).
For \(d\ge2\), let \(w_1,\dots,w_d\in\mathbb{R}^{d-1}\) be unit vectors with \(\langle w_i,w_j\rangle=-\frac1{d-1}\) for \(i\ne j\) (the vertices of a regular simplex inscribed in the unit sphere \(S^{d-2}\)), so that \(\sum_iw_i=0\). Let \(G\) be a standard Gaussian vector in \(\mathbb{R}^{d-1}\). The regular simplex vector is \(U^*=(U^*_1,\dots,U^*_d)\) with \(U^*_i=\langle w_i,G\rangle\). It is centered, with unit variances and all pairwise correlations \(-\frac1{d-1}\), and \(\sum_iU^*_i=\langle\sum_iw_i,G\rangle=0\). Its orthant function and the reflection of the latter are \[S_d(a):=\mathbb{P}\bigl(U^*_i>a\ \text{for}\ 1\le i\le d\bigr),\qquad T_d(h):=S_d(-h)=\mathbb{P}\bigl(\max_iU^*_i<h\bigr)\qquad(a,h\in\mathbb{R}),\] the last identity because \(-U^*\) has the same distribution as \(U^*\). Since the coordinates of \(U^*\) sum to zero, they cannot all exceed a number \(a\ge0\); hence \[\begin{equation*} \tag{6.4} S_d(a)=0\quad\text{for}\ a\ge0,\qquad T_d(h)=0\quad\text{for}\ h\le0 . \end{equation*}\]
The bound of Lemma A.2 for three unequal thresholds starts by lowering all correlations until the correlation matrix is singular.
Lemma 6.4 (rank reduction). Let \(d\ge2\) and let \(C\) be a nonsingular \(d\times d\) correlation matrix. There is a singular \(d\times d\) correlation matrix \(C'\) such that, for \(U\sim N(0,C)\) and \(U'\sim N(0,C')\), \(\mathbb{P}(U_i>a_i\ \forall i)\ge\mathbb{P}(U'_i>a_i\ \forall i)\) for every \(a\in\mathbb{R}^d\).
Proof. Let \(J\) be the all-ones matrix and \(C_t=C-t(J-I)\) for \(t\ge0\); it has unit diagonal and its off-diagonal entries are those of \(C\) minus \(t\). The set \(\{t\ge0:C_t\succeq0\}\) is closed and convex, contains a neighborhood of \(0\) in \([0,\infty)\) (as \(C\succ0\)), and is bounded, because \(\mathbf 1^{\mathsf T}C_t\mathbf 1=\mathbf 1^{\mathsf T}C\mathbf 1-d(d-1)t\). So it is an interval \([0,t^*]\) with \(t^*>0\). The matrix \(C':=C_{t^*}\) is positive semidefinite, and it is singular by the maximality of \(t^*\): the least eigenvalue of \(C_t\) is continuous in \(t\), nonnegative at \(t^*\) and negative for \(t>t^*\). The off-diagonal entries of \(C'\) are at most those of \(C\), so Slepian’s inequality (Lemma 4.8) gives the claim. ∎
Lemma 6.5 (simplex theorem for \(d\le5\)). Let \(d\in\{3,4,5\}\) and let \(U=(U_1,\dots,U_d)\) be a centered Gaussian vector with unit variances. Then \(\mathbb{P}(U_i>a\ \text{for}\ 1\le i\le d)\ge S_d(a)\) for every \(a\in\mathbb{R}\); consequently \(P^{(d)}_{\min}(a,\dots,a)=S_d(a)\).
Proof. The second claim follows from the first, since \(U^*\) itself is admissible in the infimum.
Mulgund (Mulgund 2026 Theorem 1.1) proves: for every \(n\ge2\), every \(n\times n\) correlation matrix \(\Gamma\) (positive semidefinite with unit diagonal, singular matrices included) and every \(t\in\mathbb{R}\), \[\mathbb{P}_{X\sim N(0,\Sigma_n)}\bigl(\max_iX_i\le t\bigr)\le\mathbb{P}_{X\sim N(0,\Gamma)}\bigl(\max_iX_i\le t\bigr),\] where \(\Sigma_n\) has unit diagonal and off-diagonal entries \(-\frac1{n-1}\). Apply this with \(n=d\), \(X=-U\) (whose correlation matrix is that of \(U\)) and \(t=-a\). Since \(-U^*\) has the distribution \(N(0,\Sigma_d)\), this gives \(\mathbb{P}(U_i\ge a\ \forall i)\ge \mathbb{P}(U^*_i\ge a\ \forall i)\), and since every coordinate has a continuous distribution, the weak inequalities may be replaced by strict ones. ∎
Remark 6.6 (status of the simplex theorem). For \(d=3\) the inequality also has an elementary proof: condition on one coordinate, apply the Fréchet bound \(\mathbb{P}(A\cap B)\ge\mathbb{P}A+\mathbb{P}B-1\) to the other two, note that the bound is attained by a planar configuration with the same conditional marginals, and compare planar configurations by the convexity of the probability in the arcs between the directions. For \(d=4\) the inequality also follows from the four-cap theorem of L. Fejes Tóth (Fejes Tóth 1950) ((Böröczky 2004 Theorem 5.6.2)) by slicing the Gaussian measure along spheres centered at the origin, after lowering the correlations until the correlation matrix is singular (Lemma 6.4); see (Balitskiy, Karasev, and Tsigler 2017, secs. 2–3). For \(d=5\) no other proof is known to us. The paper (Mulgund 2026) is a preprint (version 2), whose author discloses substantial AI assistance. The three-variable case enters the proof of Theorem 8.1 through Proposition 8.8, the four-variable case only through vertices of degree at least \(4\), and the five-variable case only through the triples \(\mathsf{P},\mathsf{R},\mathsf{S}\) of Theorem 7.2, and through \(\mathsf{S}\) also Theorem 1.3, Corollary 1.4 and the results derived from them.
6.3 Ideal stars and the constants \(F_3\) and \(F_4\)
When all lower bounds of a star are equal, the center bound is the frontier probability of an explicit star, and this star is the worst case at every threshold.
Definition 6.7 (ideal stars). Let \(d\in\{3,4,5\}\) and \(r\in(0,1)\). Let \(Z\) be standard normal and \(U^*\) the regular simplex vector in \(d\) variables, independent of \(Z\). The ideal \(d\)-star at correlation \(r\) is \[Y^*_0=Z,\qquad Y^*_i=rZ+s_rU^*_i\qquad(1\le i\le d).\] Its ideal star function is \[f_{d,r}(\tau):=\mathbb{P}\bigl(Y^*_0>\tau,\ \min_iY^*_i\le\tau\bigr)\qquad(\tau\in\mathbb{R}).\] Put \[F_3:=\sup_{\tau\in\mathbb{R}}f_{3,r_{33}}(\tau),\qquad F_4:=\sup_{\tau\in\mathbb{R}}f_{4,r_{44}}(\tau), \qquad r_{33}=\tfrac{2\sqrt2}3,\quad r_{44}=\tfrac{\sqrt3}2 .\]
The constants \(F_3\) and \(F_4\) are those of Theorems 7.1 and 7.2. The ideal star is a \(d\)-star with all lower bounds equal to \(r\): its incident correlations are \(r\) and its other correlations are \(r^2-s_r^2/(d-1)=(dr^2-1)/(d-1)\). Since \(U^*\) is independent of \(Z\) and \(Y^*_i>\tau\) means \(U^*_i>(\tau-rZ)/s_r\), Fubini’s theorem and (6.1) give \[\begin{equation*} \tag{6.5} f_{d,r}(\tau)=\Phi(-\tau)-\int_\tau^\infty\varphi(z)\,S_d\Bigl(\frac{\tau-rz}{s_r}\Bigr)dz . \end{equation*}\] Comparing this with (6.2) and using \(P_{\min}(a,\dots,a)=S_d(a)\) (Lemma 6.5), \[\begin{equation*} \tag{6.6} C_d\bigl(\tau;(r,\dots,r)\bigr)=f_{d,r}(\tau)\qquad(d\in\{3,4,5\},\ r\in(0,1),\ \tau\in\mathbb{R}). \end{equation*}\] In the cubic case, \(r_{33}=r_*=\frac{2\sqrt2}3\) is the edge correlation bound \(r_*(1-\frac1R)\) of the geometric labels in the limit \(R\to\infty\) (Lemma 5.4), and \(f_{3,r_*}(0)\) is the constant \(c_{3}\) of Theorem 8.1 (Lemma 8.6).
Corollary 6.8 (ideal star bound). Let \(d\in\{3,4,5\}\), \(r\in(0,1)\) and \(0\le k\le d\), and let \((Y_0,Y_1,\dots,Y_k)\) be a centered Gaussian vector with unit variances and \(\mathop{\mathrm{Corr}}(Y_0,Y_i)\ge r\) for \(1\le i\le k\). Then for every \(\tau\in\mathbb{R}\), \[\mathbb{P}\bigl(Y_0>\tau,\ Y_i\le\tau\ \text{for some}\ 1\le i\le k\bigr)\le f_{d,r}(\tau).\]
Proof. If \(k<d\), add coordinates \(Y_j=rY_0+s_r\eta_j\) for \(k<j\le d\), with fresh independent standard normal \(\eta_j\). The extended vector is a \(d\)-star with lower bounds \((r,\dots,r)\), and the event can only grow. Now apply Lemma 6.2 and (6.6). ∎
In particular \(f_{d,r}\le f_{d,r'}\) pointwise whenever \(0<r'\le r<1\): apply Corollary 6.8 with lower bound \(r'\) to the ideal \(d\)-star at correlation \(r\).
The bound \(f_{4,r}\) is used with \(r=r_{44}(1-1/R)\) for the padded degree-\(4\) labels (Lemma 5.4); by (6.6) and Lemma 6.3(b), it exceeds \(f_{4,r_{44}}\) by at most \(178/R\) at every threshold in \([-3,3]\).
Proposition 6.9 (enclosures of \(F_3\) and \(F_4\)). The suprema \(F_3\) and \(F_4\) of Definition 6.7 satisfy \[\begin{gather*} 0.1401582523314521636939405140172\ \le\ F_3\ \le\ 0.1401582524,\\ 0.2457719746988\ \le\ F_4\ \le\ 0.24577197475 . \end{gather*}\]
Code: arb_F.py, arb_F_global.py, certify_F4.py
The proof is computer-assisted, in ball arithmetic with the Arb library (Johansson 2017), from one-dimensional integral formulas for the ideal star functions; it is in Appendix A.2.2.
Remark 6.10. The numbers in Proposition 6.9 are used as follows: the lower bounds of \(F_3\) and \(F_4\) in tail estimates and in the exact check of the certificate (Appendix A.2), and the upper bound of \(F_3\) in the certificate for the triples \(\mathsf{R}\) and \(\mathsf{S}\), whose coefficient at degree \(3\) exceeds \(F_3\). Numerically, \(F_3\) is attained at \(\tau\approx-0.06814\) and \(F_4\) at \(\tau\approx-0.16367\); both maximizers are negative, so in the plain sweep the binding thresholds lie slightly below the median.