Závislá náhodná volba - Dependent random choice

V matematice závislá náhodná volba je jednoduchá, ale výkonná pravděpodobnostní technika, která ukazuje, jak najít velkou sadu vrcholů v hustém grafu, takže každá malá podmnožina vrcholů má mnoho společných sousedů. Je to užitečný nástroj pro vložení grafu do jiného grafu s mnoha hranami, a proto má své použití v teorie extrémních grafů a Ramseyova teorie.

Výrok věty

^[1]^[2]^[3]^[4]^[5]Nechat ${ displaystyle u, n, r, m, t in mathbb {N}}$ , ${ displaystyle alpha> 0}$ a předpokládejme

{ displaystyle n alpha ^ {t} - {n zvolit r} doleva ({ frac {m} {n}} doprava) ^ {t} geq u.}

Pak každý graf zapnutý

{ displaystyle n}

vrcholy s minimem

{ displaystyle { frac { alpha n ^ {2}} {2}}}

edge obsahuje podmnožinu

{ displaystyle U}

vrcholů s

{ displaystyle | U | geq u}

takové, že pro všechny

{ displaystyle S podmnožina U}

s

{ displaystyle | S | = r}

,

{ displaystyle S}

má alespoň

{ displaystyle m}

společné sousedy.

Důkaz

Základní myšlenkou je náhodný výběr množiny vrcholů. Namísto náhodného výběru každého vrcholu však postup zvolí seznam ${ displaystyle t}$ nejprve vrcholy a poté vybere své společné sousedy jako množinu vrcholů. Doufáme, že tímto způsobem by vybraná množina pravděpodobně měla více společných sousedů.

Formálně, pojďme ${ displaystyle T}$ být seznam ${ displaystyle t}$ vrcholy vybrané náhodně jednotně z ${ displaystyle V (G)}$ s výměnou (umožňující opakování). Nechat ${ displaystyle A}$ být společným sousedstvím ${ displaystyle T}$ . Očekávaná hodnota ${ displaystyle | A |}$ je

{ displaystyle { begin {seřazeno} mathbb {E} | A | & = sum _ {v in V} mathbb {P} (v v A) = sum _ {v ve V} mathbb {P} (T subseteq N (v)) = sum _ {v in V} left ({ frac {d (v)} {n}} right) ^ {t} & geq n left ({ frac {1} {n}} sum _ {v in V} { frac {d (v)} {n}} right) ^ {t} quad { text { (konvexita)}} & geq n alpha ^ {t}. end {zarovnáno}}}

Pro každého

{ displaystyle r}

- podmnožina prvků

{ displaystyle S}

z

{ displaystyle V}

událost

{ displaystyle A}

obsahující

{ displaystyle S}

nastane tehdy a jen tehdy

{ displaystyle T}

je obsažen ve společném sousedství

{ displaystyle S}

, ke kterému dochází s pravděpodobností

