首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到10条相似文献,搜索用时 62 毫秒
1.
Ramsey函数估值和图论中的渐近方法   总被引:5,自引:0,他引:5  
本文介绍在图论极值问题Ramsey数的渐近性态研究上的一些成果,它们的背景和所使用的证明方法,主要是随机图方法和分析方法,给出了几个体现其特色,简单易懂但不失严格性的证明。我们还简介了近年来几项重要数学奖项,包括1997年Fulkerson奖,1998年Fields奖和1999年Wolf奖得主与Ramsey理论有关的工作和方法。这些方法正改变着极值图论研究的面貌,它们将给这个领域带来新的景象。本文也包含笔者的一些结果。  相似文献   

2.
该文给出:对于偶数m≥4当n→ ∞时 r(Wm,Kn)≤l(1+o(1))C1(m) (n/logn ) (2m-2)/(m-2)对于奇数m≥5当n→∞时r(Wm,Kn)≤(1+o(1))C2(m) (n2m/m+1/log n)(m+1)/(m-1) .特别地,C2(5)=12. 以及 c(n/logn)5/2≤r(K4,Kn)≤ (1+o(1)) n3/(logn)2.此外,该文还讨论了轮和完全图的 Ramsey 数的一些推广.  相似文献   

3.
 In this paper we study three-color Ramsey numbers. Let K i,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G 1, G 2 and G 3, if r(G 1, G 2)≥s(G 3), then r(G 1, G 2, G 3)≥(r(G 1, G 2)−1)(χ(G 3)−1)+s(G 3), where s(G 3) is the chromatic surplus of G 3; (ii) (k+m−2)(n−1)+1≤r(K 1,k , K 1,m , K n )≤ (k+m−1)(n−1)+1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed mk≥2, there is a constant c such that r(K k,m , K k,m , K n )≤c(n/logn), and r(C 2m , C 2m , K n )≤c(n/logn) m/(m−1) for sufficiently large n. Received: July 25, 2000 Final version received: July 30, 2002 RID="*" ID="*" Partially supported by RGC, Hong Kong; FRG, Hong Kong Baptist University; and by NSFC, the scientific foundations of education ministry of China, and the foundations of Jiangsu Province Acknowledgments. The authors are grateful to the referee for his valuable comments. AMS 2000 MSC: 05C55  相似文献   

4.
f (l,k) be the minimum n with the property that every coloring yields either with , or with all distinct. We prove that if , then as . This supports the conjecture of Lefmann, R?dl, and Thomas that . Received July 2, 1998  相似文献   

5.
本文利用Lovasz局部引理的Spencer形式和对称形式给出r-一致超图Ramsey函数的渐近下界.证明了:对于任意取定的正整数f0,使得当n→∞时,有R~((r))(m~l,n~(k-l))≥(c-o(1))(n~(r-1)/logn)~■.特别地,R~((r))_k(n)≥(1-o(1))n/e k~■(n→∞).对于任意取定的正整数s≥r+1和常数δ>0,α≥0,如果F表示阶为s的r-一致超图,■表示阶为t的r-一致超图,且■的边数满足m(■)≥(δ-o(1))t~r/(logt)α(t→∞),则存在c=c(s,δ,α)>0,使得R~((r))(F,■)≥(c-o(1))(t~(r-1)/(logt)~l+(r-l)α)~(m(F)-l/s-r).  相似文献   

6.
 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log 2 n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999  相似文献   

7.
本文得到了含双参数x,y的Ramsey数的新上、下界公式,且初步研究了它的应用,证明了R(K6-e,K6)≤116和R(K6-e,K7)≤202.  相似文献   

8.
本文证明了Ramsey数R(a,b)足初等函数.  相似文献   

9.
7个经典Ramsey数R(k,l)的新下界   总被引:11,自引:0,他引:11  
利用构造性的方法,得到7个经典Ramsey数的新下界R(3,29)≥174,R(4,23)≥272,R(5,24)≥488,R(7,12)≥312,R(8,18)≥728,R(8,20)≥860,R(9,21)≥1278.  相似文献   

10.
 Let kn be positive integers. A finite, simple, undirected graph is called k-critically n-connected, or, briefly, an (n,k)-graph, if it is noncomplete and n-connected and the removal of any set X of at most k vertices results in a graph which is not (n−|X|+1)-connected. We present some new results on the number of vertices of an (n,k)-graph, depending on new estimations of the transversal number of a uniform hypergraph with a large independent edge set. Received: April 14, 2000 Final version received: May 8, 2001  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号