图论中的组合方法和概率方法

论文摘要

一个图如果其性质如顶点、边或者顶点与边之间的关系具有随机性,我们通常称之为随机图。随机图理论创始于Erd（o|¨）s与Rényi在上个世纪50年代末60年代初发表的一系列论文,他们发现概率方法在处理图论的某些问题时非常有用。现在,随机图理论在很多方面都有一些很漂亮的结果,如随机图的进化过程、极限分布、子图理论、极图理论以及Ramsey理论等等。作为离散数学的一个重要分支,随机图在其他学科,如计算机科学、化学、社会学及生物学等都有广泛的应用。另一方面,概率理论也已经成为图论研究的一种越来越重要的工具。本篇论文主要包括三个部分:第一部分是序言（第1章）,第二部分我们主要是研究随机多重图和随机超图的度序列的分布问题（第2,3,4章）,第三部分我们主要研究关于边染色超图的彩色的哈密顿圈和H-因子问题（第5,6章）。在本文中,如果在一个随机图模型中,一个图性质Q满足limn→∞P{Q}=1,那么我们就说在该空间中几乎所有的图都具有性质Q。假设n是一个自然数,r是一个固定的自然数,ni=ni（n）（1≤i≤r）是一系列关于n的非负整值函数且满足n1+n2+…+nr=n。作为经典随机二部图的的一种推广,随机r一致r部随机超图模型H（n1,n2,…,nr;n,p）定义如下:（ⅰ）样本空间由所有具有顶点划分V={V1,V2,…,Vr}且每条（超）边恰好有一个端点落在Vi（1≤i≤r）的r一致r部超图组成;（ⅱ）multiply from i=1 to r ni条边中的每一条边被选取构成超图的概率是p（0＜p＜1）,且不同边的选取互相独立。在第二章,我们研究了随机r一致r部随机超图模型H（n1,n2,…,nr;n,p）中的随机超图在V1中的度序列的分布问题。△V1=△V1（H）和δV1=δV1（H）分别表示图H在V1中的最大度和最小度;Xd,V1=Xd,V1（H）,Yd,V1=Yd,V1（H）,Zd,V1=Zd,V1（H）和Zc,d,V1=Zc,d,V1（H）分别表示图H在V1中度为d,度大于或等于d,度小于或等于d,和度大于或等于c且小于或等于d的顶点数目。在第二章,我们证明在随机r一致r部随机超图空间H（n1,n2,…,nr;n,p）中,随机变量Xd,V1,Yd,V1,Zd,V1,及Zc,d,V1都近似服从Poisson分布。另一方面,我么也考虑了下面两个问题:（ⅰ）当p满足什么条件时,我们能找到一个关于n的整值函数D（n）使得在空间H（n1,n2,…,nr;n,p）中,limn→∞P{△V1=D（n）}=1?（ⅱ）当p满足什么条件时,在空间H（n1,n2,…,nr;n,p）中,几乎所有的超图在V1的最大度顶点是唯一的?我们证明了第一个问题的答案是p=o（log n1/N）,而第二个问题的答案是Np/log n1→∞。假设d1,V1（H）≥d2,V1（H）≥…≥dn1,V1（H）是H在V1的度序列。考虑完度序列中最大度和最小度的情况之后,我们考虑了度序列中一般元素di,V1的分布问题,另外我们还对di,V1—di+1,V1给出了一个估计。在第三章,我们把经典二项随机图模型推广到多重随机图模型G（n;{pk}）,定义如下:（ⅰ）样本空间由所有以V={v1,v2,…,vn}为顶点集的无自同环多重图组成;（ⅱ）若用随机变量tvi,vj（1≤i＜j≤n）表示顶点vi与vj之间存在的边数。则tvi,vj（1≤i＜j≤n）相互独立,且服从同分布:P{tvi,vj=k}=pk,k=0,1,2,…其中pk≥0且sum from k=0 to∞pk=1。首先,我们给出了在空间G（n;{pk}）中多重图的度序列近似服从Poisson分布的一个充分条件。然后,为了改进这个结果,我们还分别考查了当{pk}服从几何分布、二项分布及Poisson分布的情况,并给出了充要条件。在第四章,我们把经典随机二部图模型推广到随机多重二部图模型G（n,m;{pk}）,定义如下:（ⅰ）样本空间由所有以A∪B为顶点集的无自同环多重二部图组成,其中A={a1,a2,…,an},B={b1,b2,…,bm};（ⅱ）若用随机变量tai,bj（1≤i≤n,1≤j≤m）表示顶点ai与bj之间存在的边数。则tai,bj（1≤i≤n,1≤j≤m）相互独立,且服从同分布:P{tai,bj=k}=pk,k=0,1,2,…其中pk≥0且sum from k=0 to∞pk=1。在这一章我们得到一些类似于第二章的结果。另一方面,图的染色理论在图论中占很重要的地位。近年来,对图的染色问题的研究变得异常活跃,得到了一系列漂亮的结果,也产生了很多新的研究方法,其中包括概率方法。在第5,6章我们考虑了边染色超图中的彩色H-因子和彩色哈密顿圈问题。我们说一个边染色子图是彩色的,如果该子图的任意两条边的颜色都不一样。假设H是图G的一个子图,我们称G的一个满足每个连通分支都同构于H的生成子图为G的一个H-因子,且如果每个连通分支都是彩色的H,那么我们就称之为G的一个彩色H-因子。在第五章,我们用概率方法证明了如果一个具有n个顶点的完全3一致超图Kn3的边染色满足任意一种颜色出现的次数不超过[cn]次,则该染色包含一个每一条边颜色都不一样的哈密顿圈,其中c是满足c<1/1152的任意常数。在第六章,我们用概率方法证明了如果h,r和s是正整数且满足s≤r≤h,H是具有h个顶点且满足x（H）=r的s一致超图,那么我们可以找到一个常数k=k（h,r,s）使得任何正常边染色的超图Ts,r（k）都包含一个每条边颜色都不一样的彩色的H-因子,其中Ts,r（k）是顶点划分为{V1,V2,…,Vr}且|Vi|=k（1≤i≤r）的s一致r部超图。

