Alon – Boppana vázán - Alon–Boppana bound - Wikipedia

v teorie spektrálních grafů, Alon – Boppana vázán poskytuje dolní mez na druhé největší vlastní číslo z matice sousedství a ${ displaystyle d}$-pravidelný graf,^[1] což znamená graf, ve kterém má každý vrchol určitý stupeň ${ displaystyle d}$. Důvodem zájmu o druhou největší vlastní hodnotu je, že je zaručeno, že největší vlastní hodnota bude ${ displaystyle d}$ kvůli ${ displaystyle d}$-regularity, přičemž vektor all-ones je přidružený vlastní vektor. Grafy, které se blíží splnění této meze, jsou Ramanujan grafy, což jsou příklady toho nejlepšího možného expandérové ​​grafy.

Věta

Nechat ${ displaystyle G}$ být ${ displaystyle d}$-pravidelný graf na ${ displaystyle n}$ vrcholy s průměrem ${ displaystyle m}$a nechte ${ displaystyle A}$ být jeho maticí sousedství. Nechat ${ displaystyle lambda _ {1} geq lambda _ {2} geq cdots geq lambda _ {n}}$ být jeho vlastní čísla. Pak

${ displaystyle lambda _ {2} geq 2 { sqrt {d-1}} - { frac {2 { sqrt {d-1}} - 1} { lfloor m / 2 rfloor}}. }$

Výše uvedené tvrzení je původní a prokázáno Noga Alon. Existují některé mírně slabší varianty, které zlepšují snadnost důkazů nebo zlepšují intuici. Dva z nich jsou uvedeny v důkazech níže.

Intuice

The Cayleyův graf z volná skupina na dvou generátorech ${ displaystyle a}$ a ${ displaystyle b}$ je příkladem nekonečna ${ displaystyle d}$-pravidelný strom pro ${ displaystyle d = 4.}$

Intuice čísla ${ displaystyle 2 { sqrt {d-1}}}$ pochází z uvažování o nekonečnu ${ displaystyle d}$-pravidelný strom.^[2] Tento graf je univerzální obálkou ${ displaystyle d}$-pravidelné grafy, a to má spektrální poloměr ${ displaystyle 2 { sqrt {d-1}}.}$

Nasycení

Graf, který v zásadě saturuje vázanou vazbu Alon – Boppana, se nazývá a Ramanujan graf. Přesněji řečeno, graf Ramanujan je ${ displaystyle d}$-pravidelný graf takový, že ${ displaystyle | lambda _ {2} |, | lambda _ {n} | leq 2 { sqrt {d-1}}.}$

Friedmanova věta^[3] ukazuje, že pro každého ${ displaystyle d}$ a ${ displaystyle epsilon> 0}$ a pro dostatečně velké ${ displaystyle n}$, náhodný ${ displaystyle d}$-pravidelný graf ${ displaystyle G}$ na ${ displaystyle n}$ vrcholy uspokojí ${ displaystyle max {| lambda _ {2} |, | lambda _ {n} | } <2 { sqrt {d-1}} + epsilon}$ s vysokou pravděpodobností. To znamená, že náhodné ${ displaystyle n}$-vrchol ${ displaystyle d}$-pravidelný graf je obvykle „téměř Ramanujan“.

První důkaz (mírně slabší výrok)

Prokážeme mírně slabší tvrzení, konkrétně upuštění od specifičnosti u druhého funkčního období a jednoduše tvrzení ${ displaystyle lambda _ {2} geq 2 { sqrt {d-1}} - o (1).}$ Tady je ${ displaystyle o (1)}$ termín označuje asymptotické chování jako ${ displaystyle n}$ roste bez vazby ${ displaystyle d}$ zůstává pevná.

Nechť je vrchol vrchol ${ displaystyle V.}$ Podle věta o min-max, stačí zkonstruovat nenulový vektor ${ displaystyle z in mathbb {R} ^ {| V |}}$ takhle ${ displaystyle z ^ { text {T}} mathbf {1} = 0}$ a ${ displaystyle { frac {z ^ { text {T}} Az} {z ^ { text {T}} z}} geq 2 { sqrt {d-1}} - o (1).}$

Vyberte nějakou hodnotu ${ displaystyle r in mathbb {N}.}$ Pro každý vrchol v ${ displaystyle V,}$ definovat vektor ${ displaystyle f (v) in mathbb {R} ^ {| V |}}$ jak následuje. Každá komponenta bude indexována vrcholem ${ displaystyle u}$ v grafu. Pro každého ${ displaystyle u,}$ pokud je vzdálenost mezi ${ displaystyle u}$ a ${ displaystyle v}$ je ${ displaystyle k,}$ pak ${ displaystyle u}$složka ${ displaystyle f (v)}$ je ${ displaystyle f (v) _ {u} = w_ {k} = (d-1) ^ {- k / 2}}$ -li ${ displaystyle k leq r-1}$ a ${ displaystyle 0}$ -li ${ displaystyle k geq r.}$ Tvrdíme, že každý takový vektor ${ displaystyle x = f (v)}$ splňuje

${ displaystyle { frac {x ^ { text {T}} Sekera} {x ^ { text {T}} x}} geq 2 { sqrt {d-1}} vlevo (1 - { frac {1} {2r}} right).}$

Dokážeme to ${ displaystyle V_ {k}}$ označuje množinu všech vrcholů, které mají přesnou vzdálenost ${ displaystyle k}$ z ${ displaystyle v.}$ Nejprve si to povšimněte

${ displaystyle x ^ { text {T}} x = součet _ {k = 0} ^ {r-1} | V_ {k} | w_ {k} ^ {2}.}$

Zadruhé, všimněte si toho

${ displaystyle x ^ { text {T}} Ax = sum _ {u in V} x_ {u} sum _ {u ' v N (u)} x_ {u'} geq sum _ {k = 0} ^ {r-1} | V_ {k} | w_ {k} left [w_ {k-1} + (d-1) w_ {k + 1} right] - (d-1 ) | V_ {r-1} | w_ {r-1} w_ {r},}$

kde poslední člen vpravo pochází z možného přepočtu výrazů v počátečním výrazu. Z výše uvedeného tedy vyplývá

${ displaystyle x ^ { text {T}} Axe geq 2 { sqrt {d-1}} left ( sum _ {k = 0} ^ {r-1} | V_ {k} | w_ { k} ^ {2} - { frac {1} {2}} | V_ {r-1} | w_ {r} ^ {2} right),}$

které v kombinaci se skutečností, že ${ displaystyle | V_ {k + 1} | leq (d-1) | V_ {k} |}$ pro všechny ${ displaystyle k,}$ výnosy

${ displaystyle x ^ { text {T}} Sekera geq 2 { sqrt {d-1}} vlevo (1 - { frac {1} {2r}} vpravo) součet _ {k = 0 } ^ {r-1} | V_ {k} | w_ {k} ^ {2}.}$

Kombinace výše uvedených výsledků dokazuje požadovanou nerovnost.

Pro větší pohodlí definujte ${ displaystyle (r-1)}$- koule vrcholu ${ displaystyle v}$ být množina vrcholů se vzdáleností maximálně ${ displaystyle r-1}$ z ${ displaystyle v.}$ Všimněte si, že vstup ${ displaystyle f (v)}$ odpovídající vrcholu ${ displaystyle u}$ je nenulová právě tehdy ${ displaystyle u}$ leží v ${ displaystyle (r-1)}$- koule ${ displaystyle x.}$

Počet vrcholů ve vzdálenosti ${ displaystyle k}$ daného vrcholu je maximálně ${ displaystyle 1 + d + d (d-1) + d (d-1) ^ {2} + cdots + d (d-1) ^ {k-1} = d ^ {k} +1.}$ Proto pokud ${ displaystyle n geq d ^ {2r-1} +2,}$ pak existují vrcholy ${ displaystyle u, v}$ minimálně se vzdáleností ${ displaystyle 2r.}$

