膨胀图族的锯齿积构造

苏州大学本科生毕业论文 题 目膨胀图的锯齿积构造目录第1章 膨胀图2第2章 G=Z群的概念2第3章 邻接算子3第4章 CAYLEY图介绍3第5章 锯齿积4 第51节 的来源4 第52节 一个实际的膨胀图族6摘要 在组合学中，膨胀图是一个具有强连通性的稀疏图，由顶点，边和频谱扩展可以确定膨胀图的发展进一步推动了计算机网络的发展，在设计算法，错误校正码等许多方面都取得不少突破单个膨胀图的用处并不大，人们更多的是对一族膨胀图进行研究目前构造膨胀图族的主流方法有三种，本文中重点讨论的是锯齿积(Zig-zag Product)构造 Incombinatorics, anexpander graphis asparse graphthat has strongconnectivityproperties, quantified usingvertex,edgeor spectral expansion as described belowExpander constructions have spawned research in pure and applied mathematics, with several applications tocomplexity theory, design of robustcomputer networks, and the theory oferror-correcting codes There are three general strategies for constructing families of expander graphs11The first strategy is algebraic and group-theoretic, the second strategy is analytic and usesadditive combinatorics, and the third strategy is combinatorial and uses thezig-zagand related graph productsNoga Alonshowed that certain graphs constructed fromfinite geometriesare the sparsest examples of highly expanding graphs 关键词 膨胀图(Expander Graph),锯齿积(Zig-zag Product)前言 目前，学术界对膨胀图及锯齿积进行了大量的研究和实践，取得了一批具有启发性，建设性的成果，为用锯齿积构造膨胀图族构建了完善的理论参考本段对国内外部分学者的有关研究进行了梳理和总结 膨胀图是一个具有强连通性的稀疏图每一个连通图都是一个膨胀图但是，不同的连通图具有不同的膨胀参数，例如点膨胀4，边膨胀7，谱膨胀7膨胀图的发展进一步加深了对数学与应用数学的研究最初研究膨胀图的动机是建立稳固的节约成本的网络，目前膨胀图在计算科学领域有大量应用，在设计算法，错误校正码7，提取器，伪随机数生成器，排序网络1和稳固计算机网络方面都取得了不少突破它们同样被使用来证明复杂计算理论中的许多重要结论，例如SL=L10和PCP定理5在密码系统中，膨胀图族被用来构造散列函数下面的一些膨胀图族的特性在许多领域都被证明很有用，例如膨胀图混合引理(Expander mixing lemma)，膨胀图回路抽样(Expander walk sampling)26，脑图膨胀特性 目前构造一族膨胀图的主流方法有三种11第一种方法是利用代数和群理论构造，第二种通过分析法和加法论来构造，第三种即为本文中将要证明的锯齿积构造法，Noga Alon证明了有限几何学上构造的一族特定的图即为膨胀图族的一个极佳的例子3 锯齿积是由Reingold，Vadhan & Wigderson8首次提出的在2002年，Omer Reingold，Salil Vadhan和Avi Wigderson给出了一个简单明确的构造一族有固定度数的膨胀图族的方法构造法是迭代的，并且需要一个满足相关条件的基础图在每次迭代过程中，锯齿积被用来生成另一个保持原有性质不变的图，通过不断迭代，最终生成一族膨胀图再后来又被用来证明复杂计算理论中symmetric logspace 和 logspace是相等的9 本文中重点描述的是如何通过给定的基础图来构造一族膨胀图，并且验证构造过程是合理的 正文第1章 膨胀图 X=(V，E)为图，V为它的顶点集，E为它的边集如果没有特别声明，总假定X是无圈的有限图 定义11 X=(V，E)为有限图，记 为X的膨胀常数(还可以称为等周常数或Cheeger常数)这里AV，A为A的邻居，也就是不在A中，但与A中的点相连接的那些点 定义12 X为正则有限图(即每个顶点的度为恒定的k)对于，X称为-膨胀图如果 对于连通图而言，若顶点数为，取，那么对任何非空的且，总有，因此膨胀图的定义对单个图而言意义并不十分大人们更多的是考虑一族正则图的膨胀常数，一般还要求正则度数是固定的，并且这族图的顶点数目是趋于无穷的 定义13 为一族有限的连通正则图，且，这里是的顶点集，如果存在，使得 ，就称是一族膨胀图 第2章 G=Z8 p 群的概念 整数集合Z对于加法+而言作成整数加群；所有的模n剩余类构成的集合是整数集合的一个分类(对应的是整数集合上的同余关系)，现将所有的模n剩余类构成集合记作Zn，即Zn=r|r=0，1，n-1其中r=qm+r|q=0，1，2， 模n剩余类加法:设a=a，b=b则a+b=a+b称此运算为模n剩余类加法，记 ab=a+b 模n剩余类集合Zn对于模n剩余类加法构成的群称为模n剩余类加群 类似可有第3章 邻接算子 定义31 令S为有限集定义复向量空间如下 令且向量空间上加法运算为数乘运算为标准内积和范数分别为，当表示标准内积和标准范数时，下标可以省略，简记为 定义32 令X为一个图，其顶点分别为则X的邻接矩阵为矩阵A，其中Ai，j等于以vi，vj为两顶点的边的数目 例如，在右下图中，12 备注33 假定图X的顶点集V为，令A为X的邻接矩阵给定，则可将f看作Cn中的向量则因此由公式 (1) 可将A视为从到其自身的一个线性转换定义34 由(1)式定义出的线性算子A称为X的邻接算子第四章 CAYLEY图介绍 定义41 一个集合的元素如果在该集合中出现次数大于1，则称该集合为多重集元素在该多重集中出现的次数称为该元素的多重性如果S为一个多重集，则|S|表示S中元素的个数 例42 考虑多重集元素的多重性为3，-1的多重性为2，元素4，x和15的多重性皆为1，故|S| 定义43 令G为一个群，为G的一个多重子集如果对于任意的多重性为n，同样为中多重性为n的元素，则称是对称的如果是G的对称多重子集，则记G 定义44 令G为一个群且G则G关于的Cayley图记为 Cay(G， )，定义如下：Cay(G， )的顶点是G的元素G中两个顶点x，y相邻等价于(即)边(x，y)在边集E中的多重性等于中的多重性 引理45 令G为一个群且G，则下述结论成立1 Cay(G， )是|正则的2 Cay(G， )连通等价于生成群G第5章 锯齿积 第1节 的来源 令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中的顶点，则此两点间边的数目等于有序边对的数目，其中z1，z2必须满足下列条件: y1为z1的终点，y2为z2的终点且 例51 在下面给出的图X，Y中，有VX=a，b，VY=1，2，3注意到X为3正则图，且|Y|=3所以一旦选好标号，就可以定义X和Y的锯齿积12 1212 取EX=e1，e2，e3，e4，其中e1为顶点a处的环；e2为顶点b处的环；e3为顶点a，b间的顶边；e4为顶点a，b间的底边则Ea=e1，e3，e4，Eb=e2，e3，e4定义La，Lb如下: La(1)=e3 Lb(1)=e3La(2)=e4 Lb(2)=e4La(3)=e1 Lb(3)=e2我们通过标记X中每个顶点处的边来描述L=La，Lb，如图所示 问：a1与b3有几条边相连？即满足的边对数目 只有此时，故a1，b3之间有边对(s，u)与(r，u)寻找zig-zag product的边的过程，实际上是以下操作的多次进行 备注52 令(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的相邻点有哪些？(zig) 不妨考虑z1=s(hyphen) ， ， 指针在b2(zag) 因此a1与b1，b3相邻同样的考虑z1=r，最终结果与上面相同再考虑z1=t，得a1与a1，a2，a3相连，重数分别为1，1，1综上a1分别与a1，a2，a3，b1，b3相连，重数分别为1，1，1，4，2第2节 一个实际的膨胀图族 在本段中，我们将用迭代法构造出一族膨胀图开始之前，我们先给出一个基本图W我们会发现图W必须要满足几个条件才能更好地定义出构造，同时必须符合定理526来保证谱隙一致有界不为零现在明确地给出一个正则的非二部图W满足|W|=d4 W，(W)我们开始对这个图进行构造 令p为大于35的质数令G=Z8 p换句话说，G为Zp的8次笛卡尔积 定义：Z2 pG，(x，y)=(x，xy，xy2，xy3，xy4，xy5，xy6，xy7)令=(x，y)|(x，y)Z2 p(这里我们把看作多重集，不是一般集)记G 令 W=Cay(G，)令=e 定义53 取aG记作a=(a0，a1，a2，a3，a4，a5，a6，a7)对任意a，bG，定义ab=a0b0+a1b1+a2b2+a3b3+a4b4+a5b5+a6b6+a7b7记G的单位元为0 引理54 令为整数令则 引理55 证明： 当c0，由|G|=p8可以立即得出当c0时，存在j使得cj0不失一般性，令c00 ，最后一等式由引理54给出 对任意aG，定义faL2(W):fa(x)(注意到wp=1，fa是定义良好的)令A为W的邻接算子（adjacency operator）定义a现在来证明W的特征值就是 引理56 对于任意aG，有Afaafa证明：bG，有 (Afa)(b) afa(b) 引理57 令V为内积空间，若形成一组非零正交向量，则线性无关 引理58 fa|aG是一个线性无关集合证明： 我们将要证0，ab由引理57可推断如下等式 0最后一等式由引理55得到 引理59 W的每个特征值都等于某个，其中证明： 由引理56，每个fa都是W的特征值a的一个特征向量通过引理58以及向量组fa的数量恰好为|W|，可以看出向量组fa组成正交特征基 引理510 a0，有0a7p证明： a 定义多项式g(t)=a0+a1t+a7t7对任意给定的yZp，由引理62得 因此a=np，n为g在Zp中根的数量由于a0，故g是一个不大于7次的非零多项式，所以n7下面的引理列举了我们需要的W的性质 引理511 令W=Cay(G，)，则1|W|=，2W是非二部的，3证明:1|W|=|G|=p8，dW=|=p22由引理59和引理510可知，-2不是W的特征值3由引理59，引理510，和p35，可得 定义512 令X为有限图，顶点集为V定义Xn的顶点集仍为V，从v1到v2的边的重数等于X中从v1到v2步长为n的路径数目即，Xn为X的n次积 终于，我们可以定义一个实际的膨胀图族 定义513 令W=Cay(G，)，按如下规则递归地定义(Wn) W1=W2， Wn+1=W2 nW 其中W2 nW由任意从W到W2 n的标记形成 引理514 令X，Y，L如52定义，则XLY为-正则图 备注515 对引理514 用归纳法可以直接得出(W2 n)的度=p8=|W|，上式对任意正整数n皆成立，故锯齿积W2 nW的构造是合理的 引理516 令X为有限图，特征值为则Xj的特征值为 引理517 令X为-正则非二部图，Y为-正则非二部图，且有则对任意从X到Y的标号有 (XY) 引理518 令(Xn)为一系列d-正则图，且则(Xn)为一族膨胀图一致有界不为零 定理519 令(Wn)按照定义513定义则(Wn)是一膨胀图族证明： 首先，由命题514，得deg(Wn)=p4对任意n成立再由归纳法得|Wn|=p8n，则|Wn|现在我们通过归纳来证对任意n，(Wn)35，有 这创建了基本情形为了归纳，假定(Wn)2p4/5由引理535，我们知道W非二部由引理511，引理516及引理517，得 (W2 nW)+p2(W)+(W)2 结论 用锯齿积来构造一族膨胀图被证实是可行的，这使得在计算机领域可通过迭代算法来构造出膨胀图族，从而进一步推动了膨胀图在计算机网络方面的发展参考文献1Ajtai, M;Komls, J;Szemerdi, E(1983), An O(n log n) sorting network,Proceedings of the 15th Annual ACM Symposium on Theory of Computing, pp19,doi:101145/800061808726,ISBN0-89791-099-02Ajtai, M; Komls, J; Szemerdi, E (1987), Deterministic simulation in LOGSPACE,Proceedings of the 19th Annual ACM Symposium on Theory of Computing, ACM, pp132140,doi:101145/2839528410,ISBN0-89791-221-73Alon, Noga (1986)Eigenvalues, geometric expanders, sorting in rounds, and ramsey theoryCombinatorica6: 207219doi:101007/BF025793824Bobkov, S; Houdr, C;Tetali, P(2000), , vertex isoperimetry and concentration,Combinatorica,20(2): 153172,doi:101007/s0049300700185Dinur, Irit (2007),The PCP theorem by gap amplification(PDF),Journal of the ACM,54(3): 12es,doi:101145/123645712364596Gillman, D (1998), A Chernoff Bound for Random Walks on Expander Graphs,SIAM Journal on Computing, Society for Industrial and Applied Mathematics,27(4,): 12031220,doi:101137/S00975397942687657Hoory, Shlomo;Linial, Nathan;Widgerson, Avi(2006),Expander graphs and their applications(PDF),Bulletin (New Series) of the American Mathematical Society,43(4): 439561,doi:101090/S0273-0979-06-01126-88Reingold， 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)， pp313，doi:101109/SFCS20008920069Reingold， O(2008)， Undirected connectivity in log-space，Journal of the ACM，55(4): Article 17， 24 pages，doi:101145/1391289139129110Reingold， 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)， pp457466，doi:101145/11325161132583 11Yehudayoff, Amir (2012), Proving expansion in three steps,ACM SIGACT News,43(3): 6784,doi:101145/2421096242111512Krebs, Mike; Shaheen, Anthony (2011),Expander families and Cayley graphs: A beginners guide, Oxford University Press,ISBN0-19-976711-411