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

About 4 years old · traced to

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 T≥1T\geq 1, ∣Ft∣=∣Ht∣=m≤k|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.

References

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.