Probabilistisk metod

Den probabilistiska metoden är en icke -konstruktiv metod för att bevisa existensen av ett matematiskt objekt med givna egenskaper. Används mestadels inom kombinatorik , men även inom talteori , linjär algebra och kalkyl , samt inom datavetenskap (som den probabilistiska avrundningsmetoden ) och informationsteori .

Metoden består i att uppskatta sannolikheten för att ett slumpmässigt objekt från en given klass uppfyller det önskade villkoret. Om det bevisas att denna sannolikhet är positiv, så finns det ett objekt med de önskade egenskaperna. Även om beviset använder sannolikheter, är den slutliga slutsatsen definitiv, utan någon tvetydighet.

Vanliga verktyg som används i den probabilistiska metoden inkluderar Markovs ojämlikhet , Chernovs ojämlikhet och Lovas lokala lemma .

Historik

Den mest kända tillämpningen av denna metod är förknippad med Erdős . Den probabilistiska metoden tillämpades dock redan innan Erdős arbete i denna riktning. Till exempel använde Seles 1943 metoden för att bevisa att det finns turneringar som innehåller ett stort antal Hamilton-cykler .

Exempel

Följande två exempel på tillämpningen av den probabilistiska metoden diskuteras i detalj i boken Evidence from the Book av Martin Aigner och Günther Ziegler .

Nedre gräns för Ramsey-numret

Vi måste bevisa förekomsten av en färgning i två färger (säg, röd och blå) av kanterna på en komplett graf med hörn (för inte särskilt stora värden på ) så att det inte finns någon fullständig monokromatisk subgraf med hörn (som är, med varje kant av samma färg). $n$ $n$ $r$

Vi kommer att välja färger slumpmässigt. Färgen på varje kant väljs oberoende med lika sannolikhet röd eller blå. Beräkna det förväntade antalet kompletta monokromatiska subgrafer med hörn enligt följande: $r$

För varje uppsättning av hörn i vår graf, definiera ett värde på 1 om varje kant slutar i samma färg, och 0 annars. Observera att antalet monokromatiska -subgrafer är summan över allt . $S$ $r$ $X(S)$ $S$ $r$ $X(S)$ $S$

För alla är förväntningen på sannolikheten att alla kanter i har samma färg. Och det betyder $S$ $\mu$ $X(S)$ ${r \choose 2}$ $S$

\mu =2\cdot 2^{-{r \choose 2)).

Faktorn 2 visas eftersom det finns två möjliga färger.

Detsamma gäller för alla möjliga delmängder med hörn. Så att den matematiska förväntan på summan över allt är lika ${\displaystyle {n \choose r))$ $r$ $X(S)$ $S$

M={n \choose r}\cdot \mu ={n \choose r}\cdot 2\cdot 2^{-{r \choose 2))

Summan av de matematiska förväntningarna är lika med förväntningarna på summan (oavsett om variablerna är oberoende ). Med andra ord , det finns det genomsnittliga antalet monokromatiska subgrafer i en slumpmässigt färgad graf. $M$ $r$

Antalet monokromatiska subgrafer i en slumpmässig färgning kommer alltid att vara ett heltal . Därför, om , då i minst en färg, får det inte finnas några fullständiga monokromatiska -subgrafer. $r$ $M<1$ $r$

Det vill säga om

2\cdot {n \choose r}<2^{r \choose 2},

sedan

R(r,r)>n

där anger Ramsey-numret för . I synnerhet växer den åtminstone exponentiellt i . $R(r,r)$ $r$ $R(r,r)$ $r$

Anteckningar

Ovanstående bevis ges av Erdős. [ett]
Denna metod ger inte ett explicit exempel på sådan färgning. Frågan om att beskriva ett visst exempel har varit öppen i mer än 50 år.

Konstruktion av en graf utan korta cykler med ett stort kromatiskt tal

Låt positiva heltal och ges . Vi måste bygga en graf med minst alla längdcykler och samtidigt är det kromatiska talet G minst . $g$ $k$ $G$ $g$ $k$

Vi fixar ett stort heltal . Betrakta en slumpmässig graf med hörn, där varje kant i existerar med sannolikhet p = n 1/ g −1 . Låt oss visa att följande två egenskaper håller med positiv sannolikhet $n$ $G$ $n$ $G$

Egenskap 1. innehåller högst cykler med längd mindre än . Mer exakt, sannolikheten att grafen inte har mer än cykler med längd mindre än tenderar till 1 som . $G$ $n/2$ $g$ $G$ $n/2$ $g$ $n\till\infty$

Bevis. Låta vara antalet cykler av längd mindre än . Antalet längdcykler i en komplett graf på med hörn är $X$ $g$ $i$ $n$

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

och var och en av dem ingår i med sannolikhet pi . Därför har vi genom Markovs ojämlikhet $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).

■

Egenskap 2. innehåller inte en oberoende uppsättning storlek . Mer exakt, sannolikheten för att en graf har en oberoende storleksuppsättning tenderar till 1 som . $G$ $\lceil {\tfrac {n}{2k))\rceil$ $G$ $\lceil {\tfrac {n}{2k))\rceil$ $n\till\infty$

Bevis. Låt beteckna storleken på den största oberoende uppsättningen i . Uppenbarligen har vi det $Y$ $G$

\Pr(Y\geq y)\leq {n \choose 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),

när

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

■

Eftersom det har dessa två egenskaper, kan vi extrahera det maximala antalet hörn från för att få en ny graf med hörn som endast innehåller längdcykler som mest . Vi ser att det har en oberoende storleksuppsättning . kan bara delas upp i åtminstone oberoende uppsättningar och har därför ett kromatiskt tal på minst . $G$ $n/2$ $G$ $G'$ $n'\geq n/2$ $g$ $G'$ $\lceil {\frac {n'}{k))\rceil$ $G'$ $k$ $k$

Anteckningar

Detta resultat förklarar varför det är en svår uppgift att beräkna det kromatiska numret för en graf. Även i frånvaro av lokala orsaker (som små cykler) kan det kromatiska talet vara godtyckligt stort.

Se även

Slumpmässig räkning

Litteratur

Aigner M. Ziegler G. Bevis från boken. Det bästa beviset från Euklids tid till våra dagar. - Förlaget "Laboratory of Knowledge" (tidigare "BINOM. Laboratory of Knowledge"), 2014. - ISBN 978-5-9963-2736-2 .

Alon N., Spencer J. Probabilistic method, Binom, 2007, sid. 320, 1100 exemplar. ISBN 978-5-94774-556-6

A.M. Raigorodsky . Grafer med stort kromatiskt tal och stor omkrets // Matem. upplysning , ser. 3. - 2016. - T. 20 . - S. 228-237 . (ryska)

På engelska

Erdős, P. Grafteori och sannolikhet (obestämd) // Canad. J. Math .. - 1959. - T. 11 , nr 0 . - S. 34-38 . - doi : 10.4153/CJM-1959-003-9 . Arkiverad från originalet den 18 juli 2011.

J. Matousek, J. Vondrak. Den probabilistiska metoden . föreläsningsanteckningar.

Alon, N och Krivelevich, M (2006). Extrem och probabilistisk kombinatorik

Fotnoter

↑ Erdös, P. Några anmärkningar om teorin om grafer. Tjur. amer. Matematik. soc. 53, (1947). 292–294.