Probabilistic Methods in Combinatorics
Joel Spencer · Birkhäuser Basel eBooks · 1995
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)}}} < 1 $$ then there exists a graph G on n vertices with clique number w(G) < k and independence number a(G) < k. (in terms of the Ramsey function, R(k,k) > 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.
Cited by 589 works. doi:10.1007/978-3-0348-9078-6_132
Authors
References
- Some remarks on the theory of graphs
- “Integer-making” theorems
- On a combinatorial conjecture of Erdös
- The chromatic number of random graphs
- On a limit theorem in combinatorical analysis
- On a Packing and Covering Problem
- A parallel algorithmic version of the local lemma
- Six Standard Deviations Suffice
- An algorithmic approach to the Lovász local lemma. I
- Poisson approximation for large deviations