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

批准号:
11671124
项目类别:
面上项目
资助金额:
48.0 万元
负责人:
彭岳建
依托单位:
学科分类:
A0409.图论及其应用
结题年份:
2020
批准年份:
2016
项目状态:
已结题
项目参与者:
王岁杰、彭豪、陈平鸽、吴彪、刘少强、梅周胜、梁金花、胡思楠
国基评审专家1V1指导 中标率高出同行96.8%
结合最新热点,提供专业选题建议
深度指导申报书撰写,确保创新可行
指导项目中标800+,快速提高中标率
微信扫码咨询
中文摘要
Turán型问题是极值组合中的核心问题与经典难题,在对Turán型问题的研究中一个重要的方法是超图的拉格朗日方法。Sidorenko证明了一致超图F的Turán密度等于所有Dense的不能将F同态嵌入的一致超图拉格朗日的上确界。将Sidorenko的结果应用到Turán密度中时,有两个关键问题,一是对Dense超图的刻画,或者更特殊地,对不能将F同态嵌入Dense的一致超图性质的刻画,二是对相关超图的拉格朗日的估算。本项目将对这两个问题进行研究,进而应用到对超图的Turán密度的估计中,并利用超图的正则性和Removal引理讨论稳定性从而得到某些超图Turán数的精确值。受拉格朗日方法的启发,本项目将更一般地研究如何构造由超图决定的连续函数,建立其最优值与超图最大团的关系从而估算超图的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.
本项目主要研究了拉姆齐数问题和超图的拉格朗日密度及拉格朗日方法在超图的图兰密度中的应用,取得如下进展和成果:.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提出的猜想,并应用这一结果提高了星图与树的拉姆齐数上界,并给出了某些情形下星图与树的拉姆齐数精确值。
期刊论文列表
专著列表
科研奖励列表
会议论文列表
专利列表
The connection between polynomial optimization, maximum cliques and Turan densities
多项式优化、最大派系和图兰密度之间的联系
DOI:10.1016/j.dam.2017.03.014
发表时间:2017
期刊:Discrete Applied Mathematics
影响因子:1.1
作者:Wu Biao;Peng Yuejian
通讯作者:Peng Yuejian
lambda-perfect hypergraphs and Lagrangian densities of hypergraph cycles
lambda 完美超图和超图循环的拉格朗日密度
DOI:10.1016/j.disc.2019.03.024
发表时间:2019
期刊:Discrete Mathematics
影响因子:0.8
作者:Yan Zilong;Peng Yuejian
通讯作者:Peng Yuejian
Lagrangian densities of linear forests and Turan numbers of their extensions
线性森林的拉格朗日密度及其扩展的图兰数
DOI:10.1002/jcd.21687
发表时间:2020
期刊:Journal of Combinatorial Designs
影响因子:0.7
作者:Hu Sinan;Peng Yuejian;Wu Biao
通讯作者:Wu Biao
A Note on Non-jumping Numbers for r-Uniform Hypergraphs
关于r-均匀超图的非跳数的注解
DOI:10.1007/s00373-018-1888-6
发表时间:2018-03
期刊:Graphs and Combinatorics
影响因子:0.7
作者:Liu Shaoqiang;Peng Yuejian
通讯作者:Peng Yuejian
Connection Between Polynomial Optimization and Maximum Cliques of Non-Uniform Hypergraphs
多项式优化与非均匀超图最大团之间的联系
DOI:10.1007/s11083-017-9434-3
发表时间:2018-07
期刊:Order
影响因子:--
作者:Chen Pingge;Peng Yuejian
通讯作者:Peng Yuejian
图与超图中的Turán问题与Ramsey问题
- 批准号:2025JJ30003
- 项目类别:省市级项目
- 资助金额:0.0万元
- 批准年份:2025
- 负责人:彭岳建
- 依托单位:
超图中的一些极值问题
- 批准号:11271116
- 项目类别:面上项目
- 资助金额:60.0万元
- 批准年份:2012
- 负责人:彭岳建
- 依托单位:
国内基金
海外基金
