Thresholds and Expectation-Thresholds of Monotone Properties with Small Minterms

  • Ehud Friedgut
  • Jeff Kahn
  • Clara Shikhelman
Keywords: Thresholds, Boolean functions

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 $\mu_p(\cal{A}) := Pr[N_p \in \cal{A}]$ for $\cal{A} \subseteq 2^N$.


In this paper we study monotone (upward-closed) families $\cal{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(\cal{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 $\cal{A}$ either a substantial subfamily $\cal{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 Kahn and Kalai.

Published
2015-06-03
Article Number
P2.39