### 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 | English (US) |
---|---|

Journal | Electronic Journal of Combinatorics |

Volume | 22 |

Issue number | 2 |

DOIs | |

State | Published - Jun 3 2015 |

### All Science Journal Classification (ASJC) codes

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

## Fingerprint Dive into the research topics of 'Thresholds and expectation-thresholds of monotone properties with small minterms'. Together they form a unique fingerprint.

## Cite this

*Electronic Journal of Combinatorics*,

*22*(2). https://doi.org/10.37236/4769