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

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, that satisfies certain requirements.The study of problems in extremal combinatorics is the need of the development of mathematical theory and the applications in practices. For example, the Strong Perfect Graph Conjecture which is now proved by Chudnovsky et al. is a famous problem raised in information theory when researchers consider the capacity of a tunnel. In this project, we plan to consider the existence of all trees,complete graphs,cycles and the best possible bounds for the independence number of a graph under the conditions that the size of a graph is given or the graph contains no some given subgraphs. The research will not only concern genaral classes of graphs, but also the special classes of graphs such as planar graphs and so on. The main goal of this project is to consider Erd?s-Sós conjecture on the relation between the size of a graph and the existence of all trees in the graph, and several related problems concerning the existence of trees,complete graphs,cycles,independent set and so on in extremal combinatorics. Erd?s-Sós conjecture is one of the hottest problems in extremal combinatorics in recent years and it has some natural relations with the other problems which we choose to investigate in this project.

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

证明了Erdős-Sós 猜想在图的独立数为2或其补图是平面图时是正确的；运用结构分析方法，确定了一系列涉及完全图、圈、轮等图类平面Ramsey数的准确值；运用结构分析、有限域以及随机方法确定了一系列涉及圈、星、轮等图类的Ramsey数准确值；利用最大度建立了稀疏图邻点可区分色指标的若干上界；证明了Arkin和Hassin有关顶点划分猜想在一定条件下是正确的；完全证明了Aouchiche 和Hansen提出的有关图的平均距离和半径之间关系的猜想；刻画了若干给定秩7的图类以及Z2s+1-连通图；证明了距离频谱分配问题是NP-困难的，设计了一个高效的两阶段优化算法。