## Abstract

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.

Original language | American English |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 22 |

Issue number | 2 |

DOIs | |

State | Published - Jun 3 2015 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics