MaxCut for ${\mathrm{MTP}}_2$ Covariances

Abstract

Let $X=(X_1,\dots ,X_n)\in \{0,1{\}}^n$ have a multivariate totally positive (${\mathrm{MTP}}_2$) law. We prove that $$\sum _{i<j}\mathbb{E}\left[\left|\mathrm{Cov}(X_i,X_j\mid X_{[n]\setminus \{i,j\}})\right|\right]\le n/2,$$ and more generally a weighted MaxCut inequality for the fully conditioned covariances. As an application, we confirm a conjecture of Allen and O'Donnell on correlation rounding for signed ${\mathrm{MTP}}_2$ laws.

8 pages