Thresholds and expectation thresholds
| dc.creator | Kahn, Jeff | |
| dc.creator | Kalai, Gil | |
| dc.date | 2006-03-09 | |
| dc.date | 2006-04-02 | |
| dc.date.accessioned | 2026-07-07T07:06:42Z | |
| dc.date.available | 2026-07-07T07:06:42Z | |
| dc.description | Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value for which the expected number of copies of H' in G is at least 1/2 for every subgraph H' of H. Let p be the value for which the probability that G contains a copy of H is 1/2. Conjecture: p/q = O(log n). Related conjectures for general Boolean functions, and a possible connection with discrete isoperimetry are discussed. | |
| dc.description | The gap between expectations and reality is studied, 7 pages | |
| dc.identifier | https://arxiv.org/abs/math/0603218 | |
| dc.identifier | http://arxiv.org/abs/math/0603218 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/110124 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05C80, 05D40, 60C05, 60K35, 82B26, 94C10, 06E30 | |
| dc.title | Thresholds and expectation thresholds | |
| dc.type | text |