Náhodný graf

V matematiky , je náhodný graf je graf , který je generován pomocí náhodného procesu . První model náhodných grafů popularizovali Paul Erdős a Alfréd Rényi v sérii článků publikovaných v letech 1959 až 1968.

Dva základní modely Erdőse a Rényiho

Erdősův a Rényiho model ve skutečnosti spojuje dva modely, formálně odlišné, ale úzce související. U obou modelů

množina vrcholů je ${1, 2, 3, ..., n }$ označená následujícím ; ${\ displaystyle \ [\! [n] \!]}$
potenciálně přítomné hrany jsou $n ( N -1) / 2$ Dvouprvkové části ; sada těchto okrajů je někdy uvedena. Bude však třeba poznamenat $J.$ pro typografické pohodlí a pro soulad s článkem o Harrisově nerovnosti . ${\ displaystyle \ [\! [n] \!]}$ ${\ displaystyle {[\! [n] \!] \ vyberte 2}.}$
náhodný graf je tedy neorientovaný a nemá žádné smyčky ani více hran .

Binomický náhodný graf

V tomto modelu je často každá z hran $n$ $($ $n$ $-1) / 2$ přítomna s pravděpodobností $p$ , chybí s pravděpodobností $1-$ $p$ , bez ohledu na stav ostatních hran. Případ $p$ $= 0,5$ byla studována Erdős již v roce 1947. Počet $N$ $p$ hran následuje binomické rozdělení parametrů $n$ $($ $n$ $-1) / 2$ a $p$ . ${\ displaystyle \ mathbb {G} (n, p),}$ ${\ displaystyle \ mathbb {G} (n, p)}$

Jednotný náhodný graf

V tomto modelu, často známém, je podmnožina M hran rovnoměrně vybrána mezi $n$ $($ $n$ $-1) / 2$ možných hran. Když má graf G s n vrcholy M hrany, je pravděpodobnost G dána vztahem ${\ displaystyle \ mathbb {G} (n, M),}$

{\ displaystyle \ mathbb {P} (G) \ = \ {\ frac {1} {{n \ vyberte 2} \ zvolte M}}.}

Toto je model, který je studován hlavně v sérii klíčových článků publikovaných Erdősem a Rényim v letech 1959 až 1968. ${\ displaystyle \ mathbb {G} (n, M)}$

Dva náhodné procesy s hodnotami grafu

Můžeme začít z grafu bez hran, tedy zcela odpojených, a přidat hranu nakreslenou náhodně jednotně, pak další atd. , bez výměny. Získáme tak rostoucí posloupnost (ve smyslu zahrnutí množiny hran), $1 +$ $n$ $($ $n$ $-1) / 2$ náhodných grafů, které tvoří diskrétní proces s hodnotami v sadě grafů . Každý člen v pořadí je jednotný náhodný graf definovaný v předchozí části. Výhodou této konstrukce je vidět různé náhodné grafy s různými parametry M koexistovat na stejném pravděpodobnostním prostoru a být schopen porovnat jejich charakteristiky, nikoli průměrně nebo zákonem, ale pro každý prvek ω uvažovaného pravděpodobnostního prostoru. . To umožňuje uvažovat spojením. ${\ displaystyle \ {\ mathbb {G} (n, M) \} _ {0 \ leq M \ leq n (n-1) / 2},}$
Můžeme také spojit s každou hranu e z J náhodná proměnná $T e$ , hmotnosti okraje tak, že se rodina $( T E ) e \in J$ je rodina náhodných proměnných lid, například s jednotným zákonem o l ' interval [0, 1]. Potom označíme graf tvořený hranami, jejichž váha je menší než p . U každé hrany se to stane s pravděpodobností ${\ displaystyle \ mathbb {G} (n, p)}$

{\ displaystyle \ mathbb {P} (T_ {e} \ leq p) \ = \ p.}

Získáváme tak rostoucí rodinu náhodných grafů, které tvoří kontinuální časový proces, s hodnotami v sadě grafů. Tato rodina se zvětšuje ve smyslu zahrnutí množiny hran: hrana e přítomná v je také přítomna v od. Každý člen rodiny grafů je binomický náhodný graf definovaný dříve.

{\ displaystyle \ {\ mathbb {G} (n, p) \} _ {0 \ leq p \ leq 1},}

{\ displaystyle \ mathbb {G} (n, p)}

