Expandovací míchací lemma - Expander mixing lemma - Wikipedia

The expandér míchací lemma intuitivně uvádí, že hrany jisté ${ displaystyle d}$-pravidelné grafy jsou rovnoměrně rozloženy po celém grafu. Zejména počet hran mezi dvěma podskupinami vrcholů ${ displaystyle S}$ a ${ displaystyle T}$ je vždy blízko očekávanému počtu hran mezi nimi v a náhodný ${ displaystyle d}$-běžný graf, jmenovitě ${ displaystyle { frac {d} {n}} | S || T |}$.

${ displaystyle d}$-Regular Expander Graphs

Definovat ${ displaystyle (n, d, lambda)}$-graf být ${ displaystyle d}$-pravidelný graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy takové, že všechny vlastní hodnoty jeho matice sousedství ${ displaystyle A_ {G}}$ kromě jednoho mají velikost nejvýše ${ displaystyle lambda.}$ The ${ displaystyle d}$-pravidelnost grafu zaručuje, že jeho vlastní hodnota největší velikosti je ${ displaystyle d.}$ Ve skutečnosti je to all-1 vektor ${ displaystyle mathbf {1}}$ je vlastní vektor ${ displaystyle A_ {G}}$ s vlastním číslem ${ displaystyle d}$a vlastní vektory matice sousedství nikdy nepřekročí maximální stupeň ${ displaystyle G}$ ve velikosti.

Pokud to opravíme ${ displaystyle d}$ a ${ displaystyle lambda}$ pak ${ displaystyle (n, d, lambda)}$-grafy tvoří rodinu expandérové ​​grafy s konstantou spektrální mezera.

Prohlášení

Nechat ${ displaystyle G = (V, E)}$ být ${ displaystyle (n, d, lambda)}$-graf. Pro jakékoli dvě podmnožiny ${ displaystyle S, T subseteq V}$, nechť ${ displaystyle e (S, T) = | {(x, y) v S krát T: xy v E (G) } |}$ být počet hran mezi S a T (počítání hran obsažených v průsečíku S a T dvakrát). Pak

${ displaystyle left | e (S, T) - { frac {d | S || T |} {n}} doprava | leq lambda { sqrt {| S || T |}} , .}$

Užší vazba

Můžeme to ve skutečnosti ukázat

${ displaystyle left | e (S, T) - { frac {d | S || T |} {n}} doprava | leq lambda { sqrt {| S || T | (1- | S | / n) (1- | T | / n)}} ,}$

pomocí podobných technik.^[1]

Biregular Graphs

Pro biregular graphs, máme následující variantu.^[2]

Nechat ${ displaystyle G = (L, R, E)}$ být bipartitní graf tak, aby každý vrchol v ${ displaystyle L}$ sousedí s ${ displaystyle d_ {L}}$ vrcholy ${ displaystyle R}$ a každý vrchol v ${ displaystyle R}$ sousedí s ${ displaystyle d_ {R}}$ vrcholy ${ displaystyle L}$. Nechat ${ displaystyle S subseteq L, T subseteq R}$ s ${ displaystyle | S | = alfa | L |}$ a ${ displaystyle | T | = beta | R |}$. Nechat ${ displaystyle e (G) = | E (G) |}$. Pak

${ displaystyle left | { frac {e (S, T)} {e (G)}} - alpha beta right | leq { frac { lambda} { sqrt {d_ {L} d_ {R}}}} { sqrt { alpha beta (1- alpha) (1- beta)}} leq { frac { lambda} { sqrt {d_ {L} d_ {R}} }} { sqrt { alpha beta}} ,.}$

Všimněte si, že ${ displaystyle { sqrt {d_ {L} d_ {R}}}}$ je největší absolutní hodnota vlastních čísel ${ displaystyle G}$.

Důkazy

Důkaz prvního prohlášení

Nechat ${ displaystyle A_ {G}}$ být matice sousedství z ${ displaystyle G}$ a nechte ${ displaystyle lambda _ {1} geq cdots geq lambda _ {n}}$ být vlastní čísla z ${ displaystyle A_ {G}}$ (tato vlastní čísla jsou skutečná, protože ${ displaystyle A_ {G}}$ je symetrický). Víme, že ${ displaystyle lambda _ {1} = d}$ s odpovídajícím vlastním vektorem ${ displaystyle v_ {1} = { frac {1} { sqrt {n}}} mathbf {1}}$, normalizace vektoru all-1. Protože ${ displaystyle A_ {G}}$ je symetrický, můžeme vybrat vlastní vektory ${ displaystyle v_ {2}, ldots, v_ {n}}$ z ${ displaystyle A_ {G}}$ odpovídající vlastním číslům ${ displaystyle lambda _ {2}, ldots, lambda _ {n}}$ aby ${ displaystyle {v_ {1}, ldots, v_ {n} }}$ tvoří ortonormální základ ${ displaystyle mathbf {R} ^ {n}}$.

