Kalai–Keller–Mossel correlation conjecture for increasing balanced families

From papers

Let Ωn={0,1}n\Omega_n=\{0,1\}^n with the uniform measure μ\mu. A family AΩn\mathcal{A}\subseteq\Omega_n is increasing if xyx\leq y coordinate-wise implies xAx\in\mathcal{A} whenever yAy\in\mathcal{A}, and balanced if μ(A)=1/2\mu(\mathcal{A})=1/2. For a family F\mathcal{F}, write 1F\mathbf{1}_{\mathcal{F}} for its indicator, and let Covμ\operatorname{Cov}_\mu denote covariance under μ\mu. An increasing linear-threshold family is a family of the form

B={xΩn:i=1naixi>t},\mathcal{B}=\left\{x\in\Omega_n:\sum_{i=1}^n a_i x_i>t\right\},

where ai0a_i\geq 0 and tRt\in\mathbb{R}.

Kalai–Keller–Mossel correlation conjecture. For every increasing and balanced family AΩn\mathcal{A}\subseteq\Omega_n, there exists an increasing linear-threshold family B\mathcal{B} with non-negative weights such that

Covμ(1A,1B)clognn,\operatorname{Cov}_\mu(\mathbf{1}_{\mathcal{A}},\mathbf{1}_{\mathcal{B}})\geq c\,\frac{\log n}{\sqrt{n}},

where c>0c>0 is a universal constant.

The paper states that its second main theorem proves this conjecture, by finding a suitable coordinate projection or the majority function; thus the conjecture is solved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Yiming Chen and Guozheng Dai, “A note on correlation inequalities for regular increasing families”, arXiv:2603.24066 (2026).

Solutions 0

No solutions have been posted yet.