HackerPapers

arXiv:math/0603218math.CO

Thresholds and expectation thresholds

Jeff Kahn, Gil Kalai

Early discovery. Linked by one identifiable commenter. This paper is outside the main ranking; a mention is not an endorsement.

Abstract

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.

arXiv comments
The gap between expectations and reality is studied, 7 pages
Journal reference
DOI
Subjects
math.COCombinatorics math.PRProbability

On Hacker News

Linked by 1 identifiable commenter in 1 comment across 1 thread, from Apr 2022 to Apr 2022.

Comments linking this paper, per year.

Discussed in comments1 thread

  1. Elegant six-page proof reveals the emergence of random structure 1 comment

    • Neat comment on the arxiv (https://arxiv.org/abs/math/0603218): The gap between expectations and reality is studied, 7 pages (these comments are added by the submitting author).

      axiom92View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.