1
$\begingroup$

I am interested whether the statement of Kahn-Kalai conjecture (proved by Jinyoung Park and Huy Tuan Pham in '22) can be strengthened to the question about Boolean functions $f : 2^{[1, n]}\to \{0, 1\}$ in the following way:

Definitions (following 1). Let $f : 2^{[1, n]}\to\{0, 1\}$ be any function. For $g : 2^{[1, n]}\to\{0, 1\}$, denote $g\geq f$ if for each $A : f(A) = 1$ there is $B : g(B) = 1, B\subseteq A$.

Questions 1, 2 generalize the KK conjecture.

Question 1. Is it true that for some universal constant $C > 0$ and any $0 < p < 1$ $$\min_{g\geq f}\sum_{B: g(B) = 1}\left(\frac{p}{C\log(n)}\right)^{|B|}\leq \sum_{A: f(C) = 1 \text{ for some }C\subseteq A}p^{|A|}(1 - p)^{|[1, n]\setminus A|}$$holds for each $f : 2^{[1, n]}\to\{0, 1\}$?

Question 2. Is it true that for some universal constant $C > 0$ and any $0 < p < 1$ $$\frac{1}{|\{g:g\geq f\}|}\sum_{g\geq f}\sum_{B: g(B) = 1}\left(\frac{p}{C\log(n)}\right)^{|B|}\leq \sum_{A: f(C) = 1 \text{ for some }C\subseteq A}p^{|A|}(1 - p)^{|[1, n]\setminus A|}$$holds for each $f : 2^{[1, n]}\to\{0, 1\}$?

I think that Question 1 is a consequence of 2, since the proof doesn't rely on $\mu_p(\mathcal{F}) = 1/2$.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .