膨脹圖族的鋸齒積構造分析研究數(shù)學與應用數(shù)學專業(yè)

《膨脹圖族的鋸齒積構造分析研究數(shù)學與應用數(shù)學專業(yè)》由會員分享，可在線閱讀，更多相關《膨脹圖族的鋸齒積構造分析研究數(shù)學與應用數(shù)學專業(yè)（12頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 目錄 第1章 膨脹圖………………………………………………………2 第2章 G=Z群的概念…………………………………………2 第3章 鄰接算子………………………………………………3 第4章 CAYLEY圖介紹……………………………………………3 第5章 鋸齒積………………………………………………………4 第5．1節(jié) 的來源……………………………………………4 第5．2節(jié) 一個實際的膨脹圖族…………………………………6 摘要 在組合學中，膨脹

2、圖是一個具有強連通性的稀疏圖，由頂點，邊和頻譜擴展可以確定．膨脹圖的發(fā)展進一步推動了計算機網(wǎng)絡的發(fā)展，在設計算法，錯誤校正碼等許多方面都取得不少突破．單個膨脹圖的用處并不大，人們更多的是對一族膨脹圖進行研究．目前構造膨脹圖族的主流方法有三種，本文中重點討論的是鋸齒積(Zig-zag Product)構造． In?combinatorics, an?expander graph?is a?sparse graph?that has strong?connectivity?properties, quantified using?vertex,?edge?or spectral expans

3、ion as described below．Expander constructions have spawned research in pure and applied mathematics, with several applications to?complexity theory, design of robust?computer networks, and the theory of?error-correcting codes． There are three general strategies for constructing families of expan

4、der graphs．[11]?The first strategy is algebraic and group-theoretic, the second strategy is analytic and uses?additive combinatorics, and the third strategy is combinatorial and uses the?zig-zag?and related graph products．?Noga Alon?showed that certain graphs constructed from?finite geometries?are t

5、he sparsest examples of highly expanding graphs． 關鍵詞 膨脹圖(Expander Graph),鋸齒積(Zig-zag Product) 前言 目前，學術界對膨脹圖及鋸齒積進行了大量的研究和實踐，取得了一批具有啟發(fā)性，建設性的成果，為用鋸齒積構造膨脹圖族構建了完善的理論參考．本段對國內外部分學者的有關研究進行了梳理和總結． 膨脹圖是一個具有強連通性的稀疏圖．每一個連通圖都是一個膨脹圖．但是，不同的連通圖具有不同的膨脹參數(shù)，例如點膨脹[4]，邊膨脹[7]，譜膨脹[7]．膨脹圖的發(fā)展進一步加深了對數(shù)學與應用數(shù)學的研究

6、．最初研究膨脹圖的動機是建立穩(wěn)固的節(jié)約成本的網(wǎng)絡，目前膨脹圖在計算科學領域有大量應用，在設計算法，錯誤校正碼[7]，提取器，偽隨機數(shù)生成器，排序網(wǎng)絡[1]和穩(wěn)固計算機網(wǎng)絡方面都取得了不少突破．它們同樣被使用來證明復雜計算理論中的許多重要結論，例如SL=L[10]和PCP定理[5]．在密碼系統(tǒng)中，膨脹圖族被用來構造散列函數(shù)．下面的一些膨脹圖族的特性在許多領域都被證明很有用，例如膨脹圖混合引理(Expander mixing lemma)，膨脹圖回路抽樣(Expander walk sampling)[2][6]，腦圖膨脹特性． 目前構造一族膨脹圖的主流方法有三種[11]．第一種方法是利用代

7、數(shù)和群理論構造，第二種通過分析法和加法論來構造，第三種即為本文中將要證明的鋸齒積構造法，Noga Alon證明了有限幾何學上構造的一族特定的圖即為膨脹圖族的一個極佳的例子[3]． 鋸齒積是由Reingold，Vadhan & Wigderson[8]首次提出的．在2002年，Omer Reingold，Salil Vadhan和Avi Wigderson給出了一個簡單明確的構造一族有固定度數(shù)的膨脹圖族的方法．構造法是迭代的，并且需要一個滿足相關條件的基礎圖．在每次迭代過程中，鋸齒積被用來生成另一個保持原有性質不變的圖，通過不斷迭代，最終生成一族膨脹圖．再后來又被用來證明復雜計算理論中sy

8、mmetric logspace 和 logspace是相等的[9]． 本文中重點描述的是如何通過給定的基礎圖來構造一族膨脹圖，并且驗證構造過程是合理的． 正文 第1章 膨脹圖 X=(V，E)為圖，V為它的頂點集，E為它的邊集．如果沒有特別聲明，總假定X是無圈的有限圖． 定義1．1 X=(V，E)為有限圖，記 為X的膨脹常數(shù)(還可以稱為等周常數(shù)或Cheeger常數(shù))．這里AV，A為A的鄰居，也就是不在A中，但與A中的點相連接的那些點． 定義1．2 X為正則有限圖(即每個頂點的度為恒定的k)

