Probabilistisk metode

Den probabilistiske metode er en ikke -konstruktiv metode til at bevise eksistensen af et matematisk objekt med givne egenskaber. Anvendes mest i kombinatorik , men også i talteori , lineær algebra og calculus , samt i datalogi (såsom den probabilistiske afrundingsmetode ) og informationsteori .

Metoden består i at estimere sandsynligheden for, at et tilfældigt objekt fra en given klasse opfylder den ønskede betingelse. Hvis det bevises, at denne sandsynlighed er positiv, eksisterer der et objekt med de ønskede egenskaber. Selvom beviset bruger sandsynligheder, er den endelige konklusion bestemt, uden nogen tvetydighed.

Almindelige værktøjer, der bruges i den probabilistiske metode, omfatter Markovs ulighed, Chernovs ulighed og Lovas ' lokale lemma .

Historie

Den mest berømte anvendelse af denne metode er forbundet med Erdős . Den probabilistiske metode blev imidlertid anvendt allerede før Erdős arbejde i denne retning. For eksempel brugte Seles i 1943 metoden til at bevise, at der er turneringer , der indeholder et stort antal Hamilton-cykler .

Eksempler

De følgende to eksempler på anvendelsen af den probabilistiske metode diskuteres detaljeret i bogen Evidence from the Book af Martin Aigner og Günter Ziegler .

Nedre grænse for Ramsey-tallet

Vi er nødt til at bevise eksistensen af en farvning i to farver (f.eks. rød og blå) af kanterne på en komplet graf med hjørner (for ikke særlig store værdier af ), således at der ikke er nogen komplet monokromatisk subgraf med hjørner (det er, med hver kant af samme farve). $n$ $n$ $r$

Vi vil vælge farver tilfældigt. Farven på hver kant vælges uafhængigt med lige stor sandsynlighed rød eller blå. Beregn det forventede antal komplette monokromatiske undergrafer med toppunkter som følger: $r$

For ethvert sæt hjørner i vores graf skal du definere en værdi på 1, hvis hver kant ender i samme farve, og 0 ellers. Bemærk, at antallet af monokromatiske -undergrafer er summen over alt . $S$ $r$ $X(S)$ $S$ $r$ $X(S)$ $S$

For enhver , er forventningen til sandsynligheden for, at alle kanter i har samme farve. Og det betyder $S$ $\mu$ $X(S)$ ${r \choose 2}$ $S$

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

Faktoren 2 vises, fordi der er to mulige farver.

Det samme gælder for enhver af de mulige delmængder med toppunkter. Så den matematiske forventning om summen over det hele er lig ${\displaystyle {n \choose r))$ $r$ $X(S)$ $S$

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

Summen af de matematiske forventninger er lig med forventningen til summen (uanset om variablerne er uafhængige ). Med andre ord er der det gennemsnitlige antal monokromatiske undergrafer i en tilfældigt farvet graf. $M$ $r$

Antallet af monokromatiske subgrafer i en tilfældig farve vil altid være et heltal . Derfor, hvis , så i mindst én farve, må der ikke være fuldstændige monokromatiske -subgrafer. $r$ $M<1$ $r$

Det vil sige, hvis

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

derefter

R(r,r)>n

hvor angiver Ramsey-nummeret for . Især vokser den i det mindste eksponentielt i . $R(r,r)$ $r$ $R(r,r)$ $r$

Noter

Ovenstående bevis er givet af Erdős. [en]
Denne metode giver ikke et eksplicit eksempel på sådan farvning. Spørgsmålet om at beskrive et bestemt eksempel har været åbent i mere end 50 år.

Konstruktion af en graf uden korte cyklusser med et stort kromatisk tal

Lad positive heltal og blive givet . Vi skal bygge en graf med mindst alle længdecyklusser , og samtidig er det kromatiske tal G mindst . $g$ $k$ $G$ $g$ $k$

Vi fikser et stort heltal . Betragt en tilfældig graf med toppunkter, hvor hver kant i eksisterer med sandsynlighed p = n 1/ g −1 . Lad os vise, at de følgende to egenskaber holder med positiv sandsynlighed $n$ $G$ $n$ $G$

Ejendom 1. indeholder højst cyklusser af længde mindre end . Mere præcist tenderer sandsynligheden for, at grafen ikke har mere end cyklusser af længde mindre end , til 1 som . $G$ $n/2$ $g$ $G$ $n/2$ $g$ $n\til\infty$

Bevis. Lade være antallet af cyklusser af længde mindre end . Antallet af længdecyklusser i en komplet graf på med toppunkter er $x$ $g$ $jeg$ $n$

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

og hver af dem er indeholdt i med sandsynlighed p i . Derfor har vi ved Markovs ulighed $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).

■

Ejendom 2. indeholder ikke et selvstændigt sæt størrelser . Mere præcist er sandsynligheden for, at en graf har et uafhængigt størrelsessæt, en tendens til 1 som . $G$ $\lceil {\tfrac {n}{2k))\rceil$ $G$ $\lceil {\tfrac {n}{2k))\rceil$ $n\til\infty$

Bevis. Lad betegne størrelsen af det største uafhængige sæt i . Det har vi åbenbart $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),

hvornår

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

■

Da det har disse to egenskaber, kan vi udtrække det maksimale antal hjørner fra for at få en ny graf med hjørner, der højst indeholder længdecyklusser . Vi kan se, der har et uafhængigt størrelsessæt . kan kun opdeles i mindst uafhængige sæt, og har derfor et kromatisk tal på mindst . $G$ $n/2$ $G$ $G'$ $n'\geq n/2$ $g$ $G'$ $\lceil {\frac {n'}{k))\rceil$ $G'$ $k$ $k$

Noter

Dette resultat forklarer, hvorfor det er en vanskelig opgave at beregne det kromatiske tal for en graf. Selv i fravær af lokale årsager (såsom små cyklusser), kan det kromatiske tal være vilkårligt stort.

Se også

Tilfældig optælling

Litteratur

Aigner M. Ziegler G. Beviser fra bogen. Det bedste bevis fra Euklids tid til i dag. - Forlaget "Laboratory of Knowledge" (tidligere "BINOM. Laboratory of Knowledge"), 2014. - ISBN 978-5-9963-2736-2 .

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

A. M. Raigorodsky . Grafer med stort kromatisk tal og stor omkreds // Matem. oplysning , ser. 3. - 2016. - T. 20 . - S. 228-237 . (Russisk)

På engelsk

Erdős, P. Grafteori og sandsynlighed (ubestemt) // Canad. J. Math .. - 1959. - T. 11 , nr. 0 . - S. 34-38 . - doi : 10.4153/CJM-1959-003-9 . Arkiveret fra originalen den 18. juli 2011.

J. Matousek, J. Vondrak. Den probabilistiske metode . forelæsningsnotater.

Alon, N og Krivelevich, M (2006). Ekstrem og probabilistisk kombinatorik

Fodnoter

↑ Erdös, P. Nogle bemærkninger til teorien om grafer. Tyr. amer. Matematik. soc. 53, (1947). 292-294.