Thresholds and expectation-thresholds of monotone properties with small minterms

Ehud Friedgut¹ ; Jeff Kahn ; Clara Shikhelman²

¹Weizmann Institute
²Tel Aviv University

The electronic journal of combinatorics, Tome 22 (2015) no. 2

Résumé

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.

Détail

DOI : 10.37236/4769

Classification : 05C80, 05C99, 60C05
Mots-clés : thresholds, Boolean functions