【作者】 张雪莲；

【导师】 阴东升；

【作者基本信息】 北京工业大学 ， 数学， 2017， 硕士

【摘要】 图论是组合数学的重要内容,本文主要研究了高维Ramsey数、r一致超图和邻点强可区别全染色问题.Paul Erdos和Noga Alon等人给出了 一般意义下的Ramsey数理论,Joel Spencer用Lovász局部引理证明Ramsey函数的渐进下界.单传辉用概率方法给出了高维情况下的Ramsey数理论及其推广的一般形式.本文通过Lovász局部引理给出了高维情况下的Ramsey数理论及其推广的另一种形式,其中包括等概率和不等概率两种不同情况下的高维Ramsey数理论.陆尚辉用Lovász局部引理的一般形式证明了Xast;图的邻点强可区别全染色的色数)上界为32A.本文通过Lovász局部引理的推论给出Xast上界为30A.Lovász和Erdos说明了如果r一致超图的每条边至多与其他2r-3条边相交,那么存在顶点的一个2-着色,使得任何边都不是单色.本文通过Lovász局部引理的一般形式给出其证明,并推广到顶点k-着色的情形.更多还原

【Abstract】 Graph theory is an important part of Combinatorics.In this paper,we study the problem of high dimensional Ramsey number,r-uniform hypergraph and Adjacent ver-tex distinguishing total coloring.Paul Erdos and Noga Alon,who gives a general sense of Ramsey Number Theory.Joel Spencer prove asymptotic lower bound of Ramsey function by Lovász local lemma.Shan Chuanhui gives a general form Ramsey Number Theory of the dimensional case and generalized.This paper presents a another form Ramsey Number Theory of the dimensional case and generalized by Lovász local lem-ma.It includes the theory of high dimensional Ramsey number under the condition of equal probability and unequal probability.Lu Shanghui prove that the upper bound of the chromatic number of the adjacent vertex strong distinguishing total coloring is 32Δby using the general form of the Lovász local lemma.In this paper,we give the upper bound on the chromatic number of adjacent vertex strong distinguishing total coloring of graph is 30Δ by using inference of Lovász local lemma.Lovász and Erdos give the conclusion that if each hypergraph edge and the other 2r-3 edges intersect at most,then there is a 2 vertex coloring,so that any edge is not monochromatic.This paper give its proof by using the general form of Lovász local lemma and extend it to the vertex k coloring.更多还原