Sharp Normalized Covariance Bounds and Constant-Stretch Correlated Sampling on the Hypersimplex

Abstract

We establish the normalized covariance bound conjectured by Anari et al. (2026, Conjecture 3) for fixed-rank external-field measures. Let $d\ge 2$ and $m\in [d-1]$. For $w\in (0,+\infty {)}^d$, let $\mathsf{S}$ be an $m$-subset of $[d]$ with rank-$m$ external-field law $\mathbb{P}(\mathsf{S}=S)=\frac{{\prod }_{i\in S}{w}_i}{e_m(w)},S\subseteq [d],|S|=m,$ where $e_m(w):={\sum }_{T\subseteq [d],|T|=m}{\prod }_{\ell \in T}{w}_{\ell }$ is the $m$th elementary symmetric polynomial in $w_1,\dots ,w_d$. Let $X:=(X_1,\dots ,X_d{)}^{\top }$ be its indicator vector, i.e., $X_i=\mathbb{I}\{i\in \mathsf{S}\},i\in \{1,\dots ,d\}.$ Let $\Sigma :=\mathrm{Cov}(X)$, put $v_i:={\Sigma }_{ii}$ for each $i\in [d]$, and define $v:=(v_1,\dots ,v_d{)}^{\top },D:=\mathrm{diag}(v),V:={\sum }_{i=1}^d{v}_i.$ We prove $\Sigma ⪰D-\frac{v{v}^{\top }}{V}.$ This improves the coefficient $1/2$ in the first version of our work (Cesari and Colomboni, 2026, Corollary 1.3) to the optimal universal value $1$. As a first corollary, we improve the coefficient in the pseudoinverse bound of Bacchiocchi et al. (2026, Lemma 2) from $2$ to the optimal value $1$. Specializing this bound to coordinate differences gives an alternative proof of our effective-resistance theorem from the first version of our work (Cesari and Colomboni, 2026, Theorem 1.1). The framework of Anari et al. (2026, Theorem 1 and Corollary 2) also yields unconditional correlated-sampling guarantees with stretch $6$ on the hypersimplex and $12$ on its at-most variant. Unconditional constant-stretch guarantees were first established in the first version of our work (Cesari and Colomboni, 2026, Corollaries 1.4 and 1.5), with constants $16$ and $32$, which we improve here to $6$ and $12$. These improved constants strengthen the positive resolution, established in the first version of our work, of the constant-stretch question posed by Naor et al. (2026, Theorem 2 and Section 5).