Mathematics – Combinatorics
Scientific paper
2006-03-09
Mathematics
Combinatorics
The gap between expectations and reality is studied, 7 pages
Scientific paper
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.
Kahn Jeff
Kalai Gil
No associations
LandOfFree
Thresholds and expectation thresholds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Thresholds and expectation thresholds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thresholds and expectation thresholds will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-711745