Metoda probabilistica

Metoda probabilistă este o metodă neconstructivă pentru a demonstra existența unui obiect matematic cu proprietăți date. Utilizat mai ales în combinatorică , dar și în teoria numerelor , algebră liniară și calcul , precum și în informatică (cum ar fi metoda de rotunjire probabilistică ) și teoria informației .

Metoda constă în estimarea probabilității ca un obiect aleatoriu dintr-o clasă dată să satisfacă condiția dorită. Dacă se demonstrează că această probabilitate este pozitivă, atunci există un obiect cu proprietățile dorite. Deși demonstrația folosește probabilități, concluzia finală este definitivă, fără nicio ambiguitate.

Instrumentele comune utilizate în metoda probabilistică includ inegalitatea lui Markov , inegalitatea lui Chernov și lema locală a lui Lovas .

Istorie

Cea mai cunoscută aplicare a acestei metode este asociată cu Erdős . Cu toate acestea, metoda probabilistică a fost aplicată chiar înainte de munca lui Erdős în această direcție. De exemplu, Seles în 1943 a folosit metoda pentru a demonstra că există turnee care conțin un număr mare de cicluri hamiltoniene .

Exemple

Următoarele două exemple de aplicare a metodei probabilistice sunt discutate în detaliu în cartea Evidence from the Book de Martin Aigner și Günther Ziegler .

Limită inferioară pentru numărul Ramsey

Trebuie să demonstrăm existența unei colorări în două culori (să zicem, roșu și albastru) a muchiilor unui graf complet cu vârfuri (pentru valori nu foarte mari ale ) astfel încât să nu existe un subgraf monocromatic complet cu vârfuri (care este, cu fiecare margine de aceeași culoare). $n$ $n$ $r$

Vom alege culorile la întâmplare. Culoarea fiecărei margini este aleasă independent cu probabilitate egală roșu sau albastru. Calculați numărul așteptat de subgrafe monocromatice complete cu vârfuri după cum urmează: $r$

Pentru orice set de vârfuri din graficul nostru, definiți o valoare de 1 dacă fiecare muchie se termină în aceeași culoare și 0 în caz contrar. Rețineți că numărul de subgrafe monocromatice este suma totală . $S$ $r$ $X(S)$ $S$ $r$ $X(S)$ $S$

Pentru orice , așteptarea este probabilitatea ca toate muchiile din să aibă aceeași culoare. Si asta inseamnă $S$ $\mu$ $X(S)$ ${r \alegeți 2}$ $S$

\mu =2\cdot 2^{-{r \alegeți 2)).

Factorul 2 apare deoarece există două culori posibile.

Același lucru este valabil pentru oricare dintre posibilele submulțimi cu vârfuri. Astfel încât așteptarea matematică a sumei peste toate este egală ${n \alegeți r)$ $r$ $X(S)$ $S$

M={n \alegeți r}\cdot \mu = {n \alegeți r}\cdot 2\cdot 2^{-{r \alegeți 2))

Suma așteptărilor matematice este egală cu așteptarea sumei (indiferent dacă variabilele sunt independente ). Cu alte cuvinte , există numărul mediu de subgrafe monocromatice ale unui grafic colorat aleatoriu. $M$ $r$

Numărul de subgrafe monocromatice într-o colorare aleatorie va fi întotdeauna un număr întreg . Prin urmare, dacă , atunci în cel puțin o colorare, nu trebuie să existe subgrafe monocromatice complete. $r$ $M<1$ $r$

Adică dacă

2\cdot {n \alegeți r}<2^{r \alegeți 2},

apoi

R(r,r)>n

unde denotă numărul Ramsey pentru . În special, crește cel puțin exponențial în . $R(r,r)$ $r$ $R(r,r)$ $r$

Note

Dovada de mai sus este dată de Erdős. [unu]
Această metodă nu oferă un exemplu explicit de astfel de colorare. Problema descrierii unui anumit exemplu este deschisă de mai bine de 50 de ani.

Construirea unui grafic fără cicluri scurte cu un număr cromatic mare

Fie numere întregi pozitive și să fie date . Trebuie să construim un grafic cu toate ciclurile de lungime cel puțin și, în același timp, numărul cromatic G este cel puțin . $g$ $k$ $G$ $g$ $k$

