Thresholds and expectation thresholds

Jeff Kahn; Gil Kalai

doi:10.1017/S0963548307008474

Thresholds and expectation thresholds

Jeff Kahn, Gil Kalai

School of Arts and Sciences, Mathematics

Research output: Contribution to journal › Article › peer-review

55 Scopus citations

Abstract

We consider relations between thresholds for monotone set properties and simple lower bounds for such thresholds. A motivating example (Conjecture 2): Given an n-vertex graph H, write PE for the least p such that, for each subgraph H′ of H, the expected number of copies of H′ in G = G(n,p) is at least 1, and p_c for that p for which the probability that G contains (a copy of) H is 1/2. Then (conjecture) p_c = O(P_E log n). Possible connections with discrete isoperimetry are also discussed.

Original language	English (US)
Pages (from-to)	495-502
Number of pages	8
Journal	Combinatorics Probability and Computing
Volume	16
Issue number	3
DOIs	https://doi.org/10.1017/S0963548307008474
State	Published - May 2007

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistics and Probability
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.1017/S0963548307008474

Cite this

@article{39fd5abc0b46489487f9e85c80a5244e,

title = "Thresholds and expectation thresholds",

abstract = "We consider relations between thresholds for monotone set properties and simple lower bounds for such thresholds. A motivating example (Conjecture 2): Given an n-vertex graph H, write PE for the least p such that, for each subgraph H′ of H, the expected number of copies of H′ in G = G(n,p) is at least 1, and pc for that p for which the probability that G contains (a copy of) H is 1/2. Then (conjecture) pc = O(PE log n). Possible connections with discrete isoperimetry are also discussed.",

author = "Jeff Kahn and Gil Kalai",

note = "Funding Information: † Supported by NSF grant DMS0200856. Research partly carried out at Microsoft Research. ‡ Supported by NSF and ISF grants.",

year = "2007",

month = may,

doi = "10.1017/S0963548307008474",

language = "English (US)",

volume = "16",

pages = "495--502",

journal = "Combinatorics Probability and Computing",

issn = "0963-5483",

publisher = "Cambridge University Press",

number = "3",

}

TY - JOUR

T1 - Thresholds and expectation thresholds

AU - Kahn, Jeff

AU - Kalai, Gil

N1 - Funding Information: † Supported by NSF grant DMS0200856. Research partly carried out at Microsoft Research. ‡ Supported by NSF and ISF grants.

PY - 2007/5

Y1 - 2007/5

N2 - We consider relations between thresholds for monotone set properties and simple lower bounds for such thresholds. A motivating example (Conjecture 2): Given an n-vertex graph H, write PE for the least p such that, for each subgraph H′ of H, the expected number of copies of H′ in G = G(n,p) is at least 1, and pc for that p for which the probability that G contains (a copy of) H is 1/2. Then (conjecture) pc = O(PE log n). Possible connections with discrete isoperimetry are also discussed.

AB - We consider relations between thresholds for monotone set properties and simple lower bounds for such thresholds. A motivating example (Conjecture 2): Given an n-vertex graph H, write PE for the least p such that, for each subgraph H′ of H, the expected number of copies of H′ in G = G(n,p) is at least 1, and pc for that p for which the probability that G contains (a copy of) H is 1/2. Then (conjecture) pc = O(PE log n). Possible connections with discrete isoperimetry are also discussed.

UR - http://www.scopus.com/inward/record.url?scp=34247640604&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247640604&partnerID=8YFLogxK

U2 - 10.1017/S0963548307008474

DO - 10.1017/S0963548307008474

M3 - Article

AN - SCOPUS:34247640604

SN - 0963-5483

VL - 16

SP - 495

EP - 502

JO - Combinatorics Probability and Computing

JF - Combinatorics Probability and Computing

IS - 3

ER -

Thresholds and expectation thresholds

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this