Name
Abstract | ||
|---|---|---|
Let N be a finite set, let p epsilon (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) := Pr[N-p epsilon A] for A subset of 2(N). In this paper we study monotone (upward-closed) families A for which all minimal sets in A have size at most k, for some positive integer k. We prove that for such a family mu(p)(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 A either a substantial subfamily 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. |
Year | Venue | Field |
|---|---|---|
2015 | ELECTRONIC JOURNAL OF COMBINATORICS | Structured program theorem,Integer,Discrete mathematics,Combinatorics,Product measure,Finite set,Duality (optimization),Power set,Conjecture,Mathematics,Monotone polygon |
DocType | Volume | Issue |
Journal | 22 | 2.0 |
ISSN | Citations | PageRank |
1077-8926 | 0 | 0.34 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehud Friedgut | 1 | 440 | 38.93 |
| Jeff Kahn | 2 | 304 | 42.26 |
| Clara Shikhelman | 3 | 0 | 0.34 |