膨脹圖族的鋸齒積構(gòu)造分析研究數(shù)學(xué)與應(yīng)用數(shù)學(xué)專業(yè)

目錄 第1章 膨脹圖………………………………………………………2 第2章 G=Z群的概念…………………………………………2 第3章 鄰接算子………………………………………………3 第4章 CAYLEY圖介紹……………………………………………3 第5章 鋸齒積………………………………………………………4 第5．1節(jié) 的來源……………………………………………4 第5．2節(jié) 一個(gè)實(shí)際的膨脹圖族…………………………………6 摘要 在組合學(xué)中，膨脹圖是一個(gè)具有強(qiáng)連通性的稀疏圖，由頂點(diǎn)，邊和頻譜擴(kuò)展可以確定．膨脹圖的發(fā)展進(jìn)一步推動(dòng)了計(jì)算機(jī)網(wǎng)絡(luò)的發(fā)展，在設(shè)計(jì)算法，錯(cuò)誤校正碼等許多方面都取得不少突破．單個(gè)膨脹圖的用處并不大，人們更多的是對(duì)一族膨脹圖進(jìn)行研究．目前構(gòu)造膨脹圖族的主流方法有三種，本文中重點(diǎn)討論的是鋸齒積(Zig-zag Product)構(gòu)造． In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion 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 expander 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 the sparsest examples of highly expanding graphs． 關(guān)鍵詞 膨脹圖(Expander Graph),鋸齒積(Zig-zag Product) 前言 目前，學(xué)術(shù)界對(duì)膨脹圖及鋸齒積進(jìn)行了大量的研究和實(shí)踐，取得了一批具有啟發(fā)性，建設(shè)性的成果，為用鋸齒積構(gòu)造膨脹圖族構(gòu)建了完善的理論參考．本段對(duì)國(guó)內(nèi)外部分學(xué)者的有關(guān)研究進(jìn)行了梳理和總結(jié)． 膨脹圖是一個(gè)具有強(qiáng)連通性的稀疏圖．每一個(gè)連通圖都是一個(gè)膨脹圖．但是，不同的連通圖具有不同的膨脹參數(shù)，例如點(diǎn)膨脹[4]，邊膨脹[7]，譜膨脹[7]．膨脹圖的發(fā)展進(jìn)一步加深了對(duì)數(shù)學(xué)與應(yīng)用數(shù)學(xué)的研究．最初研究膨脹圖的動(dòng)機(jī)是建立穩(wěn)固的節(jié)約成本的網(wǎng)絡(luò)，目前膨脹圖在計(jì)算科學(xué)領(lǐng)域有大量應(yīng)用，在設(shè)計(jì)算法，錯(cuò)誤校正碼[7]，提取器，偽隨機(jī)數(shù)生成器，排序網(wǎng)絡(luò)[1]和穩(wěn)固計(jì)算機(jī)網(wǎng)絡(luò)方面都取得了不少突破．它們同樣被使用來證明復(fù)雜計(jì)算理論中的許多重要結(jié)論，例如SL=L[10]和PCP定理[5]．在密碼系統(tǒng)中，膨脹圖族被用來構(gòu)造散列函數(shù)．下面的一些膨脹圖族的特性在許多領(lǐng)域都被證明很有用，例如膨脹圖混合引理(Expander mixing lemma)，膨脹圖回路抽樣(Expander walk sampling)[2][6]，腦圖膨脹特性． 目前構(gòu)造一族膨脹圖的主流方法有三種[11]．第一種方法是利用代數(shù)和群理論構(gòu)造，第二種通過分析法和加法論來構(gòu)造，第三種即為本文中將要證明的鋸齒積構(gòu)造法，Noga Alon證明了有限幾何學(xué)上構(gòu)造的一族特定的圖即為膨脹圖族的一個(gè)極佳的例子[3]． 鋸齒積是由Reingold，Vadhan & Wigderson[8]首次提出的．在2002年，Omer Reingold，Salil Vadhan和Avi Wigderson給出了一個(gè)簡(jiǎn)單明確的構(gòu)造一族有固定度數(shù)的膨脹圖族的方法．構(gòu)造法是迭代的，并且需要一個(gè)滿足相關(guān)條件的基礎(chǔ)圖．在每次迭代過程中，鋸齒積被用來生成另一個(gè)保持原有性質(zhì)不變的圖，通過不斷迭代，最終生成一族膨脹圖．再后來又被用來證明復(fù)雜計(jì)算理論中symmetric logspace 和 logspace是相等的[9]． 本文中重點(diǎn)描述的是如何通過給定的基礎(chǔ)圖來構(gòu)造一族膨脹圖，并且驗(yàn)證構(gòu)造過程是合理的． 正文 第1章 膨脹圖 X=(V，E)為圖，V為它的頂點(diǎn)集，E為它的邊集．如果沒有特別聲明，總假定X是無(wú)圈的有限圖． 定義1．1 X=(V，E)為有限圖，記 為X的膨脹常數(shù)(還可以稱為等周常數(shù)或Cheeger常數(shù))．這里AV，A為A的鄰居，也就是不在A中，但與A中的點(diǎn)相連接的那些點(diǎn)． 定義1．2 X為正則有限圖(即每個(gè)頂點(diǎn)的度為恒定的k)．對(duì)于，X稱為-膨脹圖如果． 對(duì)于連通圖而言，若頂點(diǎn)數(shù)為，取，那么對(duì)任何非空的且，總有，因此膨脹圖的定義對(duì)單個(gè)圖而言意義并不十分大．人們更多的是考慮一族正則圖的膨脹常數(shù)，一般還要求正則度數(shù)是固定的，并且這族圖的頂點(diǎn)數(shù)目是趨于無(wú)窮的． 定義1．3 為一族有限的連通正則圖，且，這里是的頂點(diǎn)集，如果存在，使得 ，就稱是一族膨脹圖． 第2章 G=Z8 p 群的概念 整數(shù)集合Z對(duì)于加法+而言作成整數(shù)加群；所有的模n剩余類構(gòu)成的集合是整數(shù)集合的一個(gè)分類(對(duì)應(yīng)的是整數(shù)集合上的同余關(guān)系)，現(xiàn)將所有的模n剩余類構(gòu)成集合記作Zn， 即Zn={[r]|r=0，1…，n-1} 其中[r]={qm+r|q=0，±1，±2，…} 模n剩余類加法: 設(shè)[a]=[a']，[b]=[b'] 則[a+b]=[a'+b'] 稱此運(yùn)算為模n剩余類加法，記 [a][b]=[a'+b'] 模n剩余類集合Zn對(duì)于模n剩余類加法構(gòu)成的群稱為模n剩余類加群． ． 類似可有． 第3章 鄰接算子 定義3．1 令S為有限集．定義復(fù)向量空間如下 ． 令且．向量空間上加法運(yùn)算為．?dāng)?shù)乘運(yùn)算為．標(biāo)準(zhǔn)內(nèi)積和范數(shù)分別為，．當(dāng)表示標(biāo)準(zhǔn)內(nèi)積和標(biāo)準(zhǔn)范數(shù)時(shí)，下標(biāo)可以省略，簡(jiǎn)記為． 定義3．2 令X為一個(gè)圖，其頂點(diǎn)分別為．則X的鄰接矩陣為矩陣A，其中Ai，j等于以vi，vj為兩頂點(diǎn)的邊的數(shù)目． 例如，在右下圖中， [12] 備注3．3 假定圖X的頂點(diǎn)集V為{}，令A(yù)為X的鄰接矩陣．給定，則可將f看作Cn中的向量．則 ． 因此由公式 (1) 可將A視為從到其自身的一個(gè)線性轉(zhuǎn)換． 定義3．4 由(1)式定義出的線性算子A稱為X的鄰接算子． 第四章 CAYLEY圖介紹 定義4．1 一個(gè)集合的元素如果在該集合中出現(xiàn)次數(shù)大于1，則稱該集合為多重集．元素在該多重集中出現(xiàn)的次數(shù)稱為該元素的多重性．如果S為一個(gè)多重集，則|S|表示S中元素的個(gè)數(shù)． 例4．2 考慮多重集．元素的多重性為3，-1的多重性為2，元素4，x和15的多重性皆為1，故|S|＝８． 定義4．3 令G為一個(gè)群，為G的一個(gè)多重子集．如果對(duì)于任意的多重性為n，同樣為中多重性為n的元素，則稱是對(duì)稱的．如果是G的對(duì)稱多重子集，則記G 定義4．4 令G為一個(gè)群且G．則G關(guān)于的Cayley圖記為 Cay(G， )，定義如下：Cay(G， )的頂點(diǎn)是G的元素．G中兩個(gè)頂點(diǎn)x，y相鄰等價(jià)于．(即．)邊(x，y)在邊集E中的多重性等于中的多重性． 引理4．5 令G為一個(gè)群且G，則下述結(jié)論成立 1． Cay(G， )是||正則的． 2． Cay(G， )連通等價(jià)于生成群G． 第5章 鋸齒積 第1節(jié) 的來源 令X為dx-正則圖，Y為dy-正則圖且滿足dX=|Y|=VY．令VX，VY分別為X，Y的頂點(diǎn)集，令EX，EY分別為X，Y的多重邊集，多重邊視作不同元素．，令，令為雙射．(dX=|Y|保證了Lv的存在．)稱Lv為v上的標(biāo)號(hào)．令，稱L是從Y到X的標(biāo)號(hào)． 定義鋸齒積XLY如下．XLY的頂點(diǎn)集為XY的笛卡爾積．如果(x1，y1)和(x2，y2)皆為XLY中的頂點(diǎn)，則此兩點(diǎn)間邊的數(shù)目等于有序邊對(duì)的數(shù)目，其中z1，z2必須滿足下列條件: y1為z1的終點(diǎn)，y2為z2的終點(diǎn)且． 例5．1 在下面給出的圖X，Y中，有VX={a，b}，VY={1，2，3}．注意到X為3正則圖，且|Y|=3．所以一旦選好標(biāo)號(hào)，就可以定義X和Y的鋸齒積． [12] [12] [12] 取EX={e1，e2，e3，e4}，其中e1為頂點(diǎn)a處的環(huán)；e2為頂點(diǎn)b處的環(huán)；e3為頂點(diǎn)a，b間的頂邊；e4為頂點(diǎn)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 我們通過標(biāo)記X中每個(gè)頂點(diǎn)處的邊來描述L={La，Lb}，如圖所示． 問：a1與b3有幾條邊相連？即滿足的邊對(duì)數(shù)目 只有此時(shí)， 故a1，b3之間有邊對(duì)(s，u)與(r，u)． 尋找zig-zag product的邊的過程，實(shí)際上是以下操作的多次進(jìn)行． 備注5．2 令(x1，y1)為XLY中一頂點(diǎn)，為找到其它與其相鄰的頂點(diǎn)(x2，y2)，進(jìn)行如下操作． 步驟1(zig):在Y中選一條邊z1，以y1為頂點(diǎn)，指針移動(dòng)到(x1，z1(y1))． 步驟2(hyphen):x2為的另一個(gè)端點(diǎn)，，指針移動(dòng)到(x2，y')． 步驟3:(zag):在Y中選一條邊z2，以y'為頂點(diǎn)，y2=z2(y')，指針移動(dòng)到(x2，y2)． 問上例中a1的相鄰點(diǎn)有哪些？ (zig) 不妨考慮z1=s (hyphen) ， ， 指針在b2 (zag) 因此a1與b1，b3相鄰．同樣的考慮z1=r，最終結(jié)果與上面相同． 再考慮z1=t，得a1與a1，a2，a3相連，重?cái)?shù)分別為1，1，1． 綜上a1分別與a1，a2，a3，b1，b3相連，重?cái)?shù)分別為1，1，1，4，2． 第2節(jié) 一個(gè)實(shí)際的膨脹圖族 在本段中，我們將用迭代法構(gòu)造出一族膨脹圖．開始之前，我們先給出一個(gè)基本圖W．我們會(huì)發(fā)現(xiàn)圖W必須要滿足幾個(gè)條件才能更好地定義出構(gòu)造，同時(shí)必須符合定理5．26來保證譜隙一致有界不為零．現(xiàn)在明確地給出一個(gè)正則的非二部圖W滿足|W|=d4 W，λ(W)≤．我們開始對(duì)這個(gè)圖進(jìn)行構(gòu)造． 令p為大于35的質(zhì)數(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)．對(duì)任意a，b∈G，定義 ab=a0b0+a1b1+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7．記G的單位元為0． 引理5．4 令為整數(shù)．令．則 ． 引理5．5 證明： 當(dāng)c＝0，由|G|=p8可以立即得出．當(dāng)c≠0時(shí)，存在j使得cj≠0． 不失一般性，令c0≠0． ， 最后一等式由引理5．4給出． 對(duì)任意aG，定義faL2(W):fa(x)＝．(注意到wp=1，fa是定義良好的)． 令A(yù)為W的鄰接算子（adjacency operator）．定義λa＝．現(xiàn)在來證明W的特征值就是． 引理5．6 對(duì)于任意aG，有Afa＝λafa 證明： bG，有 (Afa)(b) ＝ ＝ ＝λafa(b)． 引理5．7 令V為內(nèi)積空間，，若形成一組非零正交向量，則線性無(wú)關(guān)． 引理5．8 {fa|aG}是一個(gè)線性無(wú)關(guān)集合． 證明： 我們將要證<fa，fb>＝0，a≠b．由引理5．7可推斷如下等式 <fa，fb>＝ ＝ ＝ ＝＝0 最后一等式由引理5．5得到． 引理5．9 W的每個(gè)特征值都等于某個(gè)，其中． 證明： 由引理5．6，每個(gè)fa都是W的特征值λa的一個(gè)特征向量．通過引理5．8以及向量組fa的數(shù)量恰好為|W|，可以看出向量組fa組成正交特征基． 引理5．10 a≠0，有0≤λa≤7p． 證明： λa＝ ＝ ＝． 定義多項(xiàng)式g(t)=a0+a1t+．．．+a7t7．對(duì)任意給定的yZp，由引理6．2得 因此λa=np，n為g在Zp中根的數(shù)量．由于a0，故g是一個(gè)不大于7次的非零多項(xiàng)式，所以n7． 下面的引理列舉了我們需要的W的性質(zhì)． 引理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為有限圖，頂點(diǎn)集為V．定義Xn的頂點(diǎn)集仍為V，從v1到v2的邊的重?cái)?shù)等于X中從v1到v2步長(zhǎng)為n的路徑數(shù)目．即，Xn為X的n次積． 終于，我們可以定義一個(gè)實(shí)際的膨脹圖族． 定義5．13 令W=Cay(G，Г)，按如下規(guī)則遞歸地定義(Wn) W1=W2， Wn+1=W2 nW 其中W2 nW由任意從W到W2 n的標(biāo)記形成． 引理5．14 令X，Y，L如5．2定義，則XLY為-正則圖． 備注5．15 對(duì)引理5．14 用歸納法可以直接得出(W2 n)的度=p8=|W|，上式對(duì)任意正整數(shù)n皆成立，故鋸齒積W2 nW的構(gòu)造是合理的． 引理5．16 令X為有限圖，特征值為．則Xj的特征值為． 引理5．17 令X為-正則非二部圖，Y為-正則非二部圖，且有． 則對(duì)任意從X到Y(jié)的標(biāo)號(hào)有 (XY)． 引理5．18 令(Xn)為一系列d-正則圖，且． 則(Xn)為一族膨脹圖一致有界不為零． 定理5．19 令(Wn)按照定義5．13定義．則(Wn)是一膨脹圖族． 證明： 首先，由命題5．14，得deg(Wn)=p4對(duì)任意n成立．再由歸納法得|Wn|=p8n，則|Wn|→∞． 現(xiàn)在我們通過歸納來證對(duì)任意n，λ(Wn)<2p4/5．這意味著對(duì)任意n，Wn的譜隙至少為3p4/5，所以由引理5．18，這足夠來證明(Wn)是一族膨脹圖． 與此同時(shí)，W2 n是非二分的，因?yàn)槿我庖粋€(gè)有一條邊的圖的平方至少有一個(gè)環(huán)． 由引理5．16，引理5．11及p>35，有 ． 這創(chuàng)建了基本情形．為了歸納，假定λ(Wn)<2p4/5．由引理5．35，我們知道W非二部．由引理5．11，引理5．16及引理5．17，得 λ (W2 nW)+p2λ(W)+λ(W)2 ． 結(jié)論 用鋸齒積來構(gòu)造一族膨脹圖被證實(shí)是可行的，這使得在計(jì)算機(jī)領(lǐng)域可通過迭代算法來構(gòu)造出膨脹圖族，從而進(jìn)一步推動(dòng)了膨脹圖在計(jì)算機(jī)網(wǎng)絡(luò)方面的發(fā)展． 參考文獻(xiàn) [1]Ajtai, M．; Komlós, J．; Szemerédi, E． (1983), "An O(n log n) sorting network", Proceedings of 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/28395．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–172, 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 Applied 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， 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-space"， 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．