Szansa na sukces
Metoda probabilistyczna gościła już na łamach Delty (np. w numerach 12/2006 i 4/2015), byłoby jednak nieprawdopodobnie głupio pominąć ją w numerze poświęconym dowodom.
W najbardziej podstawowej wersji może się ona okazać przydatna w sytuacji, gdy chcemy wykazać istnienie obiektu spełniającego określone warunki - wówczas możemy spróbować przedstawić schemat losowania badanych obiektów, w którym z dodatnim prawdopodobieństwem wynik będzie spełniał przedstawione żądania. Opis ten może brzmieć dość enigmatycznie, powinien stać się bardziej zrozumiały po lekturze poniższego rozumowania, uchodzącego za jeden z pierwszych przykładów zastosowania metody probabilistycznej.
Rozważmy graf pełny, którego każde dwa wierzchołki są połączone krawędzią w kolorze niebieskim bądź czerwonym. Okazuje się, co udowodnił Frank Ramsey w 1930 roku, że
Twierdzenie. Dla dowolnie zadanych liczb naturalnych jeśli liczba wierzchołków w grafie pełnym jest dostatecznie duża, istnieje w nim podgraf o
wierzchołkach połączonych wyłącznie niebieskimi krawędziami lub podgraf o
wierzchołkach, z których każde dwa połączone są krawędziami czerwonymi.
Najmniejszy z tych "dostatecznie dużych" rozmiarów wyjściowego grafu nazywamy liczbą Ramseya i oznaczamy przez W 1947 roku Paul Erdős przedstawił następujące oszacowanie z dołu liczby
![]() |
(*) |
Oto jak uzyskał ten wynik: rozważmy graf o wierzchołkach, gdzie
jest "niedostatecznie duże", czyli
Pokażemy, że możemy pokolorować krawędzie tego grafu w taki sposób, by nie istniał podgraf rozmiaru
o wszystkich krawędziach w tym samym kolorze; zatem natychmiastowym wnioskiem będzie nierówność (*).
Każdą z krawędzi naszego grafu pomalujmy na niebiesko z prawdopodobieństwem lub na czerwono z tym samym prawdopodobieństwem. Wybierzmy dowolny podgraf o
wierzchołkach - wówczas zdarzenie, polegające na pomalowaniu wszystkich krawędzi wybranego podgrafu (których jest
inaczej
) na ten sam kolor, ma prawdopodobieństwo
Podgrafów o
wierzchołkach jest jednak
Szansa na to, że pewien z tych podgrafów ma krawędzie pomalowane na jeden kolor, nie przekracza
zatem zgodnie z założeniem o "niedostatecznie dużym"
jest mniejsza od 1. W tej sytuacji szansa na to, że żaden z podgrafów o
wierzchołkach nie ma wszystkich krawędzi w tym samym kolorze, jest dodatnia, co dowodzi istnienia żądanego kolorowania.