Thresholds and expectation-thresholds of monotone properties with small minterms

Abstract

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 for $\mathcal{A}\subseteq 2^N$ ${\mu }_p(\mathcal{A}):=Pr[N_p\in \mathcal{A}]$. In this paper we study upward-closed families $\mathcal{A}$ for which all minimal sets in $\mathcal{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 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 duality of linear programming. This is related to the threshold conjecture of Kahn and Kalai.