超图的拉格朗日与Turán数

发布时间：2021-07-04 05:22

　　超图的Turán问题是极值组合中的核心问题.给定一个r 一致超图F,F的Turán数ex（n,F）数定义为n个顶点上不含F作为子图的r 一致超图最多能有的边数.定义F的Turán密度为π（F）=limn→∞ex（n,F）/（nr）如何确定超图的Turán数和Turán密度是组合数学中非常具有挑战性的极值问题.对于普通图的情形,即2一致超图,它的结果已经比较完整了.1941年,Turán确定了所有完全图的Turán数以及相应的极值结构.对完全图以外的情形,Erdos-Stone-Simonovits证明了如下结果:如果图F的色数是t,则有ex（n,F）=1/2（1-1/t-1）n2+o（n2）.1961年,Turán提出了一个自然的问题:如何确定ex（n,Ktr）的值?其中t>r>2,Ktr是顶点数为t的完全r 一致超图.但是,到目前为止,就连最简单的4个顶点上的完全3 一致超图,它的Turán数问题仍然没有完全解决.对于一般的r 一致超图的Turán数问题,目前已知的相关结果也是很少的.拉格朗日是Turán问题研究中的一个重要工具.r 一致超图F的拉格朗日密度定义为πλ（F... 

【文章来源】：湖南大学湖南省 211工程院校 985工程院校 教育部直属院校

【文章页数】：96 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第1章 绪论
    1.1 基本概念
        1.1.1 一致超图
        1.1.2 非一致超图
    1.2 研究背景及现状
    1.3 主要研究内容
        1.3.1 稀疏超图的拉格朗日密度及其扩张的Turán数
        1.3.2 超图的Motzkin-Straus型结果及其Turán应用
    1.4 本文的结构安排
第2章 预备知识
    2.1 拉格朗日函数的基本性质
    2.2 一些特殊图的拉格朗日的估算
    2.3 KKT条件
第3章 稀疏超图的拉格朗日密度及其扩张的Turán数
    3.1 引言
    3.2 Q_(t+2)的拉格朗日密度
        3.2.1 不包含Q_(t+2)作为子图的3图的左压性质
        3.2.2 不包含Q_(t+2)但包含Q'_(t+2)作为子图的3图的拉格朗日的估算
        3.2.3 不包含Q_(t+2)但包含Q"_(t+3)作为子图的3图的拉格朗日的估算
        3.2.4 定理3.2.1的证明
    3.3 Q_(t+2)的扩张的Turán数
第4章 Motzkin-Straus型结果及其应用
    4.1 引言
    4.2 {s,r}-超图的Motzkin-Straus型结果
        4.2.1 与最大团之间的联系
        4.2.2 完全{s,r}-超图的Turán密度
    4.3 {p,s,r}-超图Motzkin-Straus型结果
        4.3.1 与最大团之间的联系
        4.3.2 完全{p,s,r}-超图的Turán密度
结论
参考文献
致谢
附录 攻读学位期间所发表和投稿论文目录


【参考文献】：
期刊论文
[1]On Graph-Lagrangians and Clique Numbers of 3-Uniform Hypergraphs[J]. Yan Ping SUN,Yue Jian PENG,Biao WU.  Acta Mathematica Sinica. 2016(08)



本文编号：3264124