{\ displaystyle \ mathbb {G} (n, p + \ varepsilon), \ \ varepsilon> 0,}

{\ displaystyle \ {T_ {e} \ leq p \} \ \ Rightarrow \ \ {T_ {e} \ leq p + \ varepsilon \}.}

Metafora. Můžeme si představit vrcholy grafu jako n ostrovů na jezeře, komunikujících pomocí lávek (hran e ), ponořených v příslušných hloubkách $T e$ pod vodní hladinou. Pokud jezero postupně vypouští svoji vodu, uvidíme, jak se mosty postupně vynoří a vytvoří se související součásti seskupující se stále více ostrovů.

Vazby mezi těmito dvěma modely

Na základě centrální limitní věty nebo Hoeffdingovy nerovnosti je binomický zákon velmi koncentrovaný kolem jeho očekávání. Přesněji řečeno, počet hran $N p$ náhodného práva grafu je tedy velmi blízko , zejména pokud tato poslední množství je velký před n : opravdu, ${\ displaystyle \ mathbb {G} (n, p)}$ ${\ displaystyle {\ hat {M}} = \ vlevo \ lfloor p \ {n \ zvolit 2} \ vpravo \ rfloor}$ ${\ hat {M}}$

{\ displaystyle \ forall t> 0, \ qquad \ mathbb {P} \ left (\ left | N_ {p} - {\ hat {M}} \ right | \ geq tn \ right) \ \ leq \ 2 \, \ mathrm {e} ^ {- 2t ^ {2}}.}

Kromě toho je podmíněné rozdělení s vědomím, že $N$ $p$ $= M$ je právě z tohoto důvodu, je-li $M$ blízko , nebo ekvivalentně, pokud ${\ displaystyle \ \ mathbb {G} (n, p)}$ ${\ displaystyle \ mathbb {G} (n, M).}$ ${\ hat {M}}$

{\ displaystyle p \ simeq {\ frac {2M} {n (n-1)}},}

to je obecně přijímáno (a často projevuje), že oba modely a mají velmi podobné vlastnosti. ${\ displaystyle \ mathbb {G} (n, p)}$ ${\ displaystyle \ mathbb {G} (n, M)}$

Jde dále, označíme $T ( K )$ na k -tý hodnoty sekvence , jakmile tato poslední sekvence je umístěna ve vzestupném pořadí: sekvence se nazývá posloupnost pořadí statistiky sekvence Když p má náhodná hodnota $T$ $($ $M$ $)$ , pak je přesně Abychom potvrdili předchozí pozorování, všimněte si, že $T$ $($ $M$ $)$ je velmi blízko v tom smyslu, že v důsledku slavných výsledků Donskera a Kolmogorovova pravděpodobnosti ${\ displaystyle (T_ {e}) _ {e \ v J}}$ ${\ displaystyle (T _ {(k)}) _ {1 \ leq e \ leq n (n-1) / 2}}$ ${\ displaystyle (T_ {e}) _ {e \ v J}.}$ ${\ displaystyle \ mathbb {G} (n, T _ {(M)})}$ ${\ displaystyle \ mathbb {G} (n, M).}$ ${\ displaystyle 2M / n (n-1),}$

{\ displaystyle \ varphi _ {n} (x) = \ mathbb {P} \ vlevo (\ sup _ {1 \ leq M \ leq n (n-1) / 2} \ vlevo \ {| T _ {(M )} - {\ tfrac {2M} {n (n-1)}} | \ right \} \ geq {\ tfrac {x {\ sqrt {2}}} {n}} \ right)}

spokojený

{\ displaystyle \ exp (-2x ^ {2}) \ \ leq \ \ liminf _ {n} \ varphi _ {n} (x) \ \ leq \ \ limsup _ {n} \ varphi _ {n} (x ) \ \ leq \ 2 \ sum _ {r = 1} ^ {+ \ infty} (- 1) ^ {r-1} \ exp (-2r ^ {2} x ^ {2}),}

1 st a 4 th podmínky pohody ocasy distribuce z Rayleigh a Kolmogorov zákony , v daném pořadí: v souhrnu, supremum (pokud M liší) chyb je řádově 1 / n . ${\ displaystyle | T _ {(M)} - 2M / n (n-1) |}$

Řád a růst