{ textstyle left ({ frac { # { text {běžní sousedé}} S} {n}} vpravo) ^ {t}.}

Zavolejte

{ displaystyle S}

špatný pokud má méně než

{ displaystyle m}

společné sousedy. Pak pro každou pevnou

{ displaystyle r}

- podmnožina prvků

{ displaystyle S}

z

{ displaystyle V}

, je obsažen v

{ displaystyle A}

s pravděpodobností menší než

{ displaystyle (m / n) ^ {t}}

. Proto podle linearity očekávání,

{ displaystyle mathbb {E} [ # { text {bad}} r { text {-prvková podmnožina}} A] <{ binom {n} {r}} left ({ frac {m } {n}} vpravo) ^ {t}.}

Abychom se ujistili, že neexistují žádné špatné podmnožiny, můžeme se zbavit jednoho prvku v každé špatné podmnožině. Počet zbývajících prvků je alespoň

{ displaystyle | A | - ( # { text {bad}} r { text {-prvková podmnožina}} A)}

, jehož očekávaná hodnota je minimálně

{ textstyle n alpha ^ {t} - { binom {n} {r}} left ({ frac {m} {n}} right) ^ {t} geq u.}

V důsledku toho existuje a

{ displaystyle T}

takové, že jich je alespoň

{ displaystyle u}

prvky v

{ displaystyle A}

zbývající po zbavení se všeho špatného

{ displaystyle r}

-prvkové podmnožiny. Sada

{ displaystyle U}

zbývajících

{ displaystyle u}

elements vyhovuje požadovaným vlastnostem.

Aplikace

Turánova čísla bipartitního grafu

Přímým použitím závislé náhodné volby nastavením příslušných parametrů můžeme ukázat, že pokud ${ displaystyle H = A pohár B}$ je bipartitní graf, ve kterém jsou všechny vrcholy ${ displaystyle B}$ mít titul nanejvýš ${ displaystyle r}$ , pak extrémní číslo ${ displaystyle { text {ex}} (n, H) leq cn ^ {2-1 / r}}$ kde ${ displaystyle c = c (H)}$ záleží jen na ${ displaystyle H}$ .^[1]^[5]

Formálně, pokud ${ displaystyle a = | A |, b = | B |}$ a ${ displaystyle c}$ je dostatečně velká konstanta taková, že ${ displaystyle (2c) ^ {r} - (a + b) ^ {r} geq a.}$ Pak nastavením ${ displaystyle alpha = 2cn ^ {- 1 / r}, m = a + b, t = r, u = a}$ víme, že

{ displaystyle n alpha ^ {t} - { binom {n} {r}} left ({ frac {m} {n}} right) ^ {t} = (2c) ^ {r} - { binom {n} {r}} vlevo ({ frac {a + b} {n}} vpravo) ^ {r} geq (2c) ^ {r} - (a + b) ^ {r } geq a = u,}

a tak platí předpoklad závislé náhodné volby. Proto pro každý graf

{ displaystyle G}

s alespoň

{ displaystyle cn ^ {2-1 / r}}

hran, existuje podmnožina vrcholů

{ displaystyle U}

velikosti

{ displaystyle a}

uspokojení, že každý

{ displaystyle r}

-podskupina

{ displaystyle U}

má alespoň

{ displaystyle a + b}

společné sousedy. To nám umožňuje vložit

{ displaystyle H}

do

{ displaystyle G}

následujícím způsobem. Vložit

{ displaystyle A}

do

{ displaystyle U}

libovolně, a poté vložte vrcholy dovnitř

{ displaystyle B}

jeden za druhým. Pro každý vrchol

{ displaystyle v}

v

{ displaystyle B}

, má nanejvýš

{ displaystyle r}

sousedé v

{ displaystyle A}

, což ukazuje, že jejich obrázky v

{ displaystyle U}

mít alespoň

{ displaystyle a + b}

společné sousedy. To nám umožňuje vložit

{ displaystyle v}

jednomu ze společných sousedů, aniž by došlo ke kolizi.

Ve skutečnosti to lze zobecnit na degenerovat grafy využívající variantu závislé náhodné volby popsané níže.

Vložení a 1 členění úplného grafu

Závislá náhodná volba může být použita přímo, aby se ukázalo, že pokud ${ displaystyle G}$ je graf na ${ displaystyle n}$ vrcholy a ${ displaystyle epsilon n ^ {2}}$ hran ${ displaystyle G}$ obsahuje 1 členění úplného grafu s ${ displaystyle epsilon ^ {3/2} n ^ {1/2}}$ vrcholy. To lze ukázat podobným způsobem jako výše uvedený důkaz o vázanosti Turánovo číslo bipartitního grafu.^[1]

Ve skutečnosti, pokud jsme nastavili ${ displaystyle alpha = 2 epsilon, m = a ^ {2}, t = { frac { log n} {2 log 1 / epsilon}}, u = a}$ , máme (od ${ displaystyle 2 epsilon = alpha leq 1}$ )

{ displaystyle n alpha ^ {t} - { binom {n} {r}} left ({ frac {m} {n}} right) ^ {t} geq (2 epsilon) ^ { t} n - { binom {n} {2}} epsilon ^ {3t} geq n ^ {1/2} geq a = u,}

a tak platí předpoklad závislé náhodné volby. Vzhledem k tomu, že 1-členění celého grafu je na

{ displaystyle a}

vertices je bipartitní graf s částmi velikosti

{ displaystyle a}

a

{ displaystyle b = { binom {a} {2}}}

kde každý vrchol ve druhé části má stupeň dva, můžeme spustit vkládací argument ve výše uvedeném důkazu o vázání Turánovo číslo bipartitního grafu pro získání požadovaného výsledku.

Variace

Existuje silnější verze závislé náhodné volby, která najde dvě podmnožiny vrcholů ${ displaystyle U_ {1}, U_ {2}}$ v hustém grafu ${ displaystyle G}$ takže každá malá podmnožina vrcholů v ${ displaystyle U_ {i}}$ má mnoho společných sousedů ${ displaystyle U_ {3-i}}$ .

Formálně, pojďme ${ displaystyle u, n, r, m, t, q}$ být některá kladná celá čísla s ${ displaystyle q> r}$ a nechte ${ displaystyle alpha> 0}$ být nějaké skutečné číslo. Předpokládejme, že platí následující omezení:

{ displaystyle { begin {aligned} n alpha ^ {t} - { binom {n} {q}} left ({ frac {m} {n}} right) ^ {t} & geq u { binom {n} {r}} vlevo ({ frac {m} {u}} vpravo) ^ {qr} & <1. end {zarovnáno}}}

Pak každý graf

{ displaystyle G}

na

{ displaystyle n}

vrcholy s minimem

{ displaystyle alpha n ^ {2} / 2}

edge obsahuje dvě podmnožiny

{ displaystyle U_ {1}, U_ {2}}

vrcholů, takže jakýkoli

{ displaystyle r}

vrcholy v

{ displaystyle U_ {i}}

mít alespoň

{ displaystyle m}

společné sousedy v

{ displaystyle U_ {3-i}}

.^[1]

Extrémní číslo zdegenerovaného bipartitního grafu

Pomocí tohoto silnějšího výrazu je možné horní mez extrémního počtu ${ displaystyle r}$ -degenerovat bipartitní graf: pro každý ${ displaystyle r}$ -generovat bipartitní graf ${ displaystyle H}$ maximálně ${ displaystyle N ^ {1-1,8 / s}}$ vrcholy, extrémní číslo ${ displaystyle { text {ex}} (N, H)}$ je nanejvýš ${ displaystyle N ^ {2-1 / (s ^ {3} r)}.}$ ^[1]

Ramseyovo číslo degenerovaného bipartitního grafu

Toto tvrzení lze také použít k získání horní hranice Ramseyova čísla degenerovaných bipartitních grafů. Li ${ displaystyle r}$ je pevné celé číslo, pak pro každou bipartitu ${ displaystyle r}$ -generovat bipartitní graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy, Ramseyovo číslo ${ displaystyle r (G)}$ je řádu ${ displaystyle n ^ {1 + o (1)}.}$ ^[1]

Reference

^ ^A ^b ^C ^d ^E ^F Fox, Jacob; Sudakov, Benny (2011). "Závislá náhodná volba". Náhodné struktury a algoritmy. 38 (1–2): 68–99. doi:10.1002 / rsa.20344. hdl:1721.1/70097. ISSN 1098-2418.
^ Verstraëte, Jacques (2015). „6 - Závislá náhodná volba“ (PDF).
^ Kostochka, A. V .; Rödl, V. (2001). "Na grafech s malými čísly Ramseyho *". Journal of Graph Theory. 37 (4): 198–204. doi:10.1002 / jgt.1014. ISSN 1097-0118.
^ Sudakov, Benny (01.05.2003). „Několik poznámek k problémům typu Ramsey – Turán“. Journal of Combinatorial Theory, Series B. 88 (1): 99–106. doi:10.1016 / S0095-8956 (02) 00038-2. ISSN 0095-8956.
^ ^A ^b Alon, Noga; Krivelevich, Michael; Sudakov, Benny (listopad 2003). „Turánovy počty bipartitních grafů a související otázky typu Ramseyho“. Kombinatorika, pravděpodobnost a výpočet. 12 (5+6): 477–494. doi:10.1017 / S0963548303005741. ISSN 1469-2163.

Další čtení

Závislá náhodná volba - MIT Math

[Fox-1] A ^b ^C ^d ^E ^F Fox, Jacob; Sudakov, Benny (2011). "Závislá náhodná volba". Náhodné struktury a algoritmy. 38 (1–2): 68–99. doi:10.1002 / rsa.20344. hdl:1721.1/70097. ISSN 1098-2418.

[2] Verstraëte, Jacques (2015). „6 - Závislá náhodná volba“ (PDF).

[3] Kostochka, A. V .; Rödl, V. (2001). "Na grafech s malými čísly Ramseyho *". Journal of Graph Theory. 37 (4): 198–204. doi:10.1002 / jgt.1014. ISSN 1097-0118.

[4] Sudakov, Benny (01.05.2003). „Několik poznámek k problémům typu Ramsey – Turán“. Journal of Combinatorial Theory, Series B. 88 (1): 99–106. doi:10.1016 / S0095-8956 (02) 00038-2. ISSN 0095-8956.

[Alon-Krivelevish-Sudakov-5] A ^b Alon, Noga; Krivelevich, Michael; Sudakov, Benny (listopad 2003). „Turánovy počty bipartitních grafů a související otázky typu Ramseyho“. Kombinatorika, pravděpodobnost a výpočet. 12 (5+6): 477–494. doi:10.1017 / S0963548303005741. ISSN 1469-2163.

[1]

[2]

[3]

[4]

[5]