用图的分割原理计算一些Ramsey数

裴超平

(同济大学 数学系， 上海 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)-部图覆盖.这里的路径和完全多部图可以是空集.

用定理1可以求解出关于路径的Ramsey数R(Pn,G).

定理2对于给定的图G，当n≥|G|2+2χ(G)·α(G)时，R(Pn,G)=(χ(G)-1)(n-1)+σ(G).

2定理证明

为了证明定理2，回顾一下Burr的定理.

定理3[1]设G是一个具有p个顶点的图.令H为含n个顶点的连通图，并且含一条长度为m的悬挂路径.设G1是G中删除含u个顶点的独立集所得到的图，H1是H的悬挂路径缩减1后的得到的图.如果m≥(p-2)(p-u)+u+1，则:

考虑H=Pn，即n≥|G|2时，有R(Pn,G)≤max(R(Pn-1,G),R(Pn,G1)+n-1).

设k=χ(G).由于k=1的情况是平凡的，假设k≥2.

设n0=|G|2+2(k-1)α(G).归纳假设当n≥n0时，R(Pn,G1)=(k-2)(n-1)+σ(G).证明当n≥|G|2+2kα(G)时，R(Pn,G)=(k-1)(n-1)+σ(G).由定理3得：

重复应用定理3，可以得R(Pn-1,G)≤max(R(Pn-2,G),(k-1)(n-1)+σ(G)).于是，

R(Pn,G)≤max(R(Pn-2,G),(k-1)(n-1)+σ(G))≤…≤max(R(Pn0,G),(k-1)(n-1)+σ(G))

设h=(χ(G)-1)(n0-1)+kα(G).由定理1，对完全图Kh的任意红蓝二着色，其顶点集可以被k-1条不相交的红色路径和1个不相交的蓝色等部集的完全k部图覆盖.如果这k-1条路径中不存在红色Pn0，则显然会存在蓝色的Kk(α(G))，从而含有一个蓝色的图G.所以，得到R(Pn0,G)≤(k-1)(n0-1)+kα(G).

由条件n≥|G|2+2kα(G)=n0+2α(G)以及k≥2，可得:

(k-1)(n-1)+σ(G)≥(k-1)(n0-1)+(2k-2)·α(G)≥(k-1)(n0-1)+kα(G)；

所以

R(Pn,G)≤max(R(Pn0,G),(k-1)(n-1)+

σ(G))≤(k-1)(n-1)+σ(G)，

得证.

3展望

相信，如果能够缩小定理3中关于悬挂路径的条件，就能够求出使得Pn是G-good的更严格的条件.而如果能给出R(Cn0,G)的约束条件的话，可以将这个结论推广到圈上.

参考文献:

[1]Burr S A. Ramsey numbers involving graphs with long suspended paths [J]. Journal of the London Mathematical Society, 1981, 24(2): 405.

[2]Allen P, Brightwell G, Skokan J. Ramsey-goodness and otherwise [J].Combinatorica, 2013, 33(2): 125.

[3]Pokrovskiy A. Partitioning edge-colored complete graphs into monochromatic cycles and paths [J]. Journal of Combinatorical Theory Series B, 2014, 106: 70.

[4]Pokrovskiy A. Partitioning edge-coloured complete graphs into monochromatic cycles[J]. Electronic Notes in Discrete Mathematics,2013,43:311.

Using Partitioning Graphs to Calculate Some Ramsey Numbers

PEI Chaoping

(Department of Mathematics, Tongji University, Shanghai 200092， China)

Abstract：Ramsey number is the smallest integer N such that for any red-blue edge-coloring of KN, there is a red subgraph G or a blue subgraph H. In this paper, we use a theorem of Burr and the method of partitioning graphs to prove that if n≥|G|2+2χ(G)α(G), then R(Pn,G)=(χ(G)-1)(n-1)+σ(G).

Key words：Ramsey numbers； Ramsey goodness； path

文献标志码：A

中图分类号：O157.5

收稿日期：2015-04-23

第一作者： 裴超平(1989—)，男，博士生，主要研究方向为组合数学和图论，E-mail:peichaoping@msn.cn