确定Ramsey数下界值的随机算法

文[1—2]借助于计算机得到了几个Ramsey数的下界值,但由于计算机确定Ramsey数的下界值往往需要判断多达指数级的各种情况,因此所需的计算时间常使人难以接受.本文提出了一种确定Ramsey数r(k,l)下界值的随机算法,该算法试图随机而有针对性地构造一个有n个顶点的简单图G,使G中既无k个顶点的团又无l个顶点的独立集,从而确定n+1是r     

Ramsey数的几个新下界公式

本文通过构造循环图,得到并证明了公式:r(3,q)≥5(q-3)+2,r(3,q)≥7(q-5)+2,(q为奇数),又由所给引理:若r(l_1,k_1)>t_1,r(l_2,k_2)>t_2,则r(l_1-1·l_2-1+1,k_1-1·k_2-1+1)>t_1t_2,归纳出又一公式:r(3~n+1,3~n+1)≥17~n+1     

关于《关于Ramsey数下界的部分结果》的注

本文用反例 ,说明了 [1 ]中 R( l,s+ t-2 ) R( l,s) + R( l,t) -1是错的     

7个经典Ramsey数R(k,l)的新下界

利用构造性的方法,得到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.     

9个经典Ramsey数R(3,t)的新下界

本文研究了经典Ramsey数R(3,t)的下界问题.利用素数阶循环图的性质改进一般阶循环图团数的计算方法,获得了9个经典Ramsey数R(3,t)的新下界:R(3,29)≥183,R(3,30)≥189,R(3,32)≥213,R(3,33)≥218,R(3,34)≥226,R(3,35)≥231,R(3,36)≥239,R(3,37)≥244,R(3,38)≥256,其中前三个结果分别改进了迄今已知的最好的下界,后6个结果是本文首次报道的.     

用拼图法研究Ramsey数下界的一些注记

指出论文《关于Ramsey数下界的部分结果》中的一些错误,评注用拼图法研究Ramsey数下界的一些困难问题,并提出两个猜想.     

三阶Ramsey数的性质和下界

本文得出了三个关于三阶Ｒａｍｓｅｙ数性质的结论，由这三个结论直接导出了若干三阶Ｒａｍｓｅｙ数的下界结果．     

求Ramsey数下界的循环巧妙图搜索算法研究

本文研究通过构造循环巧妙图而搜寻Ｒａｍｓｅｙ数下界的算法，给出了一个效率较高的算法，该算法已经编程实现，并由此得出了一个具有４６点（４，７）循环巧妙图，从而证明了ｒ（４，７）≥４７。     

含双参数的Ramsey数新上、下界公式

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

Ramsey数r（k,l）的新下界公式

本文给出并证明了Ｒａｍｓｅｙ数ｒ（ｋ，ｌ）的一个新下界公式ｒ（ｋ，ｌ）≥１．５（ｋ－１）（ｌ－１），此下界公式与文献［１，２］所给出的下界公式ｒ（ｋ，ｌ）＞（ｎ２＾ｎ／２）／（ｅ√２，ｎ＝ｍｉｎ（ｋ，ｌ）相比，当ｋ，ｌ较小时，或ｋ，ｌ相差较大明要优越。     

对于轮和完全图的 Ramsey 数的渐近上界

该文给出:对于偶数m≥4当n→ ∞时 r(W_m,K_n)≤l(1+o(1))C₁(m) (n/logn ) ^(2m-2)/(m-2)对于奇数m≥5当n→∞时r(W_m,K_n)≤(1+o(1))C₂(m) (n^2m/_m+1/^{_{log n)}(m+1)/(m-1)} .特别地,C₂(5)=12. 以及 c(ⁿ/_logn)^5/2≤r(K₄,K_n)≤ (1+o(1)) ^n3_/(logn)².此外,该文还讨论了轮和完全图的 Ramsey 数的一些推广.     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

素数阶循环图和经典Ramsey数R（4，n）的三个新下界

研究了素数阶循环圈的基本性质，提出了寻求有效参数构造正则循环圈的新方法，得到了3个经典Ramsey数的新下界：R（4，17）≥164，R（4，18）≥182，R（4，22）≥282．这前2个结果填补了关于Ramsey数综述[2]的上下界表中的2个空白，第3个结果超过了目前已知的最好下界R（4，22）≥258，