Erdos-Sos猜想及几个相关的极值组合问题

项目名称： Erdos-Sos猜想及几个相关的极值组合问题

项目编号： No.11371193

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 陈耀俊

作者单位： 南京大学

项目金额： 62万元

中文摘要： 极值组合是离散数学的最重要分支之一，其主要研究满足一定条件的一组有限结构(图，数字，向量等)构成的集合中，最大或最小可能的基数。极值组合问题的研究一方面是数学理论发展的需要，另一方面是实际应用的需要。如 Chudnovsky等人证明的强完美图定理就是在信息传输过程中考虑信道容量时提出的一个著名问题。本项目拟考虑在一定边数限制以及某些禁用子图限制条件下各种树的存在性问题，完全图的存在性问题，圈的存在性问题，独立数的最大或最小可能的上下界等等极值组合问题。这些问题既涉及一般图类，也涉及平面图等不含某些特殊子图的图类。主要研究内容是Erdos-Sos 有关图的边数与各种树存在性之间关系的猜想，以及几个涉及完全图、树、圈、独立集等存在性且与Erdos-Sos 猜想相关的极值组合问题。Erdos-Sos 猜想目前是极值组合研究的热点问题之一，与本项目拟考虑的其它几个问题之间有着某种内在的联系。

中文关键词： Erd？s-Sós 猜想；Ramsey 数；平面Ramsey数；邻和可区分色指标；算法

英文摘要： Extremal combinatorics is one of the central areas in discrete mathematics, which deals with the problem of determining or estimating the maximum or minimum possible cardinality of a collection of finite objects, such as graphs,numbers,vectors and so on,

英文关键词： Erd？s-Sós conjecture；Ramsey number；planar Ramsey number；NSD index；algorithm