Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

Every monotone graph property has a sharp thresholdHTML articles powered by AMS MathViewer

by Ehud Friedgut and Gil Kalai
Proc. Amer. Math. Soc. 124 (1996), 2993-3002 Request permission

Abstract:

In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove a conjecture of Linial that every monotone graph property has a sharp threshold. This follows from the following theorem. Let $V_n(p)= \{0,1\}^n$ denote the Hamming space endowed with the probability measure $\mu _p$ defined by $\mu _p (\epsilon _1, \epsilon _2, \dots , \epsilon _n)= p^k \cdot (1-p)^{n-k}$, where $k=\epsilon _1 +\epsilon _2 +\cdots +\epsilon _n$. Let $A$ be a monotone subset of $V_n$. We say that $A$ is symmetric if there is a transitive permutation group $\Gamma$ on $\{1,2,\dots , n\}$ such that $A$ is invariant under $\Gamma$.

Theorem. For every symmetric monotone $A$, if $\mu _p(A)>\epsilon$ then $\mu _q(A)>1-\epsilon$ for $q=p+ c_1 \log (1/2\epsilon )/\log n$. ($c_1$ is an absolute constant.)

References
• Noga Alon and Joel H. Spencer, The probabilistic method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1992. With an appendix by Paul Erdős; A Wiley-Interscience Publication. MR 1140703
• William Beckner, Inequalities in Fourier analysis, Ann. of Math. (2) 102 (1975), no. 1, 159–182. MR 385456, DOI 10.2307/1970980
• M. Ben-Or and N. Linial, Collective coin flipping, in Randomness and Computation (S. Micali, ed.), Academic Press, New York, 1990, pp. 91-115. Earlier version: Collective coin flipping, robust voting games, and minima of Banzhaf value, Proc. 26th IEEE Symp. on the Foundation of Computer Science, 1985, pp. 408-416.
• Béla Bollobás, Random graphs, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London, 1985. MR 809996
• B. Bollobás and A. Thomason, Threshold functions, Combinatorica 7 (1987), no. 1, 35–38. MR 905149, DOI 10.1007/BF02579198
• Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), no. 1-2, 55–64. MR 1194785, DOI 10.1007/BF02808010
• Peter J. Cameron, Finite permutation groups and finite simple groups, Bull. London Math. Soc. 13 (1981), no. 1, 1–22. MR 599634, DOI 10.1112/blms/13.1.1
• P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
• G. Grimmet, Percolation, Springer-Verlag, New York, 1989.
• J. Kahn, G. Kalai, and N. Linial, The influence of variables on Boolean functions, Proc. 29-th Ann. Symp. on Foundations of Comp. Sci., 68-80, Computer Society Press, 1988.
• J. Håstad (1988), Almost optimal lower bounds for small depth circuits, in S. Micali, ed., Advances in Computer Research, Vol. 5 :Randomness and Computation, 143-170, JAI Press, Greenwich, CT, 1988.
• N. Linial, private communication.
• G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101–108 (Russian). MR 0472604
• Lucio Russo, On the critical percolation probabilities, Z. Wahrsch. Verw. Gebiete 56 (1981), no. 2, 229–237. MR 618273, DOI 10.1007/BF00535742
• Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI 10.1007/BF00537230
• M. Talagrand, Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis’ graph connectivity theorem, Geom. Funct. Anal. 3 (1993), no. 3, 295–314. MR 1215783, DOI 10.1007/BF01895691
• M. Talagrand, On Russo’s approximate zero-one law, Ann. of Probab. 22(1994), 1576-1587.
• M. Talagrand, On boundaries and influences, Combinatorica, to appear.
Similar Articles
• Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 05C80, 28A35, 60K35
• Retrieve articles in all journals with MSC (1991): 05C80, 28A35, 60K35
• Ehud Friedgut
• Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel
• Email: ehudf@math.huji.ac.il
• Gil Kalai
• Affiliation: Institute of Mathematics, The Hebrew University of Jerusalem, Givat Ram, Jerusalem, Israel and Institute for Advanced Study, Princeton, New Jersey 08540
• MR Author ID: 195990
• Received by editor(s): March 27, 1995
• Additional Notes: Research supported in part by grants from the Israeli Academy of Sciences, the U.S.-Israel Binational Science Foundation, the Sloan foundation and by a grant from the state of Niedersachsen.
• Communicated by: Jeffry N. Kahn
• © Copyright 1996 American Mathematical Society
• Journal: Proc. Amer. Math. Soc. 124 (1996), 2993-3002
• MSC (1991): Primary 05C80, 28A35, 60K35
• DOI: https://doi.org/10.1090/S0002-9939-96-03732-X
• MathSciNet review: 1371123