超图中的一些极值问题

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.

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

Turán类问题是极值组合中的核心问题，对图的情形，Erdős-Stone-Simonovtis结果给出了所有非二部图Turán数的渐近值，但对超图的Turán数仅有几个已知结果。我们得到了几类超图的Turán数，并解决了Heftz-Keevash关于与4一致相交超图相关的Turán数猜想。拉格朗日函数是研究Turán类问题的重要工具，在应用拉格朗日函数时，有两个关键问题：刻画ˋDenseˊ超图及对超图的拉格朗日的估算。我们刻画了ˋDenseˊ3一致超图其拉格朗日函数的最优向量需满足的充要条件；在某些子结构给定的条件下，给出了ˋDenseˊ3一致超图的刻画。在对超图的最大团数与拉格朗日关系的探讨中， 我们对3一致超图证明了当边数与顶点数在一定范围内时， 其拉格朗日等于其最大团的拉格朗日，并且我们结果中的界是最好的，我们局部地验证了Frankl-Furedi在八十年代提出的关于一致超图Lagrangian函数的猜想, 并改进了Talbot的结果。对几类非一致超图，我们引进了一个由超图的边集决定的多项式函数，从而得到了Motzkin –Straus型的结果并应用其给出了这几个类型的完全非一致超图Turán密度上界的估计。