Nechat ${ displaystyle J}$ být ${ displaystyle n krát n}$ matice všech 1. Všimněte si, že ${ displaystyle v_ {1}}$ je vlastní vektor ${ displaystyle J}$ s vlastním číslem ${ displaystyle n}$ a navzájem ${ displaystyle v_ {i}}$, kolmo na ${ displaystyle v_ {1} = mathbf {1}}$, je vlastní vektor ${ displaystyle J}$ s vlastní hodnotou 0. Pro podmnožinu vrcholů ${ displaystyle U subseteq V}$, nechť ${ displaystyle 1_ {U}}$ být vektor sloupce s ${ displaystyle v ^ { text {th}}}$ souřadnice rovná 1, pokud ${ displaystyle v v U}$ a 0 jinak. Pak,

${ displaystyle left | e (S, T) - { frac {d} {n}} | S || T | right | = left | 1_ {S} ^ { operatorname {T}} vlevo (A_ {G} - { frac {d} {n}} J vpravo) 1_ {T} vpravo |}$.

Nechat ${ displaystyle M = A_ {G} - { frac {d} {n}} J}$. Protože ${ displaystyle A_ {G}}$ a ${ displaystyle J}$ sdílet vlastní vektory, vlastní čísla ${ displaystyle M}$ jsou ${ displaystyle 0, lambda _ {2}, ldots, lambda _ {n}}$. Podle Cauchy-Schwarzova nerovnost, máme to ${ displaystyle | 1_ {S} ^ { operatorname {T}} M1_ {T} | = | 1_ {S} cdot M1_ {T} | leq | 1_ {S} | | M1_ {T} |}$. Dále proto, že ${ displaystyle M}$ je self-adjoint, můžeme psát

${ displaystyle | M1_ {T} | ^ {2} = langle M1_ {T}, M1_ {T} rangle = langle 1_ {T}, M ^ {2} 1_ {T} rangle = left langle 1_ {T}, sum _ {i = 1} ^ {n} M ^ {2} langle 1_ {T}, v_ {i} rangle v_ {i} right rangle = sum _ {i = 2} ^ {n} lambda _ {i} ^ {2} langle 1_ {T}, v_ {i} rangle ^ {2} leq lambda ^ {2} | 1_ {T} | ^ {2}}$.

To z toho vyplývá ${ displaystyle | M1_ {T} | leq lambda | 1_ {T} |}$ a ${ displaystyle left | e (S, T) - { frac {d} {n}} | S || T | right | leq lambda | 1_ {S} | | 1_ {T} | = lambda { sqrt {| S || T |}}}$.

Důkazní skica užší vazby

Abychom výše ukázali pevnější vazbu, uvažujeme místo toho vektory ${ displaystyle 1_ {S} - { frac {| S |} {n}} mathbf {1}}$ a ${ displaystyle 1_ {T} - { frac {| T |} {n}} mathbf {1}}$, které jsou obě kolmé na ${ displaystyle v_ {1}}$. Můžeme expandovat

${ displaystyle 1_ {S} ^ { operatorname {T}} A_ {G} 1_ {T} = vlevo ({ frac {| S |} {n}} mathbf {1} vpravo) ^ { operatorname {T}} A_ {G} left ({ frac {| T |} {n}} mathbf {1} right) + left (1_ {S} - { frac {| S |} { n}} mathbf {1} right) ^ { operatorname {T}} A_ {G} left (1_ {T} - { frac {| T |} {n}} mathbf {1} right )}$

protože další dva termíny expanze jsou nulové. První termín se rovná ${ displaystyle { frac {| S || T |} {n ^ {2}}} mathbf {1} ^ { operatorname {T}} A_ {G} mathbf {1} = { frac {d } {n}} | S || T |}$, takže to zjistíme

${ displaystyle left | e (S, T) - { frac {d} {n}} | S || T | right | leq left | left (1_ {S} - { frac {| S |} {n}} mathbf {1} right) ^ { operatorname {T}} A_ {G} left (1_ {T} - { frac {| T |} {n}} mathbf { 1} vpravo) vpravo |}$

Můžeme svázat pravou stranu ${ displaystyle lambda left | 1_ {S} - { frac {| S |} {| n |}} mathbf {1} right | left | 1_ {T} - { frac { | T |} {| n |}} mathbf {1} right | = lambda { sqrt {| S || T | left (1 - { frac {| S |} {n}} vpravo) vlevo (1 - { frac {| T |} {n}} vpravo)}}}$ použitím stejných metod jako v dřívějším důkazu.

