这页讲组合群论的一些相关方面(组合群论已发展成一个极广泛的学科,可参考在美国科学院副院长Mac Lane大师的指导下1947年获得哈佛大学博士的Roger C. Lyndon和他的博士Paul Schupp1976年合撰的《组合群论》(Lyndon有一个妇孺皆知的博士Kenneth Appel;也可参考Wilhelm Magnus和其博士合撰的《组合群论》),若精力有限-可先攻涉及图论方面如Cayley,以及比如图论组合群论学家Martin Kneser开创的一些理论(如他提出的Kneser graph vertex transitive 也是 edge transitive),Lyndon的《组合群论》一书也讲Kneser的博士提出的Behr图,等等。

这学科的内容很多如曾和海南琼州大学合作的清华大学数学系党委书记胡教授的著名论文“Group theory method for enumeration of outerplanar graphs

特别是在Cayley图方面发表了在非常多的著名论文。 G是一个群 , S G的一个不含单位元 1的子集 (以后简称为 Cayley子集 ) , G的相对于 S的有向 Cayley D= D (G, S)是一个以 G为顶点集的有向图 ,其中 ,对任意 x , y G, D中有从 x y有方向弧当且仅当 x- 1y S.  S

1= S,D (G,) S对应于一个无向图,称为无向Cayley图或Cayley

 

    Cayley图已在很多方面都进行研究,如在哈密顿性的方面,美国数学协会主席Joseph Gallian教授曾写过Cayley图的哈密顿性的综述文章-Witte, David; Gallian, Joseph A. A survey: Hamiltonian cycles in Cayley graphs.Discrete Math. 51 (1984), no. 3, 293–304.  后来再写这篇综述文章Curran, Stephen J.; Gallian, Joseph A. Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey. Discrete Math. 156 (1996), no. 1-3, 1–18.

   最近这方面的进展很多,下面仅附几篇代表性的论文,在网上可找到更多相关工作:

Pak, Igor; Radoičić, Radoš. Hamiltonian paths in Cayley graphs. Discrete Math. 309 (2009), no. 17, 5501--5508. MR2548568

Kriloff, Cathy; Lay, Terry. Hamiltonian cycles in Cayley graphs of imprimitive complex reflection groups. Discrete Math.326 (2014), 50--60. MR3188987

Christofides, Demetres; Hladký, Jan; Máthé, András. Hamilton cycles in dense vertex-transitive graphs. J. Combin. Theory Ser. B 109 (2014), 34--72. MR3269902

Ghaderpour, Ebrahim; Morris, Dave Witte. Cayley graphs of order $30p$ are Hamiltonian. Discrete Math. 312 (2012), no. 24, 3614--3625. MR2979490 

Kutnar, Klavdija; Marušič, Dragan. Hamilton cycles and paths in vertex-transitive graphs—current directions. Discrete Math.309 (2009), no. 17, 5491--5500. MR2548567

Westlund, Erik E. Hamilton decompositions of 6-regular Cayley graphs on even Abelian groups with involution-free connections sets. Discrete Math. 331 (2014), 117--132. MR3225313

 

国内做得最好的权威专家是北京大学教务处长方新贵教授和该校徐明矅教授.

 

世界四大超一流数学杂志J. AMSAnn. Math.Acta Math.Invent. Math.发表的论文:

Freedman, Michael; Lovász, László; Schrijver, Alexander. Reflection positivity, rank connectivity, and homomorphism of graphs. J. Amer. Math. Soc. 20 (2007), no. 1, 37--51. MR2257396 (我们琼州大学在欧洲数学会的《数学文摘》评论诺贝尔奖获得者M. Freedman国际数学联盟主席L. Lovász等合作这篇论文)

 

Wolf奖获得者国际数学教育联盟主席Whitney, Hassler. The coloring of graphs. Ann. of Math. (2) 33(1932), no. 4, 688--718. MR1503085 

Whitney, Hassler. A theorem on graphs. Ann. of Math. (2) 32(1931), no. 2, 378--390. MR1503003 

 

Kassabov, Martin. Symmetric groups and expander graphs. Invent. Math. 170 (2007), no. 2, 327--354. MR2342639

Eskin, Alex; Fisher, David; Whyte, Kevin. Coarse differentiation of quasi-isometries II: Rigidity for Sol and lamplighter groups. Ann. of Math. (2) 177 (2013), no. 3, 869--910. MR3034290

    Eskin, Alex; Fisher, David; Whyte, Kevin. Coarse differentiation of quasi-isometries I: Spaces not quasi-isometric to Cayley graphs. Ann. of Math. (2) 176 (2012), no. 1, 221--260.MR2925383 

    Bourgain, Jean; Gamburd, Alex. Uniform expansion bounds for Cayley graphs of SL2(Fp).  Ann. of Math. (2) 167(2008), no. 2, 625--642. MR2415383

   Helfgott, Harald A.; Seress, Ákos. On the diameter of permutation groups. Ann. of Math. (2) 179 (2014), no. 2, 611--658. MR3152942

   Aharoni, Ron; Berger, Eli. Menger's theorem for infinite graphs. Invent. Math. 176 (2009), no. 1, 1--62. MR2485879

   Alon, Noga; Makarychev, Konstantin; Makarychev, Yury;Naor, Assaf. Quadratic forms on graphs. Invent. Math. 163(2006), no. 3, 499--522. MR2207233 

van Dam, E. R.; Koolen, J. H. A new family of distance-regular graphs with unbounded diameter. Invent. Math. 162(2005), no. 1, 189--193. MR2198328

   Kenyon, R. The Laplacian and Dirac operators on critical planar graphs. Invent. Math. 150 (2002), no. 2, 409--439. MR1933589

Kenyon, Richard W.; Wilson, David B. Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs. J. Amer. Math. Soc. 28 (2015), no. 4, 985--1030.MR3369907

Hatami, Hamed; Norine, Serguei. Undecidability of linear inequalities in graph homomorphism densities. J. Amer. Math. Soc.24 (2011), no. 2, 547--565. MR2748400 

Giménez, Omer; Noy, Marc. Asymptotic enumeration and limit laws of planar graphs. J. Amer. Math. Soc. 22 (2009), no. 2, 309--329. MR2476775

 

韩国年轻的学者 June Huh, Botong Wang,  Enumeration of points, lines, planes, etc., Acta Mathematica, to appear. 
    June Huh, 
Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs, Journal of the American Mathematical Society 25 (2012), 907-927
.   

  

     信息社会的基础是计算机互连网络,信息交换的关键是通信算法,具有良好性质的互连网络是实现各种有效通信算法和协议的前提。因此,网络模型的设计很大程度上决定了并行分布式系统的性能。一般地,一个优良的互连网络模型应具有如下的拓扑性质:高对称性、低度、低直径、良好的嵌入性和较高的容错性等。由于Cayley图可以具有上述拓扑特性,因此,Cayley图在计算机局域网和大规模并行处理系统的设计与分析中起着重要的作用。

随着无线通信技术的快速发展以及移动终端处理能力的日益增强,移动终端用户可以随时随地访问无线网络服务,P2P网络(P2P网络(Peer-to-Peer network,对等网络)应用扩展到无线网络环境中创造了有利的条件。但是,无线网络高度的动态性、有限的无线链路带宽以及无线节点有限的处理能力等因素使Internet上现有的P2P技术很难直接应用到无线网络环境中。因此,如何在现有的无线网络环境中,充分地利用无线网络的自身优势,使P2P技术在无线网络环境中得到广泛地应用,成为当前亟待解决的研究课题。Cayley图是一种利用群构造图的方法,人们可以使用成熟的代数图论方法分析Cayley图的结构特征和设计Cayley图上的相关算法。特别是由于基于Cayley图的网络模型具有对称性、点传递性、低度、低直径、良好的嵌入性、较高的容错性和路由算法简单等优点,因此,利用代数图论方法研究P2P网络中的相关问题具有较好的理论意义和实用价值。

并行分布系统中,互连网络拓扑结构决定了网络的性能。许多基于Cayley图的互连网络模型被提出,如超立方体网络、Torus网络、蝶网络、de BruijnKautz网络等。学者们一般是针对某种具体的网络结构进行研究,且大多采用直观的方法。由于互连网络表示符号的不同,经常会出现本质相同的网络结构被重复地提出,因此,有必要用基于Cayley图的研究方法来统一处理互连网络拓扑结构问题。

复杂网络广泛存在于自然界和人类社会,是复杂性科学中复杂系统的抽象。继小世界网络和无标度网络模型被提出以来,复杂网络的研究逐渐成为当今科学界研究的前沿和热点,从数学、物理到生命科学,从社会科学到工程技术等众多不同领域的学者开始开展复杂网络的研究,并且在复杂网络的拓扑结构和性质、网络模型、网络的同步、搜索等动力学行为以及网络应用等各个方面都取得了重要成果,这些成果加深了人们对复杂网络的认识,揭示了隐藏在现实世界中的一些普遍规律。然而,相比于网络的复杂性本身而言,这些认识仍是非常局限的,大量的复杂网络的奥秘有待于揭示和研究,更多的实证分析和理论研究工作亟待完成,实际领域的应用也亟待挖掘和探索。Cayley图和代数图论方法有助于对复杂网络的性质、演化模型展开理论.

近年来,随着分布式计算、网格计算、普适计算和移动计算平台的发展,对多点接收的组播通信需求日益增加。覆盖网络是在物理网络上构建的虚拟逻辑网络,它使用分布式散列函数将资源与结点映射到以特定拓扑结构为基础的相同标识符空间中。在以覆盖网络拓扑结构为基础的组播路由问题中,覆盖网络拓扑结构直接影响了组播路由效率的高低,好的拓扑结构能提高组播路由的确定性,并使组播路由简单化。以覆盖网络拓扑结构为基础的组播路由设计的目标是路由时延低、吞吐量大,路由过程简单且具确定性。除此之外,还有如下的几个问题直接影响了虚拟覆盖网络组播路由的可用性和系统效率,对其研究不仅有理论意义也有实用推广价值。首先,物理上相邻的结点映射到覆盖网络后不一定相邻,在构建覆盖网络时考虑结点的物理相邻关系可进一步提升组播路由效率。其次,现有的研究大多单纯利用网络编码技术提高覆盖组播网络的吞吐量,没有充分利用网络编码与覆盖网络拓扑之间的关系。最后,在无线传感器网络中,为节省能量耗散,现有研究没有考虑结合互连网络拓扑来研究以发布订阅模式为基础的以数据为中心的确定性组播路由协议。针对以上几个问题,可构造某些Cayley图使其具有点传递性和对称性,这能降低组播路由的复杂度,并提升系统容错性和查询效率。同时,模型的结点度都为常数度,这在大规模组播系统中能使组播结点的负载不随系统规模无限制地增加。另外,模型中所有结点与边之间的关系均为可计算的,这能使组播路由具确定性可为它们作为基本的拓扑模型,来满足覆盖网络组播对自组织性和可扩展性的要求。

  Cayley图在计算机互连网络等的应用已非常广泛,:

基于Cayley图的六度环绕网络研究

张震肖文俊黄书强;邓玉辉

计算机学报

2014/02

2

基于Cayley图的三维六度环面网络研究

张震肖文俊黄书强

软件学报

2015/07

一种具有小世界网络特征的常数度结构化覆盖网络

梁活民肖文俊

计算机学报

2010/09

迪卡尔乘积图到Cayley中的嵌入

赵猛方滨兴王义和;胡铭曾

计算机学报

2000/06

Biswapped网络(BSN)的拓扑性质研究:点对称性和极大容错性

陈卫东肖文俊

计算机学报

2010/05

任意k紧优、奇异k紧优双环网无限族的构造

陈协彬陈宝兴孟吉翔肖文俊

中国科学(A:数学)

2007/06

    正则性引理(Regularity Lemma)的提出极大的促进了极值图论的发展。2014年首尔国际数学家大会中,有两位45分钟邀请报告人(KühnOsthus)的研究工作是关于极值图论的研究进展,应用的主要研究工具是正则性引理。特别的,正则性引理的提出者世界著名数学家Szemerédi2012年获得世界三大国际数学奖之一的阿贝尔奖