Probabilistic Methods in Combinatorics
Probabilistic Methods in Combinatorics
复制标题
组合数学中的概率方法
DOI：
10.1007/978-3-0348-9078-6_132
复制
发表时间：
1974
影响因子：
0.8
通讯作者：
J. Spencer
中科院分区：
文献类型：
--
作者：
J. Spencer
In 1947 Paul Erdős [8] began what is now called the probabilistic method. He showed that if \(\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right){{2}^{{1 - \left( {\begin{array}{*{20}{c}} k \\ 2 \\ \end{array} } \right)}}} n.) In modern lanuage he considered the random graph G(n,.5) as described below. For each k-set S let BS denote the “bad” events that S is either a clique or an independent set. Then Pr[BS] = 21-(k/2) so that ΣPr[BS] < 1, hence ∧\( \wedge {\bar B_s}\) ≠ ∅ and a graph satisfying ∧\( \wedge {\bar B_s}\) must exist.
In 1947 Paul Erdős [8] began what is now called the probabilistic method. He showed that if \(\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right){{2}^{{1 - \left( {\begin{array}{*{20}{c}} k \\ 2 \\ \end{array} } \right)}}} n.) In modern lanuage he considered the random graph G(n,.5) as described below. For each k-set S let BS denote the “bad” events that S is either a clique or an independent set. Then Pr[BS] = 21-(k/2) so that ΣPr[BS] < 1, hence ∧\( \wedge {\bar B_s}\) ≠ ∅ and a graph satisfying ∧\( \wedge {\bar B_s}\) must exist.