Graf může být viděn jako součást nastavené J hran, takže pravděpodobnost prostor je zde Q všechny části J , které mohou někdy identifikují ${0,1} J$ . Tato identifikace je obzvláště užitečná, když chceme použít Harrisovu nerovnost .

Zahrnutí je relace částečného řádu na Ω.
Jako obvykle se říká , že mapa X definovaná na Ω se skutečnými hodnotami se zvyšuje, pokud

{\ displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \} \ quad \ Rightarrow \ quad \ {X (\ omega) \ leq X (\ omega ^ {\ prime}) \}.}

Část A Ω se říká, že se zvyšuje, pokud

{\ displaystyle \ {\ omega \ leq \ omega ^ {\ prime} \ {\ text {a}} \ \ omega \ v A \} \ quad \ Rightarrow \ quad \ {\ omega ^ {\ prime} \ v A \}.}

Ekvivalentně se říká , že část A Ω se zvyšuje, pokud se zvyšuje její indikátorová funkce .

Vlastnost rozpadu aplikace nebo části má analogickou definici.

Příklady:

Mezi vlastnostmi a parametry grafu

propojenost se zvyšuje, tj. část A Ω složená ze všech připojených grafů je rostoucí částí Ω: pokud přidáme hranu k připojenému grafu, takto získaný graf je stále připojen;
rovinnosti klesá: v případě, odstraníme okraj z rovinného grafu, se takto získaný graf je ještě rovinný;
chromatické číslo se zvyšuje;
počet stabilita klesá;
vlastnost bez trojúhelníků klesá.

Máme následující nerovnost:

Harris nerovnost - V rámci binomického náhodného grafu ,

to znamená dvě náhodné proměnné X a Y rostoucí na Ω. Tak

{\ displaystyle \ mathbb {E} [XY] \ geq \ mathbb {E} \ doleva [X \ doprava] \ mathbb {E} [Y] \,;}

to znamená dvě rostoucí části A a B Ω. Tak

{\ displaystyle \ mathbb {P} (A \ cap B) \ geq \ mathbb {P} (A) \ mathbb {P} (B).}

Poznámky:

To znamená, že mezi příslušnými proměnnými existuje pozitivní korelace , protože první nerovnost můžeme přeformulovat v následující podobě pomocí kovariance :

{\ displaystyle {\ text {Cov}} \ vlevo (X, Y \ vpravo) \ \ geq \ 0.}

Nerovnost platí také pro zmenšující se proměnné nebo části, ale význam nerovností se mění, když mají dané proměnné nebo části opačné významy monotónnosti.

Propojenost

Prahová hodnota pro připojení

Věta (Erdős, Rényi, 1960) - Nechť $a n = np ( n ) - ln n$ , nebo znovu:

{\ displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}}.}

Pokud tedy ${\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}$ ${\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ je ~ příbuzný} \ right) = 1.}$
Pokud tedy ${\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ je ~ příbuzný} \ right) = 0.}$

Říkáme, že $ln ( n ) / n$ je úzký práh pro vlastnost připojení, úzkost odkazující na skutečnost, že vlastnost je uspokojena, i když má sklon k nekonečnu přísně méně rychle než $rok$ ${\ displaystyle \ ln n.}$

Demonstrace

Dáme si náhodný graf G n se zákonem a náhodný graf se zákonem. Věta vyplývá z dvojexponenční věty , která sama vyplývá z výčtu izolovaných bodů provedeného v následující části. Konektivita je rostoucí vlastnost , proto jakmile je n dostatečně velká na to ${\ displaystyle \ mathbb {G} \ doleva (p (n), n \ doprava)}$ ${\ displaystyle {\ tilde {G}} _ {n}}$ ${\ displaystyle \ mathbb {G} \ left ({\ tilde {p}} (n), n \ right).}$

{\ displaystyle p (n) \ = \ {\ frac {\ ln n} {n}} \, + \, {\ frac {a_ {n}} {n}} \ quad \ geq \ quad {\ frac { \ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {n}} \ = \ {\ tilde {p}} (n),}

také máme

{\ displaystyle \ mathbb {P} \ left (G_ {n} \ mathrm {~ je ~ příbuzný} \ right) \ geq \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm { ~ je ~ příbuzný} \ right).}

