Thresholds and expectation-thresholds of monotone properties with small minterms (Q491531)

Summary: Let \(N\) be a finite set, let \(p \in (0,1)\), and let \(N_p\) denote a random binomial subset of \(N\) where every element of \(N\) is taken to belong to the subset independently with probability \(p\). This defines a product measure \(\mu_p\) on the power set of \(N\), where \(\mu_p(\mathcal{A}) :=\mathrm{Pr}[N_p \in \mathcal{A}]\) for \(\mathcal{A} \subseteq 2^N\). In this paper we study monotone (upward-closed) families \(\mathcal{A}\) for which all minimal sets in \(cal{A}\) have size at most \(k\), for some positive integer \(k\). We prove that for such a family \(\mu_p(\mathcal{A}) / p^k \) is a decreasing function, which implies a uniform bound on the coarseness of the thresholds of such families. We also prove a structure theorem which enables one to identify in \(\mathcal{A}\) either a substantial subfamily \(\mathcal{A}_0\) for which the first moment method gives a good approximation of its measure, or a subfamily which can be well approximated by a family with all minimal sets of size strictly smaller than \(k\). Finally, we relate the (fractional) expectation threshold and the probability threshold of such a family, using linear programming duality. This is related to the threshold conjecture of \textit{J. Kahn} and \textit{G. Kalai} [Comb. Probab. Comput. 16, No. 3, 495--502 (2007; Zbl 1118.05093)].