9、．對于，X稱為-膨脹圖如果． 對于連通圖而言，若頂點數(shù)為，取，那么對任何非空的且，總有，因此膨脹圖的定義對單個圖而言意義并不十分大．人們更多的是考慮一族正則圖的膨脹常數(shù)，一般還要求正則度數(shù)是固定的，并且這族圖的頂點數(shù)目是趨于無窮的． 定義1．3 為一族有限的連通正則圖，且，這里是的頂點集，如果存在，使得 ，就稱是一族膨脹圖． 第2章 G=Z8 p 群的概念 整數(shù)集合Z對于加法+而言作成整數(shù)加群；所有的模n剩余類構成的集合是整數(shù)集合的一個分類(對應的是整數(shù)集合上的同余關系)，現(xiàn)將所有的模n剩余類構成集合記作Zn， 即Zn={[r]|r=0，1…，n-1} 其

10、中[r]={qm+r|q=0，±1，±2，…} 模n剩余類加法: 設[a]=[a']，[b]=[b'] 則[a+b]=[a'+b'] 稱此運算為模n剩余類加法，記 [a][b]=[a'+b'] 模n剩余類集合Zn對于模n剩余類加法構成的群稱為模n剩余類加群． ． 類似可有． 第3章 鄰接算子 定義3．1 令S為有限集．定義復向量空間如下 ． 令且．向量空間上加法運算為．數(shù)乘運算為．標準內積和范數(shù)分別為，．當表示標準內積和標準范數(shù)時，下標可以省

11、略，簡記為． 定義3．2 令X為一個圖，其頂點分別為．則X的鄰接矩陣為矩陣A，其中Ai，j等于以vi，vj為兩頂點的邊的數(shù)目． 例如，在右下圖中， [12] 備注3．3 假定圖X的頂點集V為{}，令A為X的鄰接矩陣．給定，則可將f看作Cn中的向量．則 ． 因此由公式 (1) 可將A視為從到其自身的一個線性轉換． 定義3．4 由(1)式定義出的線性算子A稱為X的鄰接算子． 第四章 CAYLEY圖介紹 定義4．1 一個集合的元素如果在該集合中出現(xiàn)次數(shù)大于1，則稱該集合為多重集

12、．元素在該多重集中出現(xiàn)的次數(shù)稱為該元素的多重性．如果S為一個多重集，則|S|表示S中元素的個數(shù)． 例4．2 考慮多重集．元素的多重性為3，-1的多重性為2，元素4，x和15的多重性皆為1，故|S|＝８． 定義4．3 令G為一個群，為G的一個多重子集．如果對于任意的多重性為n，同樣為中多重性為n的元素，則稱是對稱的．如果是G的對稱多重子集，則記G 定義4．4 令G為一個群且G．則G關于的Cayley圖記為 Cay(G， )，定義如下：Cay(G， )的頂點是G的元素．G中兩個頂點x，y相鄰等價于．(即．)邊(x，y)在邊集E中的多重性等于中的多重性． 引理4

13、．5 令G為一個群且G，則下述結論成立 1． Cay(G， )是||正則的． 2． Cay(G， )連通等價于生成群G． 第5章 鋸齒積 第1節(jié) 的來源 令X為dx-正則圖，Y為dy-正則圖且滿足dX=|Y|=VY．令VX，VY分別為X，Y的頂點集，令EX，EY分別為X，Y的多重邊集，多重邊視作不同元素．，令，令為雙射．(dX=|Y|保證了Lv的存在．)稱Lv為v上的標號．令，稱L是從Y到X的標號． 定義鋸齒積XLY如下．XLY的頂點集為XY的笛卡爾積．如果(x1，y1)和(x2，y2)皆為XLY中的頂點，則此兩點間邊的數(shù)目等于有序邊對的數(shù)目，其中z1，

14、z2必須滿足下列條件: y1為z1的終點，y2為z2的終點且． 例5．1 在下面給出的圖X，Y中，有VX={a，b}，VY={1，2，3}．注意到X為3正則圖，且|Y|=3．所以一旦選好標號，就可以定義X和Y的鋸齒積． [12] [12] [12] 取EX={e1，e2，e3，e4}，其中e1為頂點a處的環(huán)；e2為頂點b處的環(huán)；e3為頂點a，b間的

15、頂邊；e4為頂點a，b間的底邊．則Ea={e1，e3，e4}，Eb={e2，e3，e4}． 定義La，Lb如下: La(1)=e3 Lb(1)=e3 La(2)=e4 Lb(2)=e4 La(3)=e1 Lb(3)=e2 我們通過標記X中每個頂點處的邊來描述L={La，Lb}，如圖所示． 問：a1與b3有幾條邊相連？即滿足的邊對數(shù)目

16、 只有此時， 故a1，b3之間有邊對(s，u)與(r，u)． 尋找zig-zag product的邊的過程，實際上是以下操作的多次進行． 備注5．2 令(x1，y1)為XLY中一頂點，為找到其它與其相鄰的頂點(x2，y2)，進行如下操作． 步驟1(zig):在Y中選一條邊z1，以y1為頂點，指針移動到(x1，z1(y1))． 步驟2(hyphen):x2為的另一個端點，，指針移動到(x2，y')． 步驟3:(zag):在Y中選一條邊z2，以y'為頂點，y2=z2(y')，指針移動到(x2，y2)． 問上例中a1的相

17、鄰點有哪些？ (zig) 不妨考慮z1=s (hyphen) ， ， 指針在b2 (zag) 因此a1與b1，b3相鄰．同樣的考慮z1=r，最終結果與上面相同． 再考慮z1=t，得a1與a1，a2，a3相連，重數(shù)分別為1，1，1． 綜上a1分別與a1，a2，a3，b1，b3相連，重數(shù)分別為1，1，1，4，2． 第2節(jié) 一個實際的膨脹圖族 在本段中，我們將用迭代法構造出一族膨脹圖．開始之前，我們先給出一個基本圖W．我們會發(fā)現(xiàn)圖W必須要滿足幾個條件才能更好地定義出構造，同時必須符合定理5．26來保證譜隙一致有界不為零．現(xiàn)在明確地給出一

18、個正則的非二部圖W滿足|W|=d4 W，λ(W)≤．我們開始對這個圖進行構造． 令p為大于35的質數(shù)．令G=Z8 p．換句話說，G為Zp的8次笛卡爾積． 定義γ：Z2 p→G，γ(x，y)=(x，xy，xy2，xy3，xy4，xy5，xy6，xy7)．令Г={γ(x，y)|(x，y)∈Z2 p}．(這里我們把Г看作多重集，不是一般集．)記G 令 W=Cay(G，Г)． 令ω=e． 定義5．3 取a∈G記作a=(a0，a1，a2，a3，a4，a5，a6，a7)．對任意a，b∈G，定義 ab=a0b0+a1b1+a2b2+a

19、3b3+a4b4+a5b5+a6b6+a7b7．記G的單位元為0． 引理5．4 令為整數(shù)．令．則 ． 引理5．5 證明： 當c＝0，由|G|=p8可以立即得出．當c≠0時，存在j使得cj≠0． 不失一般性，令c0≠0． ， 最后一等式由引理5．4給出． 對任意aG，定義faL2(W):fa(x)＝．(注意到wp=1，fa是定義良好的)． 令A為W的鄰接算子（adjacency operator）．定義λa＝．現(xiàn)在來證明W的

20、特征值就是． 引理5．6 對于任意aG，有Afa＝λafa 證明： bG，有 (Afa)(b) ＝ ＝ ＝λafa(b)． 引理5．7 令V為內積空間，，若形成一組非零正交向量，則線性無關． 引理5．8 {fa|aG}是一個線性無關集合． 證明： 我們將要證＝0，a≠b．由引理5．7可推斷如下等式 ＝ ＝ ＝ ＝＝

21、0 最后一等式由引理5．5得到． 引理5．9 W的每個特征值都等于某個，其中． 證明： 由引理5．6，每個fa都是W的特征值λa的一個特征向量．通過引理5．8以及向量組fa的數(shù)量恰好為|W|，可以看出向量組fa組成正交特征基． 引理5．10 a≠0，有0≤λa≤7p． 證明： λa＝ ＝ ＝． 定義多項式g(t)=a0+a1t+．．．+a7t7．對任意給定的yZp，由引理6．2得 因此λa=np，n為g在Zp中根的數(shù)量．由于a0，故g是一個不大于7次的非零多項式，所以n7． 下面的引理列舉了我們

22、需要的W的性質． 引理5．11 令W=Cay(G，Г)，則 1．|W|=， 2．W是非二部的， 3．． 證明: 1．|W|=|G|=p8，dW=|Г|=p2． 2．由引理5．9和引理5．10可知，-ｐ2不是W的特征值． 3．由引理5．9，引理5．10，和p﹥35，可得 ． 定義5．12 令X為有限圖，頂點集為V．定義Xn的頂點集仍為V，從v1到v2的邊的重數(shù)等于X中從v1到v2步長為n的路徑數(shù)目．即，Xn為X的n次積． 終于，我們可以定義一個實際的膨脹圖族． 定義5．13 令W=Cay(G，Г)，按如下規(guī)則遞歸地定義(Wn)

23、 W1=W2， Wn+1=W2 nW 其中W2 nW由任意從W到W2 n的標記形成． 引理5．14 令X，Y，L如5．2定義，則XLY為-正則圖． 備注5．15 對引理5．14 用歸納法可以直接得出(W2 n)的度=p8=|W|，上式對任意正整數(shù)n皆成立，故鋸齒積W2 nW的構造是合理的． 引理5．16 令X為有限圖，特征值為．則Xj的特征值為． 引理5．17 令X為-正則非二部圖，Y為-正則非二部圖，且有． 則對任意從X到Y的標號有 (XY)． 引理5．18 令(Xn)為一

24、系列d-正則圖，且． 則(Xn)為一族膨脹圖一致有界不為零． 定理5．19 令(Wn)按照定義5．13定義．則(Wn)是一膨脹圖族． 證明： 首先，由命題5．14，得deg(Wn)=p4對任意n成立．再由歸納法得|Wn|=p8n，則|Wn|→∞． 現(xiàn)在我們通過歸納來證對任意n，λ(Wn)<2p4/5．這意味著對任意n，Wn的譜隙至少為3p4/5，所以由引理5．18，這足夠來證明(Wn)是一族膨脹圖． 與此同時，W2 n是非二分的，因為任意一個有一條邊的圖的平方至少有一個環(huán)． 由引理5．16，引理5．11及p>35，有 ． 這

25、創(chuàng)建了基本情形．為了歸納，假定λ(Wn)<2p4/5．由引理5．35，我們知道W非二部．由引理5．11，引理5．16及引理5．17，得 λ (W2 nW)+p2λ(W)+λ(W)2 ． 結論 用鋸齒積來構造一族膨脹圖被證實是可行的，這使得在計算機領域可通過迭代算法來構造出膨脹圖族，從而進一步推動了膨脹圖在計算機網(wǎng)絡方面的發(fā)展． 參考文獻 [1]Ajtai, M．;?Komlós, J．;?Szemerédi, E．?(1983), "An O(n log n) sorting network",?Proceedings of

26、 the 15th Annual ACM Symposium on Theory of Computing, pp．?1–9,?doi:10．1145/800061．808726,?ISBN?0-89791-099-0． [2]Ajtai, M．; Komlós, J．; Szemerédi, E． (1987), "Deterministic simulation in LOGSPACE",?Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, pp．?132–140,?doi:10．1145/2

27、8395．28410,?ISBN?0-89791-221-7． [3]Alon, Noga (1986)．?"Eigenvalues, geometric expanders, sorting in rounds, and ramsey theory"．?Combinatorica．?6: 207–219．?doi:10．1007/BF02579382． [4]Bobkov, S．; Houdré, C．;?Tetali, P．?(2000), "λ∞, vertex isoperimetry and concentration",?Combinatorica,?20?(2): 153–1

28、72,?doi:10．1007/s004930070018． [5]Dinur, Irit (2007),?"The PCP theorem by gap amplification"(PDF),?Journal of the ACM,?54?(3): 12–es,?doi:10．1145/1236457．1236459． [6]Gillman, D． (1998), "A Chernoff Bound for Random Walks on Expander Graphs",?SIAM Journal on Computing, Society for Industrial and Ap

29、plied Mathematics,?27?(4,): 1203–1220,?doi:10．1137/S0097539794268765． [7]Hoory, Shlomo;?Linial, Nathan;?Widgerson, Avi?(2006),?"Expander graphs and their applications"?(PDF),?Bulletin (New Series) of the American Mathematical Society,?43?(4): 439–561,?doi:10．1090/S0273-0979-06-01126-8． [8]Reingold

30、， O．;?Vadhan， S．;?Wigderson， A．?(2000)， "Entropy waves， the zig-zag graph product， and new constant-degree expanders and extractors"，?Proc． 41st IEEE Symposium on Foundations of Computer Science (FOCS)， pp．?3–13，?doi:10．1109/SFCS．2000．892006． [9]Reingold， O?(2008)， "Undirected connectivity in log-s

31、pace"，?Journal of the ACM，?55?(4): Article 17， 24 pages，?doi:10．1145/1391289．1391291． [10]Reingold， O．;?Trevisan， L．;?Vadhan， S．?(2006)， "Pseudorandom walks on regular digraphs and the RL vs． L problem"，?Proc． 38th ACM Symposium on Theory of Computing (STOC)， pp．?457–466，?doi:10．1145/1132516．1132583 ． [11]Yehudayoff, Amir (2012), "Proving expansion in three steps",?ACM SIGACT News,?43?(3): 67–84,?doi:10．1145/2421096．2421115． [12]Krebs, Mike; Shaheen, Anthony (2011),?Expander families and Cayley graphs: A beginner's guide, Oxford University Press,?ISBN?0-19-976711-4．