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