Skip to main content
1 of 8
Drrd
  • 11
  • 2

Question related to Kahn-Kalai conjecture

I am interested whether the statement of Kahn-Kalai conjecture (proved by Jinyoung Park and Huy Tuan Pham in '22) can be reformulated (and even 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$ and $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}{Cn}\right)^{|B|}\leq \sum_{A: f(A) = 1}p^{|A|}(1 - p)^{|[1, n]\setminus A|}?$$

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

Drrd
  • 11
  • 2