Mwaka wa kwanza wa uzamiliDiscrete MathematicsImepangwa
The probabilistic method
Proving existence by showing that a random object has the desired property with positive probability: Erdős's lower bound for Ramsey numbers, linearity of expectation, the second-moment method, the Lovász local lemma and concentration inequalities.
math.discrete.probabilistic-method
Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.
Inajengwa juu ya
Masharti ya awali ya lazima 44 (hadi chini kabisa)
Utajifunza
- Prove Erdős's bound R(k, k) > 2^(k/2) for k ≥ 3 using a random colouring.
- Use linearity of expectation and deletion arguments to prove existence results.
- Apply the Lovász local lemma and Chernoff bounds.
Fasili
- First-moment method: if X takes non-negative integer values and E[X] < 1, then P(X = 0) > 0.
- Lovász local lemma (symmetric form): if each of a collection of bad events has probability at most p and is mutually independent of all but at most d of the others, and ep(d + 1) ≤ 1, then with positive probability none of the bad events occurs.
Nadharia
- R(k, k) > 2^(k/2) for every k ≥ 3 (Erdős, 1947).
- There are graphs with arbitrarily large girth and arbitrarily large chromatic number (Erdős, 1959).
Mawazo potofu ya kawaida
- Thinking a probabilistic existence proof gives an efficient construction; explicit constructions are often unknown.
Ugunduzi wa hiari
- Computational complexity Derandomisation asks when random constructions can be replaced by efficient deterministic ones; the algorithmic local lemma of Moser and Tardos is one success.
Usomaji zaidi
- Noga Alon and Joel H. Spencer, The Probabilistic Method (1992)