Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-22T06:04:49.075Z Has data issue: false hasContentIssue false
  • English
  • Français

Thresholds and Expectation Thresholds

Published online by Cambridge University Press:  01 May 2007

JEFF KAHN  and
GIL KALAI
JEFF KAHN
Affiliation:
Department of Mathematics, Rutgers University, Piscataway NJ [email protected]
GIL KALAI
Affiliation:
Department of Mathematics, The Hebrew University, Jerusalem, [email protected]
Get access Rights & Permissions [Opens in a new window]

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(pElog n). Possible connections with discrete isoperimetry are also discussed.

Type
PROBLEM SECTION
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 3 , May 2007 , pp. 495 - 502
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Achlioptas, D., Naor, A. and Peres, Y., Rigorous location of phase transitions in hard optimization problems, Nature 435 (2005), 759–764.CrossRefGoogle ScholarPubMed
[2]Alon, N. and Spencer, J., The Probabilistic Method, Wiley, New York, 2000.CrossRefGoogle Scholar
[3]Ben-Or, M. and Linial, N., Collective coin flipping, in Randomness and Computation (Micali, S., ed.), New York, Academic Press, pp. 91–115, 1990.Google Scholar
[4]Bollobás, B., Random, Graphs, pp. 257–274 in Combinatorics, London Math. Soc. Lecture Note Ser. 52, Cambridge Univ. Press, Cambridge, 1981.Google Scholar
[5]Bollobás, B., The evolution of sparse graphs, pp. 35–57 in Graph Theory and Combinatorics, Bollobás, B., ed., Academic Pr., 1984.Google Scholar
[6]Bollobás, B., Random Graphs, Academic Press, London, 1985.Google Scholar
[7]Bollobás, B. and Riordan, O., A short proof of the Harris-Kesten Theorem, Bull. London Math. Soc. 38 (2006), 470–484.CrossRefGoogle Scholar
[8]Bollobás, B. and Thomason, A., Threshold functions, Combinatorica 7 (1987), 35–38.CrossRefGoogle Scholar
[9]Bourgain, J., On sharp thresholds of monotone properties, Appendix to [13].Google Scholar
[10]Cooper, C., Frieze, A., Molloy, M. and Reed, B., Perfect matchings in random $r$-regular, $s$-uniform hypergraphs, Combin. Probab. Comput. 5 (1996), 1–14.CrossRefGoogle Scholar
[11]Erdös, P., On the combinatorial problems which I would most like to see solved, Combinatorica 1 (1981), 25–42.CrossRefGoogle Scholar
[12]Erdös, P. and Rényi, A., On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960), 17–61.Google Scholar
[13]Friedgut, E., Sharp thresholds of graph properties, and the $k$-sat problem. J. Amer. Math. Soc. 12 (1999), 1017–1054.CrossRefGoogle Scholar
[14]Friedgut, E., Influences in product spaces: KKL and BKKKL revisited, Combin. Probab. Comput. 13 (2004), 17–29.CrossRefGoogle Scholar
[15]Friedgut, E., Kahn, J. and Wigderson, A., Computing graph properties by randomized subcube partitions, Randomization and Approximation Techniques in Computer Science, 6th International Workshop (2002), 105–113.CrossRefGoogle Scholar
[16]Frieze, A. and Janson, S., Perfect matchings in random $s$-uniform hypergraphs, Random Structures & Algorithms 7 (1995), 41–57.CrossRefGoogle Scholar
[17]Grimmett, G., Percolation, Second edition, Springer-Verlag, Berlin, 1999.CrossRefGoogle Scholar
[18]Janson, S., Łuczak, T. and Ruciński, A., Random Graphs, Wiley, New York, 2000.CrossRefGoogle Scholar
[19]Johansson, A., Triangle factors in random graphs, manuscript, 2005.Google Scholar
[20]Kahn, J., Kalai, G. and Linial, N., The influence of variables on Boolean functions, in Proc. 29-th Annual Symposium on Foundations of Computer Science, 68–80, 1988.CrossRefGoogle Scholar
[21]Kalai, G. and Safra, S., Threshold Phenomena and Influence, pp. 25–60 in Computational Complexity and Statistical Physics, Percus, A. G., Istrate, G. and Moore, C., eds., Oxford University Press, New York, 2006.Google Scholar
[22]Kim, J. H., Perfect matchings in random uniform hypergraphs, Random Structures & Algorithms 23 (2003), 111–132.CrossRefGoogle Scholar
[23]Komlós, J. and Szemerédi, E., Limit distributions for the existence of Hamilton cycles in a random graph, Discrete Math. 43 (1983), 55–63.CrossRefGoogle Scholar
[24]Korshunov, A. D., Solution of a problem of Erdös and Rényi on Hamiltonian cycles in non-oriented graphs, Soviet Mat. Dokl. 17 (1976), 760–764.Google Scholar
[25]Krivelevich, M., Triangle factors in random graphs, Combin. Probab. Comput. 6 (1997), 337–347.CrossRefGoogle Scholar
[26]Ledoux, M., The concentration of measure phenomenon, Mathematical Surveys and Monographs, 89, American Mathematical Society, Providence, RI, 2001.Google Scholar
[27]Pósa, L., Hamiltonian circuits in random graphs, Disc. Math. 14 (1976), 359–364.CrossRefGoogle Scholar
[28]Russo, L., On the critical percolation probabilities, Z. Wahrsch. Verw. Geb. 56 (1981), 229–237.CrossRefGoogle Scholar
[29]Schmidt, J. and Shamir, E., A threshold for perfect matchings in random $d$-pure hypergraphs, Disc. Math. 45 (1983), 287–295.CrossRefGoogle Scholar
[30]Talagrand, M., Are all sets of positive measure essentially convex?, pp. 295–310 in Geometric Aspects of Functional Analysis (Israel, 1992–1994) (Lindenstrauss, J. and Milman, V., eds.), Operator theory, advances and applications Vol. 77, Bikhäuser, Basel, 1995.CrossRefGoogle Scholar
[31]Talagrand, M., Selector processes on classes of sets, Proba. Theor. Rel. Fields, 135 (2006), 471–486.CrossRefGoogle Scholar