The general CNF–DNF correlation inequality for random points in a hypercube

Let U1,,Uk,Uk+1,,U2k,U2k+1,,UnU_1,\ldots,U_k,U_{k+1},\ldots,U_{2k},U_{2k+1},\ldots,U_n be independent and identically distributed random variables with the uniform distribution on (0,1)(0,1). Let F1,,FT[k]×{2k+1,,n}F_1,\ldots,F_T\subset [k]\times\{2k+1,\ldots,n\} and H1,,HT{k+1,,2k}×{2k+1,,n}H_1,\ldots,H_T\subset\{k+1,\ldots,2k\}\times\{2k+1,\ldots,n\}, where T1T\geq 1, Ft=Ht=mk|F_t|=|H_t|=m\leq k for every t[T]t\in[T], and

j=1m1{(i,j)Ft}1for every i[k], t[T],\sum_{j=1}^{m}\mathbf{1}_{\{(i,j)\in F_t\}}\leq 1\quad\text{for every }i\in[k],\ t\in[T],

with the analogous condition

j=1m1{(i,j)Ht}1for every i{k+1,,2k}, t[T].\sum_{j=1}^{m}\mathbf{1}_{\{(i,j)\in H_t\}}\leq 1\quad\text{for every }i\in\{k+1,\ldots,2k\},\ t\in[T].

General CNF–DNF correlation conjecture. Under these assumptions, the inequality referred to in the source as the CNF–DNF inequality holds.

Sources & referencesView supporting material

Primary source

Royi Jacobovic and Or Zuk, “A correlation inequality for random points in a hypercube with some implications”, arXiv:2209.00346 (2022).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.