用图的分割原理计算一些Ramsey数
2016-04-26裴超平
裴超平
(同济大学 数学系, 上海 200092)
用图的分割原理计算一些Ramsey数
裴超平
(同济大学 数学系, 上海 200092)
摘要:Ramsey数R(G,H)为最小的正整数N,使得对完全图KN的边集的任意红蓝二着色,都存在红色的子图G或者蓝色的子图H.结合Burr的一个定理和图的分割原理,证明当n≥|G|2+2χ(G)α(G)时,R(Pn,G)=(χ(G)-1)(n-1)+σ(G).
关键词:Ramsey数; Ramsey 完备性; 路径
1研究内容
本文所讨论的图都是简单图.对于给定的图G和H,Ramsey数R(G,H)为最小的正整数N,使得对完全图KN的边集的任意红蓝二着色,都存在红色的子图G或者蓝色的子图H.设Δ(G)为图G的最大度,χ(G)为图G色数,α(G)为G的最大独立集所含顶点数,σ(G)为G的着色剩余,即对G的顶点集的任意χ(G)-真着色中最小的颜色集所包含的顶点数.Burr[1]得到如下的下界.
引理1给定图G和连通图H,|H|≥σ(G),则:

称H是G-good,如果引理1中的等式成立.Burr[1]证明了如果连通图H含有一条充分长的悬挂路径且|H|≥σ(G),则H是G-good的.由此引出一个问题:对于给定的图G,H中的悬挂路径有多长就能保证H是G-good ? 这个问题的难度非常高,因为Ramsey 数的求解一直是数学上具有挑战的问题之一.因此研究一个更具体的问题:路径Pn有多长,能保证Pn是G-good?Allen等[2]猜想只要n≥χ(G)|G|就可以.
图的分割原理是近年来图论新兴起的课题之一,它研究的是对完全图的边集进行二着色后,其顶点集可以被多少条不相交的路径或者圈覆盖.Pokrovskiy[3-4]证明了如下定理:
定理1对于任意的正整数k,以及n≥k,假设Kn的边集被红蓝两种颜色着色.则Kn的顶点集可以被k条不相交的红色路径和一个不相交的每个部集都相等的蓝色完全(k+1)-部图覆盖.这里的路……
