The 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)