论文部分内容阅读
确定图的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)的渐近值.