超图中的一些极值问题

项目名称： 超图中的一些极值问题

项目编号： No.11271116

项目类型： 面上项目

立项/批准年度： 2013

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

项目作者： 彭岳建

作者单位： 湖南大学

项目金额： 60万元

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

中文关键词： 极值组合问题；Turan 问题；超图；超图拉格朗日；

英文摘要： 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 Lagra

英文关键词： Extremal combinatorics；Turan Problem；Hypergraph；Hypergraph Lagrangian；