论文目录

• ABSTRACT
• 中文摘要
• Résumé
• Chapter 1 INTRODUCTION
• 1.1 Preliminaries
• 1.2 Random graph models
• 1.3 The degree sequence of random graphs and hypergraphs
• 1.4 H-factor in edge-colored graph and hypergraph
• Chapter 2 The degree sequence of random hypergraphs
• 2.1 Introduction
• 2.2 The degree distribution
• 2.3 The maximum and minimum degree of random r-uniform r-partite hypergraphs
• 2.4 The sharp of the degree sequence
• Chapter 3 The degree sequence of random multigraphs
• 3.1 Introduction
• 3.2 Main results
• Chapter 4 The degree sequence of random bipartite multigraphs
• 4.1 Introduction
• 4.2 The degree distributions
• kq}）'>4.3 Extremal degrees in（?）（n,m;{p^kq}）
• -λλ^k)/k!})'>4.4 Extremal degree in（?）(n,m;{(e^-λλ^k)/k!})
• 4.5 Extremal degrees in（?）（n,m;{b（k;l,p）}）
• Chapter 5 Multicolored Hamilton cycles of the 3-uniform hypergraphs
• 5.1 Introduction
• 5.2 The proof of main results
• Chapter 6 Rainbow H-factors in uniform hypergraphs
• 6.1 Introduction
• 6.2 The proof of the main result
• Chapter 7 Conclusion and open problems
• A LIST OF NOTATIONS
• BIBLIOGRAPHY
• PUBLISHED AND SUBMITTED PAPERS
• ACKNOWLEDGEMENTS