Dokonce i při konstrukci a používání stejných jednotných proměnných iid ve stejném prostoru pravděpodobnosti Ω, jak je popsáno v části „Graf dvou hodnot náhodných procesů“ , máme pro všechny ω z Ω, $G_ {n}$ ${\ displaystyle {\ tilde {G}} _ {n}}$ ${\ displaystyle (U_ {e}) _ {e \ v J}}$

{\ displaystyle G_ {n} (\ omega) \ supset {\ tilde {G}} _ {n} (\ omega),}

proto

{\ displaystyle \ left \ {{\ tilde {G}} _ {n} (\ omega) {\ text {souvisí}} \ right \} \ rightarrow \ left \ {G_ {n} (\ omega) \ mathrm {~ je ~ související} \ vpravo \},}

{\ displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ je ~ příbuzný} \ right) \ leq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ je ~ příbuzný} \ right).}

Pokud z toho vyplývá, že pro jakékoliv reálné číslo c , ${\ displaystyle \ lim _ {n} a_ {n} = + \ infty,}$

{\ displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ je ~ příbuzný} \ right) \ geq \ mathrm { e} ^ {- \ mathrm {e} ^ {- c}},}

nebo dokonce

{\ displaystyle \ liminf _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ je ~ příbuzný} \ right) \ geq \ sup \ left \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ right \} \ = \ 1.}

Na druhou stranu, pokud pak, pro n dostatečně velké, budeme mít, pro všechny ω , a ${\ displaystyle \ lim _ {n} a_ {n} = - \ infty,}$ ${\ displaystyle G_ {n} (\ omega) \ podmnožina {\ tilde {G}} _ {n} (\ omega),}$

{\ displaystyle \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ je ~ příbuzný} \ right) \ geq \ mathbb {P} \ left (G_ {n} \ mathrm { ~ je ~ příbuzný} \ right).}

Takže pro jakékoli reálné číslo c ,

{\ displaystyle \ limsup _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left (p (n), n \ right) \ mathrm {~ je ~ příbuzný} \ right) \ leq \ inf \ left \ {\ mathrm {e} ^ {- \ mathrm {e} ^ {- c}} \, | \, c \ in \ mathbb {R} \ right \} \ = \ 0.}

Výčet izolovaných bodů

Je snazší (pravděpodobnější) uspět v řezání spojení n - 1 mezi bodem a jeho doplňkem, než spojení k ( n - k ) mezi skupinou bodů k a jeho doplňkem, protože funkce $f ( k ) = k ( n - k ) se$ zvyšuje velmi rychle kolem 1, proto, jak se k zvyšuje, mnohem více hran k ořezání a mnohem nižší pravděpodobnost, že je všechny úspěšně odříznete. Jako důsledek, s výběrem parametru p provedeného výše, bude graf G ( n , p ) nepřipojený „téměř jen“, pokud má izolované body, v tom smyslu, že pravděpodobnost připojení je velmi blízká pravděpodobnost, že nebudeme mít izolované body, což se přibližně $rovná$ $e$ $-e$ $-$ $c$ Ve skutečnosti máme následující výsledek: ${\ displaystyle \ mathbb {P} \ vlevo (X_ {n} = 0 \ vpravo),}$

Izolované body (Erdős, Rényi, 1960). - Předpokládejme to

{\ displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {ne}}.}

Poté počet $X n$ izolovaných bodů grafu konverguje zákonem k Poissonově rozdělení parametru $e$ $-$ $c$ . ${\ displaystyle G \ left ({\ tilde {p}} (n), n \ right)}$

Demonstrace

V následujícím textu budeme zkracovat v a my představovat ${\ displaystyle G \ left ({\ tilde {p}} (n), n \ right)}$ ${\ displaystyle {\ tilde {G}} _ {n},}$

{\ displaystyle \ mu = \ mathrm {e} ^ {- c}.}

Nechť $X n$ je počet izolovaných bodů Víme to ${\ displaystyle {\ tilde {G}} _ {n}.}$

{\ displaystyle X_ {n} = Y_ {1} + Y_ {2} + \ tečky + Y_ {n},}

nebo

{\ displaystyle Y_ {i} = 1 _ {\ mathrm {the ~ vertex ~} i \ mathrm {~ is ~ isol {\ akutní {e}}}}.}

Použijme metodu faktorových momentů. Nechť $I n , A$ je sada injekcí v Pro všechny $[\! [1, n] \!]$ $NA.$ ${\ displaystyle r \ geq 1,}$

