स्नातकोत्तर प्रथम वर्षDiscrete Mathematicsनियोजित
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
इस विषय का पाठ अभी लिखा नहीं गया है। नीचे दी गई रूपरेखा पाठ्यक्रम-मानचित्र का हिस्सा है और इसकी समीक्षा नहीं हुई है।
इस पर आधारित
44 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)
आप सीखेंगे
- 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.
परिभाषा
- 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.
प्रमेय
- 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).
आम भ्रांतियाँ
- Thinking a probabilistic existence proof gives an efficient construction; explicit constructions are often unknown.
वैकल्पिक खोजें
- 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.
आगे पढ़ने के लिए
- Noga Alon and Joel H. Spencer, The Probabilistic Method (1992)