Valószínűségszámítási módszerek a kombinatorikában

1. Legyen H egy legfeljebb 2^{r−1} − 1 élű r-uniform hipergráf. Bizonyítsuk be, hogy a pontok 2 színnel színezhetők úgy, hogy minden r pontú élben mindkét szín előfordul.

2. Bizonyítsuk be, hogy az R_{2}(n, n) Ramsey szám legalább 2^{n/2}.

3. Bizonyítsuk be, hogy az 1, 2, , …, 2^{k/2} számok 2 színnel színezhetők úgy, hogy ne legyen k tagú monokromatikus számtani sorozat.

Beszélünk az 1997 Schweitzer verseny 1. feladatának (i.) részéről, illetve a megoldás gerincét alkotó Lovász lokális lemmáról és annak bizonyításáról. A Schweitzer feladat:

Definiáljuk minden k pozitív egész számra gráfoknak egy G_{k} osztályát a következő módon. Egy G = (V, E) gráf pontosan akkor eleme G_{k}-nak, ha létezik éleinek olyan ψ: E → [k] = {1, 2, …, k} színezése, hogy a csúcsok tetszőleges φ: V → [k] színezése esetén található a gráfnak olyan e = {x, y} éle, melyre φ(x) = φ(y) = ψ(e). Bizonyítsuk be, hogy léteznek c_{1} < c_{2} pozitív konstansok az alábbi két tulajdonsággal:

(i) minden G_{k}-beli gráfnak legalább c_{1}k^{2} csúcsa van;

(ii) van G_{k}-ban olyan gráf, melynek legfeljebb c_{2}k^{2} csúsa van.

A tárgyalandó (i) rész állítása így is fogalmazható: Ha egy gráf csúcsainak száma kisebb, mint c_{1}k^{2} (c_{1} = \frac{1}{8} választás például megfelelő), és a gráf éleit kiszínezzük k színnel valamilyen módon, akkor a gráf csúcsainak létezik olyan kiszínezése ezzel a k színnel úgy, hogy e színezéssel a gráf minden élére igaz a következő állítás: Az élnek és az él két végpontjában levő csúcsoknak a színe (azaz három helyen lévő szín) mindegyike nem egyezhet meg. Lássuk be az alább megfogalmazott és tárgyalandó Lovász lokális lemma segítségével a követező eredményt: Ha minden csúcsot egymástól függetlenül kiszínezünk k színnel, minden színt egyforma valószínűséggel választva, akkor pozitív annak a valószínűsége, hogy valamelyik színezés teljesíti a kívánt tulajdonságot.

A Lovász lokális lemma célja jól használható feltételt adni arra, hogy pozitív legyen annak a valószínűsége, hogy bízonyos események mindegyike bekövetkezik. Olyan feltételt fogalmaz meg, mely akkor is alkalmazható, amikor a tekintett események nem teljesen (csak majdnem teljesen) függetlenek, és az események együttes bekövetkezésének a valószínűsége kicsi is lehet.

Lovász lokális lemma: Legyenek A_{1}, …, A_{n} események egy valószínűségi mezőn, d egy egész szám, melyek teljesítik a következő feltételeket:

1. P (A_{j}) ≤ \frac{1}{4d} minden j = 1, …, n-re

2. Lehet olyan gráfot definiálni, melynek csúcsai az {1, 2, …, n} pontok, minden pont fokszáma kisebb vagy egyenlő d-vel, és amennyiben valamilyen az i pont a j_{1}, …, j_{k} pontok egyikével sincs összekötve, akkor az A_{i} esemény független az A_{j_{1}}, …, A_{j_{k}} események együttesétől (azaz az A_{j_{1}}, …, A_{j_{k}} események minden függvényétől).

Ekkor P (Ā_{1} ⋯ Ā_{n}) > 0, ahol Ā_{i} az A_{i} esemény komplementere.

4. Bizonyítsuk be a Lovász lemmát, illetve ennek segítségével a Schweitzer verseny első feladatának (i) részét. Segítség: Bizonyítsuk be k szerinti teljes indukcióval, hogy

P (A_{j}|Ā_{i_{1}} ⋯ Ā_{i_{k}}) = \frac{P (A_{j}Ā_{i_{1}} ⋯ Ā_{i_{h}}|Ā_{i_{h+1}} ⋯ Ā_{i_{k}})}{P (Ā_{i_{1}} ⋯ Ā_{i_{h}}|Ā_{i_{h+1}} ⋯ Ā_{i_{k}})} ≤ \frac{1}{2d},

ahol i_{1}, …, i_{h} azok a pontok az i_{1}, …, i_{k} pontok közül, amelyek a tekintett gráfban össze vannak kötve a j ponttal.