{\ displaystyle (X_ {n}) _ {r} = (Y_ {1} + Y_ {2} + \ tečky + Y_ {n}) _ {r} = \ součet _ {\ varphi \ v I_ {r, [\! [1, n] \!]}} \ \ Prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}.}

Podmínky předchozího součtu se skutečně objevují v expanzi, ale kromě těchto podmínek tato expanze přináší mnoho dalších termínů, které zjevně kolidují. Opravdu ${\ displaystyle \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)}}$ ${\ displaystyle (Y_ {1} + Y_ {2} + \ tečky + Y_ {n}) _ {r},}$

{\ displaystyle E = \ left \ {a \ in [\! [1, n] \!] \, | \, Y_ {a} = 1 \ right \}.}

Tak

{\ displaystyle \ forall \, \ varphi \ v I_ {r, [\! [1, n] \!]}, \ qquad \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i) } = 1 _ {\ varphi \ v I_ {r, E}},}

proto

{\ displaystyle \ sum _ {\ varphi \ v I_ {r, [\! [1, n] \!]}} \ \ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ = \ | I_ {r, E} | \ = \ (| E |) _ {r} \ = \ (X_ {n}) _ {r}.}

Symetrií navíc

{\ displaystyle \ mathbb {E} \ left [\ prod _ {i = 1} ^ {r} Y _ {\ varphi (i)} \ right] \ = \ \ mathbb {E} \ left [\ prod _ { i = 1} ^ {r} Y_ {i} \ right] = (1 - {\ tilde {p}} (n)) ^ {r (n-1) -r (r-1) / 2},}

kde $r ( n -1)$ je počet hran potenciálně vyplývajících z vrcholu E a kde $r ( r -1) / 2$ je počet hran mezi dvěma vrcholy E , tj. ty, které se v celkovém $r ( n -1)$ počítají dvojnásobně . Tak

{\ displaystyle {\ begin {aligned} \ mathbb {E} \ left [(X_ {n}) _ {r} \ right] & = (n) _ {r} (1 - {\ tilde {p}} ( n)) ^ {r (n-1) -r (r-1) / 2} \\ & \ simeq n ^ {r} (1 - {\ tilde {p}} (n)) ^ {r (n -1)} \\ & = \ left (n (1 - {\ tilde {p}} (n)) ^ {n-1} \ right) ^ {r} \\ & \ simeq \ mu ^ {r} . \ end {zarovnáno}}}

Proto metodou momentů $X n$ konverguje zákonem na Poissonovo rozdělení s parametrem μ a

{\ displaystyle \ lim \ mathbb {P} \ vlevo (X_ {n} = 0 \ vpravo) \ = \ \ mathrm {e} ^ {- \ mu} \ = \ \ mathrm {e} ^ {- \ mathrm { e} ^ {- c}}.}

Tato věta je nápadným znázorněním rybího paradigmatu , že když představuje mnoho příležitostí pozorovat událost vzácnou ( tj. Nepravděpodobnou), pak se celkový počet skutečně pozorovaných vzácných událostí řídí Poissonovým zákonem .

Dvojexponenciální věta

Erdős a Rényi odvozují přesnější výsledek než vlastnost úzkého prahu:

Dvojexponenciální věta (Erdős, Rényi, 1960) - Předpokládejme to

{\ displaystyle {\ tilde {p}} (n) \ = \ {\ frac {\ ln n} {n}} + {\ frac {c} {n}} + {\ frac {\ varepsilon (n)} {ne}}.}

Tak

{\ displaystyle \ lim _ {n} \ mathbb {P} \ left (\ mathbb {G} \ left ({\ tilde {p}} (n), n \ right) \ mathrm {~ je ~ příbuzný) \ right ) = e ^ {- e ^ {- c}}.}

Demonstrace Pokud je bez izolovaného bodu, a pak je malá šance, že je to něco jiného než spojeného (srov. Spencer, 10 přednášek v náhodných grafech ). Nechť je B součástí a nechť k je jeho kardinál. Označme událost „ B je připojená součást “. Na událost lze pohlížet jako na (disjunktní) sjednocení

k

k

-2

podmnožin pravděpodobností

{\ displaystyle X_ {n} = 0,}

{\ displaystyle {\ tilde {G}} _ {n}}

{\ displaystyle {\ tilde {G}} _ {n}}

