经典Ramsey数R(4,12),R(5,11)和R(5,12)的新下界

<正>已知经典Ramsey数R(m,n)(m,n≥2)是一定存在的,但确定经典Ramsey数R(m,n)是组合数学和图论中著名的难题,至今在理论和方法上尚未见到取得突破的迹象,因此近年来各国学者主要用各种方法借助计算机对一些具体的Ramsey数给出估计。王清贤、谢继国等人沿用文献[4]的方法研究一般的循环图,得到一些Ramsey数的下界。这种方法在用字典排列法产生参数时,由于大量同构的图均要一一考察,占用大量计算机机时。因此我们作出新的尝试:利用素数阶循环图的平移和旋转等性质改进了产生参数的方法,提高了运算效率,得到3个Ramsey数的新下界。     

经典Ramsey数R(5,9)和R(5,10)的下界

由于Ramsey数的确定十分困难,人们往往利用求Ramsey数上、下界的方法来逼近其精确值。表1中列出目前已知的R(5,l)的所有下界。 对较小的Ramsey数,确定下界的方法     

经典Ramsey数R(6,12),R(6,14)和R(6,15)的新下界

确定Ｒａｍｓｅｙ数是组合数学和图论中非常著名的难题,经过好几代数学家的努力,再加上计算机的帮助,迄今为止计算出来的型如Ｒ(ｋ,ｌ)的不平凡的经典Ｒａｍｓｅｙ数总共只有9个[1].关于Ｒａｍｓｅｙ数Ｒ(6,ｌ),在Ｒ(6,3)=18[2]之后,进展极其缓慢.在文献[1]中,记录了迄今已知的最好的下界:Ｒ(6,4)≥35,Ｒ(6,5)≥58和Ｒ(6,6)≥102.当ｌ≥7时至今尚未有人探索得到较好的结果,人们仅能利用递推公式[3]Ｒ(ｋ,ｌ1)≥ｓ且Ｒ(ｋ,ｌ2)≥ｔＲ(ｋ,ｌ1 ｌ2-1)≥ｓ ｔ-1.　　根据上述已知结果和熟知的平凡的Ｒ(6,2)=6,得到一些平凡的下界:ｌ7891011Ｒ(6,…     

混合Ramsey数x_2(m,K_(1,n))的下界

一个图G的全色数x_2(G)是指着色G的边和顶点使相邻、关联元素均着不同颜色所需要的最少颜色数。对于正整数m和星形图K_(1,n),混合Ramsey数x_2(m,K_(1,n))是这样的最小正整数p,使得任一p阶图H或者     

Ramsey数r(3,14)和r(3,15)的新下界

Ramsey数r(p,q)是满足下述条件的最小正整数r:对任意的r个顶点的图G(本文中的图均指无向简单图),则G或有P个顶点的团(即完全子图k_p)或有q个顶点的独立集。Ramsey 1930年证明了Ramsey数的存在性,Ramsey理论的研究在近六十年中也取得了许多有意义的结果(参看文献[2]     

Ramsey数的下界

记R(l_1,l_2,…,l_q;r)为Ramsey数。 命题 设n为满足的最大正整数,则~~     

I(L)与R(L)的连通性

本文沿用文[1]的术语和记号,证明:(1)对一般的L,LF单位区间I(L)连通;(2)若L存在元素m,使m∨m′=1,则LF实直线R(L)连通。     

关于多电子原子及离子体系的一种新的理论模型(三)

文献[1]中提到的待定参数有σ、g、d和△Z,由文献[1]可知 d=n′—n,(1)确定d的问题,可归结为确定n′的问题。因此,等待确定的参数有n′、σ、g和△Z。 一、确定参数的方法 1.n′值 具有相同电子构型的原子和正离子,按照核电荷数Z由小到大顺序排列,构成一个等电子系(或称组)。根据     

N阶完全图K_N的t边着色

如果N阶完全图K_N的边用t种颜色着色,则K_N称为是t边着色的。图F_i,l≤i≤t的Ramsey数n(F_1,…,F_i)是这样的最小正整数,使得对于任意一个i边着色完全图K_n,都可以在其中找到某个子图F_i,它是用第i种颜色着色的。当F_1=     

粘贴DNA计算机模型(Ⅱ): 应用

经典的粘贴DNA计算模型采用单、双链混合型DNA分子编码, 其生物操作具有无需DNA链的延伸、无需生物酶以及DNA链可重复使用等优点, 已经受到不同学科学者的关注. 在经典模型的基础上, 进行一定的扩展与完善, 必对DNA计算机的研究有良好的贡献. 基于此, 对粘贴DNA计算机模型进行了较为深入的研究: (1) 提出了基于粘贴模型的矩阵表达模型; (2) 对经典粘贴模型应用于图与组合优化等方面的研究成果给予综述, 诸如集合覆盖问题、图的顶点覆盖问题、图的Hamilton路与圈问题、图的团与独立集问题、图的生成树与Steiner树问题等; (3) 给出了基于粘贴模型的图的同构问题的算法.     

系统(φ,α,σ)的局部行为

文献[1]揭示了一个有趣的现象:两个含1的交换环A和R,它们并不同构(因而也不是Morita等价的),但具有同构的3维线性群。这在1987年5月举行的中美典型群及相关领域学术讨论会上引起了与会者的兴趣,因为过去人们猜测,若m和n是不小于3的整数且GL_m(A)≌GL_n(R),似应有m=n且A和R是Morita等价的。     

中值滤波中的循环序列(Ⅱ)

1背景与说明本文中k始终表示一个固定正整数,k≥2设x={x(n)}_(n=0±1,…)是一个实数列,对每一n,用x~(1)(n)表示{x(m)}_(n-k≤m≤n+k),这2k+1个数由小到大重排后位于中间的那一项.通过这样的重排运算,x={x(n)}变成一个新的实数列x_(1)={x~(1)(n)},它称为x的中值滤波.对x~(1)又可进行中值滤波,其结果记为x~(2)={x~(2)(n)}.一般地x~(p)={x~(p)(n)}表示x通过p次中值滤波后的实数列,其中x~(0)=x.若x(1)=x,则x称为中值滤波的根,关于根已有系统且完备的研究.若x~(1)≠x,但有s≥2使x~(s)=x,则x称为s次循环序列.关于循环序列已经有下面的命题若x={x(n)}是循环序列,则(i)x中任何长为k+1的段落都是二值的;(ii)x本身是二值的.本文证明:任何循环序列都是二次循环的     

(10,3,4)强正则图

记Γ(a)为点a的邻点集,|M|为集M中元素的数目。 定义 图G称为(l,m,n)强正则图,如果它是l正则的,且(?)a,b∈G,a adj b,有|Γ(a)∩Γ(b)|=M,(?)a,b∈G,a≠b,a,b不相邻,有|Γ(a)∩Γ(b)|=n。 1973年榎本提出:(10,3,4)强正则图是否存在? 1981年李乔、杜锡录等同志又提出此问题,因为它对图的对称性研究是相当有意义的。但该图的存在性一直不清楚。本文具体构造出此图,因而存在性问题自然解决了。     

S_p(4,p~n)的第一Cartan不变量

在模表示理论中,Cartan不变量的矩阵是一个重要的研究课题,它的元素的性质尚未完全搞清。我们主要讨论B_2型Chevalley群S_p(4,P~n)的Cartan矩阵中的一个元素——C_(11)——第一Cartan不变量,它等于平凡模M(n,θ)在它的射影包R(n,θ)的合成列中的重数,即C_(11)~(n)=[R(n,θ):M(n,θ)]。当P充分大时,它是一个与p无关,只依赖于自然数n的值。Cheng和笔者分别计算了p=2和p≥7时,A_2型Chevalley群SL(3,P~n)及其扭群SU(3,P~n)的第一Cartan不变量;Chastkofsky用另外的方法得到了与     

3连通图中圈上的可去边

３连通图Ｇ中的边ｅ称为可去的,若Ｇ－ｅ是一个３连通图的剖分,讨论了３连通图中圈上可去边的分布,得到这些可去边数依赖于图中极大半轮数的下界,这些下界在某种意义上是不能改进的。     

复杂度理论中某些不可证明的真命题

在复杂度理论研究中,上界不断被改进,但下界的研究却迟迟没有重要进展。对于任何一个NP完全性问题,现有最好的算法也需要指数的时间,但数学家们费尽九牛二虎之力也只能证出一个线性时间的下界。这使我们想到:复杂度理论中的许多真命题是不可证明的。但如果只是并行于Gdel的不完全性定理,得出一些诸如:“下界是2。但不可证”的结论,仍不能说明真实下界与理论下界之间的巨大差距。我们得到了下面的结果:定理1设,f(n)≥n是任一时间可构造的函数(例如2~2~m),A是一个可以用谓词P(c)表示“程序c的时间复杂度t(n)不会低于一个常数”的公     

gr(■_n)与gr(ε_p)不具有pure维数

一个交换Noetherian环R称为是有pure维数n的正则Noetherian环,是指对R的任意极大理想 ,R_m的整体维数gl.dim R_m=n,这里R_m为R在极大理想■处的局部化。众所周知,若R是某域上的有限生成交换代数,且是整环,同时g1.dim R<∞,则R有pure维数;如果,     

关于简单的MCD图边数的下界

简单的MCD图是指有n个顶点、任何两个圈的长度均不相等且有最大可能边数的简单图,文献[1]中对简单的MCD图的边数f(n)的下界得出     

简单的MCD图边数下界的改进

简单的MCD图是指有力个顶点,任何两个圈长均不相等且有最大可能边数的简单图.作者曾得出~[1]:关于简单的MCD图边数f~*(n)的下界,当n> 17时,有记号LxJ表示取不超过x的最大整数.最近,作者改进了这一结果,得出了对不小于17的整数n,可按下述步骤求f~* (n)的下界     

Grassmann流形■_(2,n)和G_(2,n)的非浸入定理

一、引言 我们知道,对实投影空间(特殊的Grassmannian)到欧氏空间的浸入问题,已经发展了许多种方法。自然,对Grassmann流形的同一问题,应当是非常有趣的。 没(?)_(m,n)(G_(m,n)为向量空间R~(m+n)中全体定向(未定向)的m维向量子空间组成的定向(未