← All problems

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

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
  1. 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.