Thresholds and expectation-thresholds of monotone properties with small minterms

Ehud Friedgut, Jeff Kahn, Clara Shikhelman

Research output: Contribution to journalArticle

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 languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume22
Issue number2
DOIs
StatePublished - 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