Fixăm un întreg mare . Considerăm un grafic aleatoriu cu vârfuri, unde fiecare muchie în există cu probabilitatea p = n 1/ g −1 . Să arătăm că următoarele două proprietăți sunt valabile cu probabilitate pozitivă $n$ $G$ $n$ $G$

Proprietatea 1. conţine cel mult cicluri de lungime mai mică de . Mai precis, probabilitatea ca graficul să aibă nu mai mult de cicluri de lungime mai mică decât tinde spre 1 ca . $G$ $n/2$ $g$ $G$ $n/2$ $g$ $n\la\infty$

Dovada. Fie numărul de cicluri de lungime mai mică decât . Numărul de cicluri de lungime dintr-un grafic complet cu vârfuri este $X$ $g$ $i$ $n$

{\frac {n!}{2\cdot i\cdot (ni)!}}\leq {\frac {n^{i}}{2}}

iar fiecare dintre ele este cuprins în cu probabilitate p i . Prin urmare, prin inegalitatea lui Markov, avem $G$

\Pr \left(X>{\tfrac {n}{2}}\right)\leq {\frac {2}{n}}\cdot E[X]\leq {\frac {1}{ n}}\cdot \sum _{i=3}^{g-1}p^{i}\cdot n^{i}={\frac {1}{n}}\cdot \sum _{i= 3}^{g-1}n^{\frac {i}{g}}\leq {\frac {g}{n}}\cdot n^{\frac {g-1}{g}}=g \cdot n^{-{\frac {1}{g}}}=o(1).

■

Proprietatea 2. nu conține un set independent de mărime . Mai precis, probabilitatea ca un grafic să aibă un set de dimensiuni independente tinde spre 1 ca . $G$ $\lceil {\tfrac {n}{2k)}\rceil$ $G$ $\lceil {\tfrac {n}{2k)}\rceil$ $n\la\infty$

Dovada. Să notăm dimensiunea celei mai mari mulțimi independente în . Evident că avem $Y$ $G$

\Pr(Y\geq y)\leq {n \alegeți y}(1-p)^{\frac {y(y-1)}{2))\leq n^{y}e^{ -{\frac {py(y-1)}{2}}}=e^{-{\frac {y}{2}}\cdot (py-2\ln np)}=o(1),

când

y=\left\lceil {\frac {n}{2k)}\right\rceil .

■

Deoarece are aceste două proprietăți, putem extrage maximul de vârfuri din pentru a obține un nou grafic cu vârfuri care conțin doar cicluri de lungime cel mult . Vedem că are un set de dimensiuni independent . poate fi împărțit numai în mulțimi cel puțin independente și, prin urmare, are un număr cromatic de cel puțin . $G$ $n/2$ $G$ $G'$ $n'\geq n/2$ $g$ $G'$ $\lceil {\frac {n'}{k)}\rceil$ $G'$ $k$ $k$

Note

Acest rezultat explică de ce calcularea numărului cromatic al unui grafic este o sarcină dificilă. Chiar și în absența cauzelor locale (cum ar fi ciclurile mici), numărul cromatic poate fi arbitrar mare.

Vezi și

Numărătoare aleatorie

Literatură

Aigner M. Ziegler G. Dovezi din carte. Cele mai bune dovezi din vremea lui Euclid până în zilele noastre. - Editura „Laboratorul de Cunoaștere” (fostă „BINOM. Laboratorul de Cunoaștere”), 2014. - ISBN 978-5-9963-2736-2 .

Alon N., Spencer J. Metoda probabilistică, Binom, 2007, p. 320, 1100 de exemplare. ISBN 978-5-94774-556-6

A. M. Raigorodsky . Grafice cu număr cromatic mare și circumferință mare // Matem. iluminarea , ser. 3. - 2016. - T. 20 . - S. 228-237 . (Rusă)

În limba engleză

Erdős, P. Teoria grafurilor și probabilitatea (nedefinită) // Canad. J. Math .. - 1959. - T. 11 , nr 0 . - S. 34-38 . - doi : 10.4153/CJM-1959-003-9 . Arhivat din original pe 18 iulie 2011.

J. Matousek, J. Vondrak. Metoda probabilistică . note de curs.

Alon, N și Krivelevich, M (2006). Combinatorică extremă și probabilistă

Note de subsol

↑ Erdös, P. Câteva observații despre teoria grafurilor. Taur. amer. Matematică. soc. 53, (1947). 292–294.