Let N be a finite set, let p 2 (0; 1), and let Np 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 fip on the power set of N, where fip(A):= Pr[Np 2 A] for A fi 2N. In this paper we study monotone (upward-closed) families A for which all min- imal sets in A have size at most k, for some positive integer k. We prove that for such a family fip(A)=pk 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 A either a substantial subfamily A0 for which the first moment method gives a good approxi- mation 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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics