Ramanujan-diagram - Ramanujan graph

I spektralgrafteori , en Ramanujan-graf , är en vanlig graf vars spektralgap är nästan så stort som möjligt (se extrem grafteori ). Sådana grafer är utmärkta spektralaxpanderare . Som Murtys undersökningsdokument antecknar, sammanfattar Ramanujan grafer "olika grenar av ren matematik, nämligen talteori , representationsteori och algebraisk geometri ". Dessa diagram är indirekt uppkallade efter Srinivasa Ramanujan ; deras namn kommer från antagandet Ramanujan – Petersson , som användes i en konstruktion av några av dessa grafer.

Definition

Låt vara en ansluten -regelbunden graf med hörn, och låt vara egenvärdena för angränsningsmatrisen för (eller spektrumet för ). Eftersom det är anslutet och -regelbundet uppfyller dess egenvärden . ${\ displaystyle G}$ ${\ displaystyle d}$ ${\ displaystyle n}$ ${\ displaystyle \ lambda _ {1} \ geq \ lambda _ {2} \ geq \ cdots \ geq \ lambda _ {n}}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle G}$ ${\ displaystyle d}$ ${\ displaystyle d = \ lambda _ {1}> \ lambda _ {2}}$ ${\ displaystyle \ geq \ cdots \ geq \ lambda _ {n} \ geq -d}$

Definiera . En ansluten -regelbunden graf är en Ramanujan-graf om . ${\ displaystyle \ lambda (G) = \ max _ {i \ neq 1} | \ lambda _ {i} | = \ max (| \ lambda _ {2} |, | \ lambda _ {n} |)}$ ${\ displaystyle d}$ ${\ displaystyle G}$ ${\ displaystyle \ lambda (G) \ leq 2 {\ sqrt {d-1}}}$

Många källor använder en alternativ definition (närhelst det finns med ) för att definiera Ramanujan-grafer. Med andra ord tillåter vi utöver de "små" egenvärdena. Eftersom och endast om diagrammet är tvåparts , kommer vi att hänvisa till graferna som uppfyller denna alternativa definition men inte den första definitionen av bipartit Ramanujan-grafer . ${\ displaystyle \ lambda '(G) = \ max _ {| \ lambda _ {i} | <d} | \ lambda _ {i} |}$ ${\ displaystyle \ lambda _ {i}}$ ${\ displaystyle | \ lambda _ {i} | <d}$ ${\ displaystyle -d}$ ${\ displaystyle \ lambda _ {n} = - d}$

Som observerats av Toshikazu Sunada är en vanlig graf Ramanujan om och bara om dess Ihara zeta-funktion uppfyller en analog av Riemann-hypotesen .

Exempel och konstruktioner

Den kompletta grafen har spektrum , och därmed och grafen är en Ramanujan graf för varje . Den kompletta bipartitgrafen har spektrum och är därför en bipartit Ramanujan-graf för alla . ${\ displaystyle K_ {d + 1}}$ ${\ displaystyle d, -1, -1, \ dots, -1}$ ${\ displaystyle \ lambda (K_ {d + 1}) = 1}$ ${\ displaystyle d> 1}$ ${\ displaystyle K_ {d, d}}$ ${\ displaystyle d, 0,0, \ dots, 0, -d}$ ${\ displaystyle d}$

Den Petersen grafen har spektrum , så det är en 3-regelbunden Ramanujan graf. Den icosahedral grafen är en 5-vanlig Ramanujan graf. ${\ displaystyle 3,1,1,1,1,1, -2, -2, -2, -2}$

En Paley- ordningsdiagram är -regelbunden med alla andra egenvärden , vilket gör Paley-grafer till en oändlig familj av Ramanujan-grafer. ${\ displaystyle q}$ ${\ displaystyle {\ frac {q-1} {2}}}$ ${\ displaystyle {\ frac {-1 \ pm {\ sqrt {q}}} {2}}}$

Matematiker är ofta intresserade av att konstruera -regelbundna Ramanujan-grafer för varje fix . Nuvarande konstruktioner av oändliga familjer av sådana Ramanujan-grafer är ofta algebraiska. ${\ displaystyle d}$ ${\ displaystyle d}$

Lubotzky , Phillips och Sarnak visar hur man konstruerar en oändlig familj av -regelbundna Ramanujan-grafer, när som helst är ett primtal och . Deras bevis använder Ramanujan-antagandet , vilket ledde till namnet på Ramanujan-grafer. Förutom att vara Ramanujan grafer, sina bygg uppfyller vissa andra egenskaper, till exempel, deras omkrets är där är antalet noder. ${\ displaystyle (p + 1)}$ ${\ displaystyle p}$ ${\ displaystyle p \ equiv 1 {\ pmod {4}}}$ ${\ displaystyle \ Omega (\ log _ {p} (n))}$ ${\ displaystyle n}$
Morgenstern utvidgade byggandet av Lubotzky, Phillips och Sarnak. Hans utökade konstruktion håller när som helst är en huvudmakt . ${\ displaystyle p}$
Arnold Pizer bevisade att de supersingular isogeni graferna är Ramanujan, även om de tenderar att ha lägre omkrets än diagrammen för Lubotzky, Phillips och Sarnak. Liksom diagrammen för Lubotzky, Phillips och Sarnak är graderna i dessa grafer alltid ett primtal plus en. Dessa diagram har föreslagits som grund för kryptografi av elliptisk kurva efter kvantitet .
Adam Marcus , Daniel Spielman och Nikhil Srivastava bevisade att det finns oändligt många - regelbundna bipartitiska Ramanujan-diagram för alla . Senare visade de att det finns bipartit Ramanujan-grafer i varje grad och varje antal hörn. Michael B. Cohen visade hur man konstruerar dessa grafer på polynomisk tid. ${\ displaystyle d}$ ${\ displaystyle d \ geq 3}$

Det är fortfarande ett öppet problem om det finns oändligt många -regelbundna (icke-bipartit) Ramanujan-diagram för någon . I synnerhet är problemet öppet , det minsta fallet för vilket inte är en huvudmakt och därmed inte täckt av Morgenstens konstruktion. ${\ displaystyle d}$ ${\ displaystyle d \ geq 3}$ ${\ displaystyle d = 7}$ ${\ displaystyle d-1}$

Ramanujan grafer som expanderdiagram

Konstanten i definitionen av Ramanujan-grafer är den bästa möjliga konstanten för varje och för stora grafer: med andra ord, för alla och det finns sådana att alla -regelbundna grafer med åtminstone hörn uppfyller . (Se nedan för mer exakta uttalanden och korrekturskisser.) Å andra sidan visade Friedman att för ett och för tillräckligt stort uppfyller en slumpmässig -regelbunden -textex med hög sannolikhet. Detta innebär att Ramanujan-grafer i princip är de bästa möjliga expanderdiagrammen . ${\ displaystyle 2 {\ sqrt {d-1}}}$ ${\ displaystyle d}$ ${\ displaystyle d}$ ${\ displaystyle \ epsilon> 0}$ ${\ displaystyle n}$ ${\ displaystyle d}$ ${\ displaystyle G}$ ${\ displaystyle n}$ ${\ displaystyle \ lambda (G)> 2 {\ sqrt {d-1}} - \ epsilon}$ ${\ displaystyle d}$ ${\ displaystyle \ epsilon> 0}$ ${\ displaystyle n}$ ${\ displaystyle d}$ ${\ displaystyle n}$ ${\ displaystyle G}$ ${\ displaystyle \ lambda (G) <2 {\ sqrt {d-1}} + \ epsilon}$

På grund av att uppnå den snäva bundet på , den expanderblandnings lemma ger utmärkta gränser på enhetligheten av fördelningen av kanter i Ramanujan grafer, och eventuella slumpvandring på graferna har en logaritmisk blandningstid (i termer av antalet hörn): med andra ord konvergerar den slumpmässiga gången mycket snabbt till den (enhetliga) stationära fördelningen . Därför är diametern på Ramanujan-graferna också begränsade logaritmiskt i termer av antalet hörn. ${\ displaystyle \ lambda (G)}$

Extremitet av Ramanujan-grafer

Om en -regular graf med diameter , en sats på grund av Noga Alon stater ${\ displaystyle G}$ ${\ displaystyle d}$ ${\ displaystyle m}$

{\ displaystyle \ lambda _ {2} (G) \ geq 2 {\ sqrt {d-1}} - {\ frac {2 {\ sqrt {d-1}} - 1} {\ lfloor m / 2 \ rfloor }}.}

Närhelst är -regelbunden och ansluten på minst tre hörn , och därför . Låt vara uppsättningen av alla anslutna -regelbundna grafer med åtminstone hörn. Eftersom den minsta diametern på grafer närmar sig oändligheten för fast och ökande , innebär denna sats en tidigare sats om Alon och Boppana som säger ${\ displaystyle G}$ ${\ displaystyle d}$ ${\ displaystyle | \ lambda _ {2} | <d}$ ${\ displaystyle \ lambda (G) \ geq \ lambda _ {2}}$ ${\ displaystyle {\ mathcal {G}} _ {n} ^ {d}}$ ${\ displaystyle d}$ ${\ displaystyle G}$ ${\ displaystyle n}$ ${\ displaystyle {\ mathcal {G}} _ {n} ^ {d}}$ ${\ displaystyle d}$ ${\ displaystyle n}$

{\ displaystyle \ lim _ {n \ to \ infty} \ inf _ {G \ i {\ mathcal {G}} _ {n} ^ {d}} \ lambda (G) \ geq 2 {\ sqrt {d- 1}}.}

En något starkare gräns är

{\ displaystyle \ lambda _ {2} (G) \ geq 2 {\ sqrt {d-1}} \ cdot \ left (1 - {\ frac {c} {m ^ {2}}} \ right),}

var . Bevisens konturer är följande. Ta . Låt vara det kompletta- höjdträdet (varje inre topp har barn), och låt vara dess angränsande matris. Vi vill bevisa det , var . Definiera en funktion med , var är avståndet till roten till . Man kan verifiera det och det är verkligen den största egenvärdet av . Låt oss nu och vara ett par hörn på avstånd i och definiera ${\ displaystyle c \ approx 2 \ pi ^ {2}}$ ${\ displaystyle k = \ left \ lfloor {\ frac {m} {2}} \ right \ rfloor -1}$ ${\ displaystyle T_ {d, k}}$ ${\ displaystyle (d-1)}$ ${\ displaystyle k}$ ${\ displaystyle d-1}$ ${\ displaystyle A_ {d, k}}$ ${\ displaystyle \ lambda _ {2} (G) \ geq \ lambda _ {1} (T_ {d, k}) = 2 {\ sqrt {d-1}} \ cos \ theta}$ ${\ displaystyle \ theta = {\ frac {\ pi} {k + 2}}}$ ${\ displaystyle g: V (T_ {d, k}) \ rightarrow \ mathbb {R}}$ ${\ displaystyle g (x) = (d-1) ^ {- \ delta / 2} \ cdot \ sin ((k + 1- \ delta) \ theta)}$ ${\ displaystyle \ delta}$ ${\ displaystyle x}$ ${\ displaystyle T_ {d, k}}$ ${\ displaystyle A_ {t, k} g = \ lambda _ {1} (T_ {d, k}) g}$ ${\ displaystyle \ lambda _ {1} (T_ {d, k})}$ ${\ displaystyle A_ {d, k}}$ ${\ displaystyle s}$ ${\ displaystyle t}$ ${\ displaystyle m}$ ${\ displaystyle G}$

{\ displaystyle f (v) = {\ begin {cases} c_ {1} g (v_ {s}) & {\ text {for}} v {\ text {på avstånd}} \ leq k {\ text {från }} s, \\ - c_ {2} g (v_ {t}) & {\ text {för}} v {\ text {på avstånd}} \ leq k {\ text {från}} t, \\ 0 & {\ text {annars,}} \ end {cases}}}

var är ett toppunkt där avståndet till roten är lika med avståndet från till och det symmetriska för . (Man kan tänka på detta som "inbyggd" två åtskilda kopior av , med några hörn kollapsade i ett.) Genom att välja värdet av positiva reals ordentligt vi får , för nära och för nära . Sedan med min-max-satsen får vi ${\ displaystyle v_ {s}}$ ${\ displaystyle T_ {d, k}}$ ${\ displaystyle v}$ ${\ displaystyle s}$ ${\ displaystyle v_ {t}}$ ${\ displaystyle T_ {d, k}}$ ${\ displaystyle c_ {1}, c_ {2}}$ ${\ displaystyle f \ perp 1}$ ${\ displaystyle (Af) _ {v} \ geq \ lambda _ {1} (T_ {d, k}) f_ {v}}$ ${\ displaystyle v}$ ${\ displaystyle s}$ ${\ displaystyle (Af) _ {v} \ leq \ lambda _ {1} (T_ {d, k}) f_ {v}}$ ${\ displaystyle v}$ ${\ displaystyle t}$