圈的二部Ramsey数与超图的Turán密度

论文摘要

Ramsey 理论和Turán问题是极值组合里的两大核心内容.设整数r,k≥ 2和H1,...,Hk为给定的r 一致超图.Ramsey数Rr（H1,H2,...,Hk）是最小的正整数N使得完全r 一致超图KN（r）,的任意k边着色含有某个单色的Hi,其中1≤i ≤k.若H1,H2,...,Hk为完全r 一致超图时,则R（H1,H2,...,Hk）是经典的Ramsey数.目前,已知的经典的Ramsey数及其上、下界仍然极少.求各种Ramsey数的精确值及其上、下界成为当今Ramsey理论的研究难点和热点.给定一个r 一致超图F,F的Turán数ex（n,F）定义为n个顶点上不含F作为子图的r 一致超图最多能有的边数.定义F的Turán密度为π（F）=limex（n,F）/（rn）.如何确定超图的Turán数和Turán密度是非常具有挑战性的问题.特别对r>3的一致超图,已知的相关结果很少.正则引理是Ramsey理论研究中的一个重要工具.1973年,Bondy-Erdos猜想当 k≥ 2 和奇数 n ≥ 3时,R（k;Cn）=2k-1（n-1）+1.Jenssen-Skokan 证明了当n足够大时Bondy-Erdos的猜想是对的.Benevides-Skokan证明存在正整数n1使得对正偶数n ≥ n1,R（3;Cn）=2n.Ferguson证明了二偶一奇长圈的Ramsey数的精确值.Figaj-Luczak给出三着色长圈的Ramsey数的渐近值.以上学者都运用了正则引理的工具.设B1,B2,...,Br,B为二部图和r ≥ 2.二部Ramsey数br（B1,B2,...,Rr）是最小的正整数N得完全二部图KN的任意r边着色含有某个单色的B,其中1≤i ≤ r.1975年,Faudree-Schelp首次研究了路的二部Ramsey数.之后,有关二部Ramsey数的研究引起科研工作者的兴趣.一个很自然的想法是把圈的Ramsey数推广到二部Ramsey数的情形.Luo-Peng确定了三着色圈的二部Ramsey数的近似值.Joubert、Hattingh-Joubert分别给出一个多着色短圈的二部Ramsey数的一个较弱的上界.本文我们运用正则引理给出一个多着色长圈C2n二部Ramsey数的一个上界和在满足某种条件下多着色长圈的二部Ramsey数的渐近值.Schelp提出一个Ramsey-Turán型问题:给定图H,找最小正常数0<c<1使得图G满足 δ（G）≥c|V（G）|和|V（G）|≥R（r;H）,那么G的任意r边着色含有单色的H.本文我们运用度形式的二部正则引理得到一个较弱的二部Ramsey-Turán型结果.超图的拉格朗日是超图Turán问题研究中的一个重要工具.跳跃数与Turán密度之间有着密切的联系.对于一个数α ∈（0,1）,如果存在∈>0满足Γ,∩（α,α+∈）=（?）的条件,其中Γr为r图所有可能的Turán密度的集合,那么我们将α称为r图的跳跃数.Erdos给出了跳跃数猜想:任意α∈（0,1）都是r图的跳跃数,其中r ≥ 2.猜想对一般图（2图）的情形是成立的.对于r ≥ 3的情形,Frankl-Rodl运用拉格朗日的工具给出了一列非跳跃数从而否定了 Erdos的猜想.给定r ≥3,判断任意α ∈（0,1）是否是r图的跳跃数是一个具有挑战性的问题.借鉴Frankl-Rodl的方法,已有不少科研工作者获得不少结果.我们运用拉格朗日的工具构造了一组无穷非跳跃数或者通过已知的非跳跃数构造出新的非跳跃数.目前,有不少学者获得一些特殊超图的扩张的Turán数及对应的极图的相关结果.我们运用拉格朗日的工具得到3图的匹配的（r-3）-fold enlargement的扩张的Turán密度.

论文目录

• 摘要
• Abstract
• 第1章 绪论
•   1.1 基本概念
•   1.2 研究背景及现状
•     1.2.1 Ramsey数
•     1.2.2 超图Turán密度
•   1.3 本文的主要结果
•   1.4 本文的结构安排
• 第2章 圈的二部Ramsey数
•   2.1 准备工作
• 2n的二部Ramsey数的上界'>  2.2 多着色圈C_2n的二部Ramsey数的上界
•     2.2.1 给定边数的二部图的长圈
•     2.2.2 定理2.1的证明
•   2.3 多着色圈的二部Ramsey数的渐近值
•     2.3.1 多着色的几乎的完全二部图的单色连通匹配
•     2.3.2 定理2.2的证明
• 第3章 二部图的Ramsey-Turán型结果
•   3.1 准备工作
•   3.2 2边着色的二部Ramsey-Turán型结果
•     3.2.1 给定最小度的2边着色的最大单色连通匹配
•     3.2.2 定理3.1的证明
• 第4章 超图的跳跃数及扩张的Turán密度
•   4.1 准备工作
•   4.2 超图的跳跃数
•     4.2.1 定理4.8的证明
•     4.2.2 定理4.4的证明
•   4.3 超图的扩张的Turán密度
• 结论
• 参考文献
• 致谢
• 附录 （攻读学位期间所发表和投稿论文目录）

文章来源

类型: 博士论文

作者: 刘少强

导师: 彭岳建

关键词: 二部数,密度,拉格朗日函数,正则引理,跳跃数,超图的扩张

来源: 湖南大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 湖南大学

分类号: O157.5

DOI: 10.27135/d.cnki.ghudu.2019.003939

总页数: 85

文件大小: 2939K

下载量: 17