[\! [1, n] \!]

{\ displaystyle {\ mathcal {C}} _ ​​{B}}

{\ displaystyle {\ tilde {G}} _ {n}}

{\ displaystyle {\ mathcal {C}} _ ​​{B}}

{\ displaystyle {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)},}

což vede k následujícímu nárůstu:

{\ displaystyle \ mathbb {P} ({\ mathcal {C}} _ ​​{B}) \ \ leq \ k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)}.}

Zde označuje počet možných rozpětí stromů pro připojený graf, jehož vrcholy by byly prvky B , nebo dokonce ekvivalentním způsobem počet možných voleb rodiny hran k- 1, díky nimž je množina B příbuzná. Kromě toho je pravděpodobnost, že k -1 hrany uvažovaného rozpětí stromu jsou skutečně přítomné, a je pravděpodobnost, že není přítomna žádná hrana spojující vrchol B s vrcholem B c , taková, že B nejenže je spojena , ale také maximální mezi propojenými částmi grafu. ${\ displaystyle k ^ {k-2}}$ ${\ displaystyle {\ tilde {p}} (n) ^ {k-1}}$ ${\ displaystyle (1 - {\ tilde {p}} (n)) ^ {k (nk)}}$

Událost

{\ displaystyle D_ {n} = \ {X_ {n} = 0 \ mathrm {~ mais ~} {\ tilde {G}} _ {n} \ mathrm {~ n} ^ {\ prime} \ mathrm {est ~ nesouvisí ~ \}}

kontrolovány

{\ displaystyle D_ {n} \ podmnožina \ bigcup _ {2 \ leq | B | \ leq n / 2} {\ mathcal {C}} _ ​​{B}.}

Ve skutečnosti, na základě hypotézy D n , má několik připojených zařízení, tedy nejmenší z nich (ve smyslu počtu vrcholů) má nejvýše n / 2 vrcholy, ale tato nejmenší připojené zařízení má alespoň dva vrcholy, protože $X$ $n$ $= 0$ . Tak ${\ displaystyle {\ tilde {G}} _ {n}}$

{\ displaystyle {\ begin {aligned} \ mathbb {P} (D_ {n}) & \ leq \ sum _ {2 \ leq | B | \ leq n / 2} \ mathbb {P} ({\ mathcal {C }} _ {B}) \\ & \ leq \ sum _ {2 \ leq k \ leq n / 2} {n \ vyberte k} k ^ {k-2} {\ tilde {p}} (n) ^ {k-1} (1 - {\ tilde {p}} (n)) ^ {k (nk)} \\ & \ leq \ sum _ {2 \ leq k \ leq n / 2} u_ {k}. \ end {zarovnáno}}}

Pro $α > 0$ však

{\ displaystyle {\ begin {zarovnáno} u_ {2} & \ leq n ^ {- 1+ \ alpha} \, \ ln n \ end {zarovnáno}}}

Jakmile

{\ displaystyle \ ln n \ geq \ max \ left [c + \ varepsilon (n) \ ,, (- 2c-2 \ varepsilon (n) +4 {\ tilde {p}} (n)) / \ alpha \ správně].}

Stejně jako připojená komponenta o velikosti větší než 2 je mnohem méně pravděpodobná než připojená komponenta o velikosti 1, připojená komponenta o velikosti větší než 3 je mnohem méně pravděpodobná než připojená komponenta o velikosti 2, což má za následek

Vlastnost - Když n má sklon k nekonečnu

{\ displaystyle u_ {2} (n) \ \ gg \ \ součet _ {3 \ leq k \ leq n / 2} u_ {k} (n).}

Některé poněkud bolestivé výpočty, aniž by byly upřímně obtížné, vedou k tomuto výsledku.

Demonstrace

Výše uvedená vazba pro $u 2 ( n )$ není jen horní mezí , ale ve skutečnosti dává řádově velikost $u 2 ( n )$ . Pokud jde o zbytek částky, musíme ji rozdělit na dvě části, než zvýšíme každou ze dvou částí:

{\ displaystyle {\ begin {zarovnáno} {\ frac {u_ {k + 1}} {u_ {k}}} & = (nk) \, (1 + {\ tfrac {1} {k}}) ^ { k-2} \, {\ tilde {p}} (n) \ times (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \\ & = (nk) \, ( e + {\ hat {\ varepsilon}} (k)) \, {\ tilde {p}} (n) \ times (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ \ & \ leq {\ hat {c}} \, \ ln n \ (1 - {\ tilde {p}} (n)) ^ {n-2k-1} \ end {zarovnáno}}}

nebo

{\ displaystyle \ forall n, k, \ quad {\ hat {c}} \ geq (e + {\ hat {\ varepsilon}} (k)) \, {\ frac {n {\ tilde {p}} ( n)} {\ ln n}}.}

Pro a ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}$ ${\ displaystyle k \ leq \ beta n,}$

{\ displaystyle {\ begin {zarovnáno} {\ frac {u_ {k + 1}} {u_ {k}}} & \ leq {\ hat {c}} \, \ ln n \ \ exp \ left [- { \ tilde {p}} (n) (n-2k-1) \ right] \\ & \ leq {\ hat {c}} n ^ {- \ gamma} \ ln n, \ end {zarovnáno}}}

Jakmile

{\ displaystyle \ ln n \ geq {\ frac {{\ tilde {p}} (n) + (c + \ varepsilon (n)) (2 \ beta -1)} {1-2 \ beta - \ gamma} }.}

Proto pro dostatečně velké n klesá rychleji než exponenciální posloupnost rozumu, když a ${\ displaystyle u_ {k}}$ ${\ displaystyle {\ hat {c}} n ^ {- \ gamma} \ ln n,}$ ${\ displaystyle 2 \ leq k \ leq 1+ \ beta n,}$

{\ displaystyle \ sum _ {k = 2} ^ {1+ \ beta n} u_ {k} \ \ leq \ {\ frac {u_ {2}} {1 - {\ hat {c}} n ^ {- \ gamma} \ ln n}} \ \ leq \ 2n ^ {- 1+ \ alpha} \, \ ln n.}

Navíc pro c můžeme najít c a ρ pozitivní, takže pro všechny ${\ displaystyle 0 <\ alpha <1/4,}$ ${\ displaystyle n \ geq 1,}$

{\ displaystyle {\ begin {zarovnáno} u_ {n / 2} & \ leq c \, \ rho ^ {n} \, n ^ {- \ alpha n}. \ end {zarovnáno}}}

Pro a ${\ displaystyle 0 <\ beta <(1- \ gamma) / 2 <0,5,}$ ${\ displaystyle k \ geq \ beta n,}$

{\ displaystyle {\ begin {aligned} {\ frac {u_ {k-1}} {u_ {k}}} & \ leq {\ frac {d} {\ ln n}} \ \ exp \ left [{\ tilda {p}} (n) (n-2k + 1) \ right] \\ & \ leq {\ frac {d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}} { \ ln n}} \\ & \ leq d \, n ^ {(1-2 \ beta) ^ {2} / \ gamma}, \ end {zarovnáno}}}

jakmile je n dostatečně velké. Proto pro a dostatečně blízko k 0,5, dostatečně blízko k 1, ${\ Displaystyle n / 2 \ geq k \ geq \ beta n,}$ $\beta$ ${\ displaystyle (1-2 \ beta) / \ gamma}$

{\ displaystyle {\ begin {aligned} - \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma) & <0, \\ {\ frac {u_ {k}} {u_ {n / 2}}} & \ leq d ^ {(1-2 \ beta) n / 2} n ^ {n (1-2 \ beta) ^ {3} / 2 \ gamma}, \\ u_ {k} & \ leq c \, {\ tilde {\ rho}} ^ {n} \, n ^ {(- \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma)) n}, \ end { zarovnaný}}}

