Probabilistisk grafteori

Inom den probabilistiska grafteorin använder man sannolikhetsteoretiska metoder för att studera egenskaper hos grafer.

Historia

Under 1940- och 1950-talet publicerade Paul Erdős ett fåtal artiklar där han med sannolikhetsteoretiska metoder visade existensen av grafer med vissa egenskaper utan att faktiskt konstruera graferna. På detta sätt lyckades Erdős bland annat kraftigt förbättra de undre uppskattningarna för vissa klassiska Ramseytal. Frank Ramsey hade visat att givet ett naturligt tal s så existerar ett minsta tal R(s;2), sådant att det inte existerar någon graf med minst R(s;2) hörn där varken grafen eller komplementärgrafen innehåller en komplett graf av ordning s. Ramseys bevis ger exponentiella övre uppskattningar för talen R(s;2) i storleksordningen 4^s. Med probabilistisk grafteori lyckades Erdős också att ge exponentiella undre uppskattningar. För en slumpgraf med antalet n hörn och lika chans för att det finns eller inte finns en kant mellan två givna hörn, är sannolikheten att antingen alla eller inga kanter existerar mellan hörnen i någon s-delmängd av hörnmängden strikt mindre än 100 %, om

${n \choose s}2^{1-{s \choose 2}}<1$.

Orsaken är väsentligen att det bara finns ${n \choose s}$ s-delmängder av n-mängden av alla hörn (se binomialkoefficient), och att sannolikheten för att antingen alla eller inget av de ${s \choose 2}$ paren hörn i en given s-delmängd har kanter mellan sig är precis $2^{1-{s \choose 2}}$. (Man måste också visa att sannolikheterna inte är negativt korrelerade.) Från detta kan man se att R(s;2) växer minst i storleksordningen ${\sqrt {2}}^{s}$.

Under 1959 publicerade Erdős och Rényi en serie artiklar som lade grunden för mer systematiska studier av slumpgrafer.

Modeller för slumpgrafer

I den enklaste modellen för en slumpgraf G = (V,E) tänker man sig en fix (oföränderlig) hörnmängd V, men för varje tänkbar kant (det vill säga för varje tvådelmängd av hörn) att en stokastisk variabel avgör huruvida den kanten är med i grafen eller ej. Dessa variabler antages här oberoende och likafördelade.

Litteratur

• R. L. Graham, B. L. Rothschild, J. H. Spencer: Ramsey theory (2:a upplagan, 1990), ISBN 0-471-50046-1.