超图中的一些极值问题

极值图论主要研究图的一些不变量如边数,色数,连通度,图谱之间的关系,以及给出这些图的不变量的极值使图具有某些特定性质。1941年Turan提出了著名的Turan 问题：给定一个图（超图）F，有n个顶点不含F 为子图的图(超图)最多能有多少条边？这个最大值称为F的Turan 数。对图来说，Erdos－Stone 给出了一个里程碑结果：一个图的Turan 数近似地取决于其色数。但对超图我们却知之甚少，事实上给出超图的Turan 数是组合极值问题中最富有挑战性的问题之一。超图的Lagrangian 和超图的一致性是极值问题中的重要工具。本项目将重点讨论超图中的一些极值问题，如超图Turan密度的结构，对超图Lagrangian的估算及其应用及一致性在极值问题中的应用，继续我们提出的对Ryser关于超图的顶点覆盖数及匹配数关系猜想的研究思路的探讨。希望在对这些问题的探讨中，能形成一些新方法和思想。

Extremal graph theory studies extremal (maximal or minimal) graphs which satisfy a certain property. Given a graph property P, an invariant u, and a set of graphs H, we wish to find the minimum value of m such that every graph in H which has u larger than m possess property P. In 1941 Turan proved that the extremal graph (with maximum number of edges) without containing a clique of order t is a balanced complete (t-1)-partite graph. In general, what is the largest possible number of edges ex(n, F) that an r-uniform graph on n vertices can have without containing F as a subgraph? This number is called the Turan number of F.This question inspired the development of Extremal Graph Theory,which is now a substantial field of research. For general graphs F we still do not know how to compute the Turan number exactly, but if we are satisfied with an approximate answer the theory becomes quite simple:A fundamental theorem of Erdos-Simonovits-Stone says that the Turan number of a graph is asymptotically determined by its chromatic number. It is more complicated for hypergraphs, we know very few about Turan numbers of hypergraphs. In fact, determining the Turan number of a hypergraph is one of the most chanllenging problems in extremal hyprgraph theory. One important tool in extremal graph (hypergraph) theory is Lagrangian of a graph (hypergraph ).1965 Motzkin and Straus established a remarkable connection between the maximum clique and the Lagrangian of a graph (a quadratic optimization problem).This connection and its extensions were sucessfully employed in optimization to provide heuristics for the maximum clique number in graphs.It also provides a bridge to the graph spectral theory. Estimating the Lagrangians of hypergraphs have been successfully applied in the course of estimating the Turan densities of several hypergraphs. In this project, we will explore whether Motzkin-Straus type results hold for hypergraphs. If it is successful, it will provide theoretical guidance for a type of optimization problems. We will also explore applications of Lagrangians of hypergraphs in estimating Turan density and Non-jumping numbers. Another important tool in extremal graph theory is Szemeredi's regularity Lemma. Fields Medalist W.T.Gowers describes this lemma as `an ideal tool for many problems'. Gowers and Rodl(etc) independently devoloped hypergraph regularity. In this project we will also explore applications of graph (hypergraph) regularity in extremal problems in combinatorics.We will also explore the relationship between the vertex-covering number and the matching number of a hypergraph. We hope that we will understand these challenging questions better and we also hope that new methods/idea can be developed through the discussion of these questions.