超图的Turán密度与超图的拉格朗日

Turán type problems are central to the development of extremal combinatorics. Lagrangian method is an important tool in this type of questions. In 1980’s, Sidorenko showed that the Turán density of an uniform hypergraph F equals the supremum of the Lagrangians of all dense F-homomorphism free uniform hypergraphs. To apply Sidorenko’s results, we need to understand two key questions. One is to understand dense uniform hypergrahs, or specifically, describe all dense F-homomorphism free uniform hypergraphs, another is to estimate their Lagrangians. In this project, we will explore these two questions and apply the results to give hypergraph Turán densities, then obtain the exact value of Turán numbers of some hypergraphs via the discussion on stability. In general, we will explore how to construct a good continuous function determined by a hypergraph, then build the connection of the optimum value of this continuous function and the maximum cliques of a hypergraph, and apply the connection in estimating Turán density of a hypergraph. Research on this type of questions is not only important from theoretical point of view, it has also important applications in computer science such as computational complexity and imaging processing.

Turán型问题是极值组合中的核心问题与经典难题,在对Turán型问题的研究中一个重要的方法是超图的拉格朗日方法。Sidorenko证明了一致超图F的Turán密度等于所有Dense的不能将F同态嵌入的一致超图拉格朗日的上确界。将Sidorenko的结果应用到Turán密度中时，有两个关键问题，一是对Dense超图的刻画，或者更特殊地，对不能将F同态嵌入Dense的一致超图性质的刻画，二是对相关超图的拉格朗日的估算。本项目将对这两个问题进行研究，进而应用到对超图的Turán密度的估计中，并利用超图的正则性和Removal引理讨论稳定性从而得到某些超图Turán数的精确值。受拉格朗日方法的启发，本项目将更一般地研究如何构造由超图决定的连续函数，建立其最优值与超图最大团的关系从而估算超图的Turán密度。对这些问题的研究在计算机科学如复杂性分析，图像处理，数据处理等中也有应用。

本项目主要研究了拉姆齐数问题和超图的拉格朗日密度及拉格朗日方法在超图的图兰密度中的应用，取得如下进展和成果：.1.回答了Baber和Talbot提出的是否存在超图其图兰密度是无理数的问题，我们构造了一个3 一致超图并证明其拉格朗日密度是无理数，从而得到第一个图兰密度是无理数的超图。.2.提出了λ-完美的概念及与之相关的问题和猜想，并局部证明了λ-完美一致超图的不交并也是λ-完美的。提出的两个相关猜想被审稿人评价为`two appealing conjectures`, `opens an interesting research area’..3.确定了3一致超图中任意匹配的拉格朗日密度，验证了Hefetz-Keevash提出的r一致超图中长度为2的匹配的密度的猜想对r=4及5成立。得到了长度为3，4 的线性路的拉格朗日密度， 并确定了其与任意长匹配的不交并的拉格朗日密度。确定了除K43-外的有三条边的3一致超图的拉格朗日密度，首次确定了一致超图的圈的拉格朗日密度；通过分析稳定性得到由这些一致超图扩张得到的一致超图的图兰数精确值及其极值结构。.4.给出了非一致超图的Motzkin-Straus型结果，并将其应用到非一致完全超图图兰密度上界的估算中。.5.完整给出了连通匹配的3染色二部拉姆齐数的精确值，并应用正则引理得到了圈的3染色二部拉姆齐数的渐近值，从而解决了Sudakov等提出的一个问题。.6.提高了已有的圈的多染色二部拉姆齐数的上界，并给出了某些情形下圈的多染色二部拉姆齐数的渐近值。.7. Chvatal的一个有名定理是树具有Km-goodness，最近Sudarsana等证明了路径具有2Km-goodness,并提出了任何树都具有2Km-goodness的猜想，我们验证了这一猜想的正确性，并给出了树及单圈二部图对匹配的拉姆齐数。.8. Ramsey-Turan 数是拉姆齐数问题和图兰问题的结合，而星对C4的拉姆齐数一直没有完全解决，我们确定了星对C4的Ramsey-Turan 数。.9. 给出了最大度不超过n-3顶点数为n的树能嵌入到最小度不少于n-3的图中的完整刻画，从而解决了Guo-Volkman提出的猜想，并应用这一结果提高了星图与树的拉姆齐数上界，并给出了某些情形下星图与树的拉姆齐数精确值。