Aplikace

Lemma expanderového míchání lze použít k horní hranici velikosti nezávislé množiny v grafu. Zejména velikost nezávislé sady v ${ displaystyle (n, d, lambda)}$-graf je nanejvýš ${ displaystyle lambda n / d.}$ To dokazuje pronájem ${ displaystyle T = S}$ ve výše uvedeném prohlášení a s využitím skutečnosti, že ${ displaystyle e (S, S) = 0.}$

Dalším důsledkem je, že pokud ${ displaystyle G}$ je ${ displaystyle (n, d, lambda)}$-graf, pak jeho chromatické číslo ${ displaystyle chi (G)}$ je alespoň ${ displaystyle d / lambda.}$ Je to proto, že v platném zbarvení grafu je sada vrcholů dané barvy nezávislou sadou. Podle výše uvedené skutečnosti má každá nezávislá sada maximálně velikost ${ displaystyle lambda n / d,}$ tak alespoň ${ displaystyle d / lambda}$ takové sady jsou potřebné k pokrytí všech vrcholů.

Druhou aplikací lemmatu míchání expandérů je poskytnout horní mez maximální možné velikosti nezávislé množiny v grafu polarity. Vzhledem k konečnému projektivní rovina ${ displaystyle pi}$ s polarita ${ displaystyle perp,}$ graf polarity je graf, kde vrcholy jsou body a ${ displaystyle pi}$a vrcholy ${ displaystyle x}$ a ${ displaystyle y}$ jsou připojeny právě tehdy, když ${ displaystyle x in y ^ { perp}.}$ Zejména pokud ${ displaystyle pi}$ má pořádek ${ displaystyle q,}$ pak lemma mixéru expandéru může ukázat, že nezávislá množina v grafu polarity může mít velikost maximálně ${ displaystyle q ^ {3/2} -q + ​​2q ^ {1/2} -1,}$ vazba prokázaná Hobartem a Willifordem.

Konverzovat

Bilu a Liniální ukázal^[3] že platí také konverzace: pokud a ${ displaystyle d}$-pravidelný graf ${ displaystyle G = (V, E)}$ splňuje to pro jakékoli dvě podmnožiny ${ displaystyle S, T subseteq V}$ s ${ displaystyle S cap T = emptyset}$ my máme

${ displaystyle left | e (S, T) - { frac {d | S || T |} {n}} doprava | leq lambda { sqrt {| S || T |}},}$

pak je jeho druhá největší (v absolutní hodnotě) vlastní hodnota omezena ${ displaystyle O ( lambda (1+ log (d / lambda)))}$.

Zobecnění na hypergrafy

Friedman a Widgerson dokázali následující zobecnění směšovacího lemmatu na hypergrafy.

Nechat ${ displaystyle H}$ být ${ displaystyle k}$-jednotný hypergraf, tj. hypergraf, ve kterém je každá „hrana“ n-ticí ${ displaystyle k}$ vrcholy. Pro jakýkoli výběr podmnožin ${ displaystyle V_ {1}, ..., V_ {k}}$ vrcholů,

${ displaystyle left || e (V_ {1}, ..., V_ {k}) | - { frac {k! | E (H) |} {n ^ {k}}} | V_ {1 } | ... | V_ {k} | right | leq lambda _ {2} (H) { sqrt {| V_ {1} | ... | V_ {k} |}}.}$

Poznámky

Reference

• Alon, N .; Chung, F. R. K. (1988), „Explicitní konstrukce tolerantních sítí lineární velikosti“, Diskrétní matematika, 72 (1–3): 15–19, doi:10.1016 / 0012-365X (88) 90189-6.

• Haemers, W. H. (1979). Techniky vlastních čísel v designu a teorii grafů (PDF) (Ph.D.).
• Haemers, W. H. (1995), "Prokládání vlastních čísel a grafů", Aplikace lineární algebry, 226: 593–616, doi:10.1016/0024-3795(95)00199-2.

• Hoory, S .; Linial, N .; Wigderson, A. (2006), „Expander Graphs and their Applications“ (PDF), Býk. Amer. Matematika. Soc. (N.S.), 43 (4): 439–561, doi:10.1090 / S0273-0979-06-01126-8.

• Friedman, J .; Widgerson, A. (1995), „Na druhé vlastní číslo hypergrafu“ (PDF), Combinatorica, 15 (1): 43–65, doi:10.1007 / BF01294459, S2CID  17896683.