图Ramsey数及编码理论中相关的极值问题

结题报告

项目介绍

AI项目解读

基本信息

批准号：
11071115
项目类别：
面上项目
资助金额：
32.0万
负责人：
陈耀俊
依托单位：
南京大学
学科分类：
A0409.图论及其应用
结题年份：
2013
批准年份：
2010
项目状态：
已结题
起止时间：
2011-01-01 至2013-12-31

项目参与者：
周国飞；张运清；田丰；余爱梅；张闫博；孙舒莹；
关键词：
Shannon容量编码图Ramsey数图参数算法

项目摘要

图Ramsey 理论研究系统规模的一种临界状态，即一个大的系统究竟要大到什么程度才会包含某个给定的子系统。编码理论是信息和理论计算机科学研究的核心内容之一，主要研究如何编码才能使一个信道信息传输量达到或接近其理论上的极大值，即Shannon容量。基于图的编码方法称之为现代编码理论。与基于有限域的经典编码理论相比，该方法更容易逼近某些信道的Shannon容量。本项目主要利用图论的方法研究一个信道的Shannon容量、当G 和H 是一些特殊图类时图Ramsey数R(G,H) 的值及其上下界，R(G,H) 与Shannon容量之间的关系，图的其他参数如独立数、色数、谱半径等与Shannon容量之间的关系，以及与之相关的一些组合结构与算法。这些研究可以推动图Ramsey理论的发展，为基于图的编码优化设计提供理论基础。

结项摘要

在本项目中，首次利用图的边数与围长之间的关系, 图的边数与泛圈性之间的关系以及一个图与其补图围长之间的关系，完全证明了Surahmat 等人关于大圈对偶阶数轮的猜想，基本上解决了Surahmat 等人关于大圈对奇阶数轮的猜想，为这一类问题的研究提供了全新的思路。基于此种方法，本项目还确定了其他几类圈-轮型Ramsey数的值。证明了轮-四圈Ramsey函数与另一个备受关注的困难问题星-四圈Ramsey函数是相等的。在平面图方面，确定了不含四圈平面图最大可能边数并考虑了相应的极值结构，计算了几乎所有的圈-轮平面Ramsey数以及完全图-树平面Ramsey数，后者是与通常Ramsey数经典结果Chvátal定理相应的平面Ramsey数形式；证实了Sun等人有关四圈-完全图猜想的一个特例；证明了当图的补图是平面图时，Erdös-Sós有关图的边数与各阶树存在性之间关系的著名猜想是成立的。研究了按照谱半径对树的排序问题，确定了第8-10棵具有最小谱半径的树。给出了赋权图的谱半径和拉普拉斯谱半径的若干下界，并刻画了达到下界的图的结构。借助图的邻接矩阵谱半径，分别给出了一个二部图具有Hamilton圈和一般图具有Hamilton路的新的充分条件。利用图的结构性质，结合代数方法，分别给出了一个图是k-边连通的拉普拉斯谱条件和无符号拉普拉斯谱条件，也分别得到了与图的围长有关的拉普拉斯谱条件，推广了一些已知结论。另外，本项目还研究Burnt Pancake图的条件边容错哈密尔顿性，证明了该图类是(2n-5)-条件边容错哈密尔顿图。