Nechat ${ displaystyle x = f (v)}$ a ${ displaystyle y = f (u).}$ Z toho pak vyplývá ${ displaystyle x ^ { text {T}} y = 0,}$ protože ve vrcholu není žádný vrchol ${ displaystyle (r-1)}$- koule obou ${ displaystyle x}$ a ${ displaystyle y.}$ Je to také pravda ${ displaystyle x ^ { text {T}} Ay = 0,}$ protože žádný vrchol v ${ displaystyle (r-1)}$- koule ${ displaystyle x}$ může sousedit s vrcholem v ${ displaystyle (r-1)}$- koule ${ displaystyle y.}$

Nyní existuje nějaká konstanta ${ displaystyle c}$ takhle ${ displaystyle z = x-cy}$ splňuje ${ displaystyle z ^ { text {T}} mathbf {1} = 0.}$ Pak od té doby ${ displaystyle x ^ { text {T}} y = x ^ { text {T}} Ay = 0,}$

${ displaystyle z ^ { text {T}} Az = x ^ { text {T}} Ax + c ^ {2} y ^ { text {T}} Ay geq 2 { sqrt {d-1 }} left (1 - { frac {1} {2r}} right) (x ^ { text {T}} x + c ^ {2} y ^ { text {T}} y) = 2 { sqrt {d-1}} left (1 - { frac {1} {2r}} right) z ^ { text {T}} z.}$

Nakonec necháme ${ displaystyle r}$ růst bez vazby a přitom to zajistit ${ displaystyle n geq d ^ {2r-1} +2}$ (To lze provést tím, že ${ displaystyle r}$ rostou sublogaritmicky jako funkce ${ displaystyle n}$) dělá chybový termín ${ displaystyle o (1)}$ v ${ displaystyle n.}$

Druhý důkaz (mírně pozměněné prohlášení)

Tento důkaz předvede mírně upravený výsledek, ale poskytuje lepší intuici pro zdroj čísla ${ displaystyle 2 { sqrt {d-1}}.}$ Spíše než to ukazovat ${ displaystyle lambda _ {2} geq 2 { sqrt {d-1}} - o (1),}$ ukážeme to ${ displaystyle lambda = max (| lambda _ {2} |, | lambda _ {n} |) geq 2 { sqrt {d-1}} - o (1).}$

Nejprve vyberte nějakou hodnotu ${ displaystyle k in mathbb {N}.}$ Všimněte si, že počet uzavřených procházek délky ${ displaystyle 2k}$ je

${ displaystyle operatorname {tr} A ^ {2k} = součet _ {i = 1} ^ {n} lambda _ {i} ^ {2k} leq d ^ {2k} + n lambda ^ {2k }.}$

Je však také pravda, že počet uzavřených procházek délky ${ displaystyle 2k}$ začínající na pevném vrcholu ${ displaystyle v}$ v ${ displaystyle d}$-pravidelný graf je alespoň počet takových procházek v nekonečnu ${ displaystyle d}$-pravidelný strom, protože nekonečný ${ displaystyle d}$-regulární strom lze použít k pokrytí grafu. Podle definice Katalánská čísla, toto číslo je minimálně ${ displaystyle C_ {k} (d-1) ^ {k},}$ kde ${ displaystyle C_ {k} = { frac {1} {k + 1}} { binom {2k} {k}}}$ je ${ displaystyle k ^ { text {th}}}$ Katalánské číslo.

Z toho vyplývá, že

${ displaystyle operatorname {tr} A ^ {2k} geq n { frac {1} {k + 1}} { binom {2k} {k}} (d-1) ^ {k}}$

${ displaystyle implikuje lambda ^ {2k} geq { frac {1} {k + 1}} { binom {2k} {k}} (d-1) ^ {k} - { frac {d ^ {2k}} {n}}.}$

Pronájem ${ displaystyle n}$ růst bez spoutání a nechat ${ displaystyle k}$ růst bez vazby, ale sublogaritmicky v ${ displaystyle n}$ výnosy ${ displaystyle lambda geq 2 { sqrt {d-1}} - o (1).}$

Reference