{\ displaystyle \ sum _ {k = \ beta n} ^ {n / 2} u_ {k} \ \ leq \ c \, {\ hat {\ rho}} ^ {n} \, n ^ {(- \ alpha + ((1-2 \ beta) ^ {3} / 2 \ gamma)) n} \ \ ll \ u_ {2}.}

Proto

{\ displaystyle \ lim _ {n} \ mathbb {P} \ left ({\ tilde {G}} _ {n} \ mathrm {~ je ~ příbuzný} \ right) = \ lim _ {n} \ mathbb {P } \ left (X_ {n} = 0 \ right).}

Označme $T n$ první okamžik t, kde je připojen graf : ${\ displaystyle \ mathbb {G} \ doleva (t, n \ doprava)}$

{\ displaystyle T_ {n} \ = \ \ inf \ left \ {t \ geq 0 \ | \ \ mathbb {G} (t, n) \ mathrm {~ je ~ příbuzný} \ right \},}

aby

{\ displaystyle \ left \ {\ mathbb {G} \ left (t, n \ right) \ mathrm {~ je ~ příbuzný} \ right \} \ quad \ rightarrow \ quad \ left \ {T_ {n} \ leq t \ right \} \ quad \ Rightarrow \ quad \ left \ {\ forall \ varepsilon> 0, \ quad \ mathbb {G} \ left (t + \ varepsilon, n \ right) \ mathrm {~ is ~ related} \ right \}.}

