The Probabilistic MethodWiley, 1992 - 254 Seiten One of the most powerful and popular tools used in combinatorics is the probabilistic method. Describes current algorithmic techniques, applying both the classical method and the modern tools it uses. Along with a detailed description of the techniques used in probabilistic arguments, it includes basic methods which utilize expectation and variance plus recent applications of martingales and correlation inequalities. Examines discrepancy and random graphs and covers such topics as theoretical computer science, computational geometry, derandomization of randomized algorithms and more. A study of various topics using successful probabilistic techniques is included along with an Open Problems Appendix by Paul Erdös, the founder of the probabilistic method. |
Inhalt
The Basic Method | 3 |
The ErdősKoRado Theorem | 13 |
Brégmans Theorem | 23 |
Urheberrecht | |
34 weitere Abschnitte werden nicht angezeigt.
Häufige Begriffe und Wortgruppen
2-coloring algorithm apply asymptotic Boolean function Chapter chromatic number circuit clique coloring combinatorial completing the proof components computing conditional probability conjecture contains copies of H Corollary define denote the number digraph disc(A disjoint distribution edges eigenvalue Erdős event exists expected number finite fixed follows G₁ given gives graph G graph theory Hamiltonian paths hence hypergraph independent set indicator random variable inequality integer k-cliques k-sets least Lemma Let G Let H linearity of expectation Lovász local lemma lower bound martingale matrix monochromatic monotone mutually independent number of vertices Paul Erdős points polynomial Pr(A Pr[B Pr[T Pr[X Probabilistic Lens probabilistic method probability space problem Proof of Theorem prove quasi-random R₁ random graph random variable randomly range space result Rödl satisfies Section set of vertices subgraph subsets Suppose Theorem 2.1 tournament triangle upper bound var[X VC-dimension vector vertex y₁