一致超图的Ramsey和Turán问题

来源 :湖南大学 | 被引量 : 0次 | 上传用户:hhj9290
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
确定图的Ramsey数一直以来是图论中的研究难点和热点.Burr[10]给出了连通图G与图H的Ramsey数R(G,H)的一般下界:当G的顶点数v(G)≥s(H)时,Ramsey数R(G,H)≥(v(G)-1)(χ(H)-1)+s(H),其中χ(H)是图H的色数,s(H)是H的色剩余.如果R(G,H)=(v(G)-1)(χ(H)-1)+s(H),则称图G是H-good的.Chvátal[17]在1977年证明了树是Km-good的,Chvátal和Harary[18]证明了树是2K2-good的.本文给出了树与两个完全图的不交并的Ramsey数,即R(Tn,2Km)的精确值.我们的结果表明树是2Km-good的,从而证明了Sudarsana,Adiwijaya和Musdalifah[87]在2010年提出的猜想.确定一致超图的Turán数和Turán密度是极值图论中重要而极富挑战性的问题.对于r一致超图,已知的Turán数与Turán密度结果非常少,如Turán70多年前提出的关于最小完全超图K 43的Turán数的猜想依然悬而未决.拉格朗日方法是解决Turán型问题的有效工具,拉格朗日密度与Turán密度紧密相关,1987年Sidorenko[75]证明了一致超图F的拉格朗日密度等于F的扩张的Turán密度,并通过确定无穷多个超图的拉格朗日密度首次得到无穷多个超图的Turán密度,而确定K43和K43-的拉格朗日密度将导致对Turán猜想和Frankl-Füredi猜想的解决.确定超图的拉格朗日密度自身也是一个很有意义且极具挑战性的问题,目前已知结果也很少.本文确定了长为3的3一致线性路与任意长的3一致匹配的不交并的拉格朗日密度,并结合稳定性的方法,得到了它的扩张的Turán数并证明了极图的唯一性.记Htr,s是长为t的s一致匹配的(r-s)扩充.1989年Sidorenko[77]确定了当r=3或4,且t≥2时Htr,2的拉格朗日密度,以及当r=5且t≥4,r=6且t≥6时Htr,2的拉格朗日密度.2017年Jenssen[51]给出了当r∈{3,4,5,6,7}时H2r,2的拉格朗日密度.可见Sidorenko的结论与Jenssen的结论间仍有空隙,本文填补了这些空隙并给出了Htr,2,H25,3,Htr,3的拉格朗日密度,其中t≥3,r=5或6.Ramsey型问题和Turán型问题有很强的相关性,Erd?s首先提出对Ramsey-Turán型问题的研究,之后形成了几类Ramsey-Turán型问题.本文讨论了如下Turán型Ramsey数问题:给定r个简单图F1,F2,...,Fr,设n≥R(F1,F2,...,Fr),这r个图的Turán型Ramsey数定义为T(n;F1,F2,...,Fr)=max{m:存在顶点数为n边数为m的图G及对G的边集的r染色使得对任意i∈[r],G均不含染i色的Fi}.Sós[81]给出了完全图的Turán型Ramsey数;当F1,...,Fr不全是二部图时,Erd?s-Hajnal-Simonovits-Sós-Szemerédi[28]给出了T(n;F1,...,Fr)的渐近值.一个自然的问题是当所有Fi均为二部图时确定T(n;F1,...,Fr)的值.本文给出了T(n;C4,K1,3)的精确值,并对所有t≥4证明了T(n;C4,K1,t)的渐近值.
其他文献
目的:近年来,随着中医体质学的发展,《中医体质量表》和相应的《中医体质分类与判定》标准已得到广泛的推广应用,成为“治未病”健康辨识的主要手段。婴幼儿体质虽与成人不同,但也存在由于先天禀赋和后天获得共同形成的体质差异,因此也“有类可分、有体可辨”,只是婴幼儿体质更加秉承于先天因素。目前,无论是儿童中医保健领域,还是儿科临床,都缺乏对婴幼儿进行中医健康测评的规范化、实用性的方法和工具。本研究依据王琦院
学位
急性胰腺炎(acutepancreatitis,AP)是内科常见急腹症之一,是一种由胆石、酒精、高甘油三酯等因素导致的突发性胰腺外分泌炎症性疾病,可诱发全身炎症反应,造成胰腺外远隔器官
第一部分 胰岛素通过恢复UCP3表达、降低细胞能荷改善骨骼肌脂毒性目的 高脂饮食引起的能量过剩及脂质代谢紊乱是脂毒性发生的危险因素。线粒体是机体能量合成及氧化代谢的主
目的通过临床研究,总结肺纤维化的六经分布规律,研究肺纤维化六经辨证分型与一般情况、主要症状、评分指标及血瘀兼证的相关性,探讨血瘀兼证在肺纤维化六经辨证中的意义,为肺纤维化临床辨证论治提供思路延展。通过动物实验,探究大黄(?)虫丸对博来霉素诱导的肺纤维化大鼠肺功能及生存状态的影响,并从大黄(?)虫丸对TGF-β1/Smad3信号通路的影响探讨其干预肺纤维化的作用机制。方法临床部分:本研究通过调查问卷
学位
第一部分ABO基因多态性与大动脉粥样硬化性脑梗死发病的关联性研究目的:探讨ABO基因单核苷酸多态性(Single nucleotide polymorphism,SNP)与大动脉粥样硬化性(Large artery a
Domain理论是D.S.Scott在70年代初提出来的,它给计算机函数式语言提供了指称语义.序结构和拓扑结构是在Domain理论中占据重要地位的数学结构,序和拓扑是可以互相生成的.本文
背景:慢性萎缩性胃炎(Chronic Atrophy Gastritis)包括胃黏膜的萎缩及肠上皮化生,属于胃的癌前状态,根据Correa提出的“肠型胃癌”的演变过程,CAG属于胃癌演变过程中关键步骤,防控CAG进一步进展成为早期胃癌成为目前国内外专家研究的热点。目前现代医学的治疗手段有限,尚无药物试验表明对胃癌前状态的抑制作用。田德禄教授在20世纪90年代即开展了中医药治疗CAG的动物及临床试验
学位
背景:糖尿病肾脏疾病是以糖、脂、蛋白等体内营养物质代谢紊乱及肾小球受损为主要表现的糖尿病微血管并发症之一,在中医诊断中属于“消渴病肾病”的范畴。随着我国经济的快速发展、人们饮食结构和生活习惯的变化,糖尿病及其并发症的发病率、致残率、死亡率及医疗费用的支出逐年递增,加重了人们的负担,严重影响着人们的生活质量,因而控制糖尿病及其并发症的发展对人类的健康影响深远。证候是病因病机形成的概括,是辨证论治的主
学位
1研究目的流感病毒、结核杆菌等外来病原微生物被鼻腔吸入后可以经呼吸道感染机体,导致多种疾病,严重影响人类健康。相比于皮下注射型疫苗,采用鼻腔黏膜免疫制剂不仅可以避免
喀斯特地区孕育了丰富的植物资源,而石漠化作为喀斯特地区常见的生态退化现象,其大面积的发生导致区域植被结构单一、生态系退化以及生物多样性的减少。为了保护植物多样性和维持生态系统平衡,挖掘本地原生植物在石漠化治理中的应用,以期为示范区野生经济植物开发利用、石漠化治理植物配置模式提供科学依据。笔者于2018年7~11月、2019年4~10月采用样线和样方相结合的方法在毕节撒拉溪示范区开展植物资源调查,共
学位