APP下载

Ramsey数和无三角的Cayley图

2015-07-31厉明波李雨生

同济大学学报(自然科学版) 2015年11期

厉明波,李雨生

(同济大学 数学系,上海200092)

设H是一个加法群,H*=H\{0}.一个H的子集A被说成是关于逆元封闭的,是指若x∈A,则-x∈A.对一个H*逆元封闭的子集A,可定义一个图GH(A)如下:它的点集是H,而{x,y}是一条边当且仅当|x-y|∈A.图GH(A)被称为由A导出的Cayley图.

本文里,群H是Zn={0,1,…,n},即模n的整数加群.对于Zn的一个逆元封闭子集A,简记由A生成的Cayley图GZn(A)为Gn(A).因Zn中x的逆元是n-x,故{x,y}是Gn(A)的一条边当且仅当|x-y|∈A.有两个平凡的Gn(A),其一是空图,对应的生成集A=Ø,其二是圈Cn,对应的生成集A={1,n-1}.下面的性质是熟知的,参见文献[1].

引理1 设A⊆Z*n为逆封闭子集,则Gn(A)是点传递的,且点i的邻域是

A+i= {a+i:a∈A}

特别地,Gn(A)是|A|-正则的;Zn的任何子集S是一个独立集当且仅当对S中任何两个相异的元x和y都有|x-y|∉A.

设m和q为正整数,定义Ramsey数r(m,q)为最小的正整数n使得任何阶为n,不含Km的图都有q元独立集.以α(G)记图G的独立集.当Gn(A)不含三角形且α(Gn(A))≤q,则r(3,q+1)≥n+1.Ramsey理论的发展,参见文献[2].

集合A⊆Zn被说成是无和的,是指(A+A)∩A=Ø就是说,方程x+y=z在A中无解,这里x,y,z不必两两互异.显然,无和集不包含零元素.计算将依据下面的结果.

定理1 设A,A′都是Z*n中的逆元封闭子集.则有

(1)若A′⊆A,则Gn(A′)是Gn(A)的一个子图,此时α(Gn(A′))≥α(Gn(A)).

(2)Gn(A)不含三角形当且仅当A是无和集.

(3)若A是无和集,则α(Gn(A))≥|A|.

证明 设A′⊆A,若{x,y}是Gn(A′)的一条边,则|x-y|∈A′故|x-y|∈A,从而{x,y}是Gn(A)的一条边.即Gn(A′)是Gn(A)的一个子图,(1)得证.

为证明(2),先假定A是无和集,要证明Gn(A)不含三角形.显然,一个图不含三角形当且仅当它的任何邻域不含边.由引理1可知,Gn(A)是点传递的,点0的邻域就是A.故要证Gn(A)不含三角形,只要证明A中任何两点不相连.当A只含一点,这是平凡的.否则设A={x,y,…},其中x≠y.若x和y相连,|x-y|∈A,故存……

登录APP查看全文