Potom můžeme vidět dvojexponenciální teorém jako výsledek asymptotické expanze $T n$ : je-li $Z n$ definován následujícím vztahem:

{\ displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ {\ frac {Z_ {n}} {n}},}

pak dvojexponenční věta uvádí, že $Z n$ konverguje v právu k distribuci Gumbela , což by se dalo v pravděpodobnostní verzi notace Landau přeložit :

{\ Displaystyle T_ {n} \ = \ {\ frac {\ ln n} {n}} \ + \ \ Theta \ vlevo ({\ frac {1} {n}} \ vpravo).}

Nekonečný náhodný graf

Erdős a Rényi zobecnili binomický model na případ spočítatelného nekonečného grafu , ukazující, že jsme pak získali ( téměř jistě ) graf mající vlastnosti univerzálnosti (obsahující zejména jakýkoli konečný nebo spočetný graf jako podgraf ); tento graf byl znovuobjeven několikrát a je nejčastěji známý jako Rado graf .

Podívejte se také

Poznámky

První článek, publikovaný v roce 1959 , je „On Random Graphs I“, Publ. Matematika. Debrecen 6, 290.
(in) P. Erdős , „ Některé poznámky k teorii grafů “ , Bull. Hořký. Matematika. Soc. , sv. 53, n O 4,1947, str. 292-294 ( číst online ). Tento článek je často považován za počátek „pravděpodobnostní metody“ pro studium nenáhodných grafů, zejména pro Ramseyovu teorii .
Souvislosti viz (in) Mr. Karoński Ruciński and A., „The Origins of the theory of random graphs“ , in The Mathematics of Paul Erdős , Berlin, Springer al. "Kombinace algoritmů." „( N O 13),1997, str. 311-336.
Další podrobnosti viz Janson, Łuczak a Ruciński 2000 , kap. 2, „Exponenciálně malé pravděpodobnosti“.
Viz Janson, Łuczak a Ruciński 2000 , oddíl 1.4, „Asymptotická ekvivalence“, s. 1. 14.
Pohled (in) Galen R. Shorack a Jon A. Wellner , Empirické procesy s aplikacemi pro statistiku , SIAM ,září 2009, 998 s. ( ISBN 978-0-89871-684-9 , číst online ), část 3.8, „Omezení rozdělení podle nulové hypotézy“, s. 142 a kap. 18, „Standardizovaný kvantilový proces“, s. 18 637.
Janson, Łuczak a Ruciński 2000 , Č . 6.7, s. 144.
Viz článek " bijection de Joyal ", nebo Martin Aigner a Günter M. Ziegler, Divine úvah , 2 nd vydání, 2006, str. 195-201, Cayleyův vzorec pro počet stromů .

Bibliografie

(en) Béla Bollobás , náhodné grafy , Cambridge University Press,Leden 2001, 2 nd ed. ( 1 st ed. 1985), 516 str. ( ISBN 978-0-521-79722-1 , číst online ).
(en) Svante Janson (en) , Tomasz Łuczak a Andrzej Ruciński, Random Graphs , Wiley-Interscience,Květen 2000, 1 st ed. , 333 s. , vázaná kniha ( ISBN 978-0-471-17541-4 ).
(en) Joel Spencer (en) , „Devět přednášek o náhodných grafech“ , Letní škola pravděpodobnosti Saint-Flour XXI-1991, část 3 , Springer, kol. "Poznámky k přednášce v matematice. „( N o 1541)1993, str. 293-347.

Související článek

Úvod do pravděpodobností v teorii grafů

Externí odkaz

Laurent Massoulié, Networks: distribuovaná kontrola a vznikající jevy , 2015