随机图方法在多重图Ramsey数估值中的应用

摘要：

多重图Ramsey数是经典Ramsey数的一种自然的推广，它是通过把完全图的边染色推广到完全多重图的边染色实现的。计算Ramsey数的精确值是NP难题，求多重图Ramsey数的精确值则更加困难，然而随机图方法往往是研究Ramsey数的有效途径。本文介绍了随机图方法在多重图Ramsey数领域中的应用，并用该方法给出了多重图Ramsey数的参数下界及其渐进下界；最后本文用归纳法给出了多重图Ramsey数的上界。

关键词： Ramsey数估值 多重图 随机图 参数下界

作者: 赵文飞 谢政 许晓东 陈挚

作者单位: 国防科学技术大学理学院,湖南长沙410073 广西科学院,广西南宁530007

会议类型: 国内会议

会议名称: 第29届中国控制会议

会议地点: 北京

会议语种:中文

页码: 1059-1062

在线出版日期: 2010-07-29（万方平台首次上网日期，不代表论文的发表时间）