有限交換環(huán)上Ramanujan二次單位一-匹配雙凱萊圖

茍小麗

(蘭州交通大學 數理學院，甘肅 蘭州 730070)

0 引言

本文所考慮的圖均為簡單無向圖.設圖G的頂點集為V(G)={1,2,…,n},它的鄰接矩陣為A=(aij)n×n,其中當頂點i和j相鄰時,aij=1; 否則aij=0.圖G的特征值是其鄰接矩陣的特征值.

設A(G)的互異特征值為λ1>λ2>…>λk,且它們的重數分別為m(λ1),m(λ2),…,m(λk),則圖G的譜記為

一個有限k-正則圖G稱為Ramanujan圖[1],如果

其中：λ(G)為G的不同于±k的特征值絕對值的最大值.關于Ramanujan圖及相關擴展圖的研究, 可參考文獻[2-8].

1878年，A Cayley 為解釋群的生成元和定義關系首次提出凱萊圖的概念.1992年, Resmini 和 Jungnickel[9]定義了雙凱萊圖.

設H是一個具有單位元1H的群,R,L,S是H的子集,且1H?R=R-1,1H?L=L-1,則H上的雙凱萊圖BC(H;R,L,S)是指以H×{0,1}為頂點集的無向圖,且(h,i)和(g,j)相鄰,當且僅當以下條件之一成立:

(i)i=j=0且gh-1∈R;

(ii)i=j=1且gh-1∈L;

(iii)i=0,j=1且gh-1∈S.

特別地,若S由H的單位元構成, Kovács 等[10]稱其為H上的一-匹配雙凱萊圖.

關于(一-匹配)雙凱萊圖的一些組合性質和代數性質,其中包括弧傳遞性、強正則性、自同構和點傳遞性,可參考文獻[9-12].

設R是有單位元1≠0的有限交換環(huán),R×表示其單位的集合.局部環(huán)是有唯一極大理想的交換環(huán)[13].由文獻[13-14]可知,若R是具有唯一極大理想M的局部環(huán),則R×=RM.每個有限交換環(huán)可表示為有限局部環(huán)的乘積,且這種分解在不計此類局部環(huán)的排列次序時是唯一的.因此,后續(xù)討論總是基于以下假設.

假設1[4]R=R1×R2×…×Rs是具有單位元1≠0的有限交換環(huán),其中Ri是具有mi階極大理想Mi的局部環(huán).設

|R1|/m1≤|R2|/m2≤…≤|Rs|/ms.

顯然,

(1)

定義1[5]給定一個交換環(huán)R,R上的二次單位凱萊圖GR定義為R關于TR=QR∪(-QR)在加法群上的凱萊圖Cay(R，TR),其中QR={u2:u∈R×},即GR有頂點集R,使得x,y∈R相鄰,當且僅當x-y∈TR.

這個概念是Zn上的二次單位凱萊圖GZn的推廣[15], 當n≡1(mod 4)且為素數時, GZn是n階Paley圖.隨著對GZn結構性質的進一步研究,de Beaudrap將GZn在n的素因子上分解為張量積, 還計算了GZn的直徑, 并給出GZn是完美的條件[15].

文獻[16]基于單位凱萊圖的概念定義了單位一-匹配雙凱萊圖.本文類比單位一-匹配雙凱萊圖的概念, 在二次單位凱萊圖的基礎上定義了二次單位一-匹配雙凱萊圖的概念.

定義2給定一個交換環(huán)R,R上的二次單位一-匹配雙凱萊圖GR定義為R加法群上的一-匹配雙凱萊圖BC(R;TR,TR,{0}),其中TR=QR∪(-QR),QR={u2:u∈R×}.

2015年,劉曉剛等[5]給出了二次單位凱萊圖是 Ramanujan 圖的等價刻畫.受此啟發(fā),本文主要討論了二次單位一-匹配雙凱萊圖是 Ramanujan 圖的等價條件.

1 二次單位一-匹配雙凱萊圖

兩個圖G和H的笛卡爾積記作G□H,其頂點集為V(G)×V(H),頂點(u,v)和(x,y)相鄰當且僅當v=y且u和x在G中相鄰,或u=x且v和y在H中相鄰.

引理1[17]設G和H是兩個圖,其特征值分別為λ1,λ2,…,λn和μ1,μ2,…,μm,則G和H的特征值為λi+μj,1≤i≤n,1≤j≤m.

引理2[5]設R是具有m階極大理想M的局部環(huán),則

(1)若|R|/m≡1(mod 4),則

(2)若|R|/m≡3(mod 4),則

Spec(GR)=

根據二次單位一-匹配雙凱萊圖和笛卡爾積的定義,有GR?Cay(R,TR)□P2=GR□P2,其中P2為2長路.由引理1和2可得如下結論.

定理1設R是具有m階唯一極大理想M的局部環(huán),則

(1)若|R|/m≡1(mod 4),則

(2)若|R|/m≡3(mod 4),則

Spec(GR)=

引理3[5]設R如假設1所示,則GR=GR1?GR2?…?GRs當且僅當至多存在一個Rj,使得-1?QRj.

定理2設R如假設1所示,|Ri|/mi≡1(mod 4),1≤i≤s,則

GR=(GR1?GR2?…?GRs)□P2.

證明根據二次單位一-匹配雙凱萊圖和笛卡爾積的定義,有

GR?Cay(R,TR)□P2=GR□P2,

其中P2為2長路.因為|Ri|/mi≡1(mod 4),1≤i≤s,所以-1∈QRi/Mi,1≤i≤s,于是-1∈QRi,1≤i≤s,從而由引理3可知,

GR=GR1?GR2?…?GRs,

故GR=(GR1?GR2?…?GRs)□P2.

令

λA,B=(-1)|B|·

其中，A,B為{1,2,…,s}的不交子集[5].特別地,λ?，?=|R×|/2s.

引理4[5]設R如假設1所示,|Ri|/mi≡1(mod 4),1≤i≤s,則GR的特征值為

(1)λA,B,重數為

其中,所有的(A,B)對均為{1,2,…,s}的子集,且A∩B=?;

(2)0，重數為

|R|-

由引理1, 定理2和引理4可得:

定理3設R如假設1所示,|Ri|/mi≡1(mod 4),1≤i≤s,則GR的特征值為

(1)λA,B±1,重數為

其中,所有的(A,B)對均為{1,2,…,s}的子集,且A∩B=?;

(2)±1,重數為

|R|-

引理5[5]設R如假設1所示,|Ri|/mi≡1(mod 4),1≤i≤s,R0是具有m0階極大理想M0的局部環(huán),且|R0|/m0≡3(mod 4),則GR0×R的特征值為

其中,所有的(A,B)對均為{1,2,…,s}的子集,且A∩B=?;

其中,所有的(A,B)對均為{1,2,…,s}的子集,且A∩B=?;

(3)0,重數為

|R|-

由引理1, 定理2和引理5可得：

定理4設R如假設1所示,|Ri|/mi≡1(mod 4),1≤i≤s,R0是具有m0階極大理想M0的局部環(huán),且|R0|/m0≡3(mod 4),則GR0×R的特征值為

其中,所有的(A,B)對均為{1,2,…,s}的子集，且A∩B=?;

其中,所有的(A,B)對均為{1,2,…,s}的子集,且A∩B=?;

(3)±1,重數為

|R|-

推論1(1)若p≡1(mod 4)為素數,且α≥1為整數,則

Spec(GZpα)=

(2)若p≡3(mod 4)為素數,且α≥1為整數,則

Spec(GZpα)=

(1)

(2)±1,重數為

(1)

(2)

(-1)|B|+1·

重數為

其中所有的(A,B)對均為{1,2,…,s}的子集,且A∩B=?;

(3)±1,重數為

2 Ramanujan二次單位一-匹配雙凱萊圖

引理6[18]設R是具有m階唯一極大理想的有限局部環(huán),則存在素數p使得|R|,m和|R|/m都是p的冪次.

定理5設R如假設1所示,|Ri|/mi≡1(mod 4),1≤i≤s,R0是具有m0階極大理想M0的局部環(huán),且|R0|/m0≡3(mod 4),則

(1)GR0是Ramanujan圖,當且僅當

(2)GR是Ramanujan圖,當且僅當R?Fq,其中q≡1(mod 4)為素數的冪;

(3)GR0×R是Ramanujan圖,當且僅當

R0×R?F3×F9.

證明由文獻[5]可知,GR0的正則度為|R0×|=|R0|-m0,GR的正則度為|R×|/2s,GR0×R的正則度為|R0×||R×|/2s.則由引理1和定理2可知,GR0的正則度為|R0|-m0+1,GR的正則度為|R×|/2s+1,GR0×R的正則度為|R0×||R×|/2s+1.

(1)根據定理1(2),當|R0|-m0-1≥m0+1,即|R0|≥2m0+2時,GR0是Ramanujan圖

當|R0|-m0-1≤m0+1,即|R0|≤2m0+2時,GR0是Ramanujan圖

(2)根據定理3,GR是Ramanujan圖

λA,B±1≠±(|R×|/2s+1).

因為|λA,B±1|≤|λA,B|+1≤|λ?，{1}|+1≠|R×|/2s+1,所以GR是Ramanujan圖

(2)

(3)

又因為

則當s≥4時,由式(1)可知,

|R×|/2s≥

即式(3)不成立,所以GR不是Ramanujan圖.

下面考慮1≤s≤3的情況.

情形1s=1.

若m1≥8時,以上不等式不成立,所以GR不是Ramanujan圖.

假設m1≤7,因為|R1|/m1≡1(mod 4),所以由引理6可知,m1=1,3,5或7.

由文獻[19]可知, 具有素數階p的極大理想的有限交換局部環(huán)是Zp2和Zp[X]/(X2),它們的剩余域均為Zp,又由|R1|/m1≡1(mod 4)可知m1=1或5.

當m1=1時,R1?Fq，q≡1(mod 4)為素數的冪.根據式(2),所以GFq是Ramanujan圖.

當m1=5時,R1?Z25或Z5[X]/(X2).此時式(2)不成立,所以GR不是Ramanujan圖.

情形2s=2.

此時,式(3)等價于

若m1m2≥4或|R2|/m2≥17,則以上不等式不成立,所以GR不是Ramanujan圖.

假設m1m2≤3,|R2|/m2≤16.

因為|Ri|/mi≡1(mod 4),i=1,2,所以由引理6可知m1m2=1或m1m2=3.注意到,Z9和Z3[X]/(X2)是恰有3個元素的唯一極大理想的局部環(huán),它們的剩余域均為Z3,這與|Ri|/mi≡1(mod 4),i=1,2矛盾,所以m1m2=3不可能出現,因此m1m2=1,且以下條件之一將會出現:

(Ⅰ)R1?R2?F5;

(Ⅱ)R1?R2?F9;

(Ⅲ)R1?R2?F13;

(Ⅳ)R1?F5，R2?F9;

(Ⅴ)R1?F5，R2?F13;

(Ⅵ)R1?F9，R2?F13.

將其依次代入式(2),式(2)均不成立,所以GR不是Ramanujan圖.

情形3s=3.

此時,式(3)等價于

因為|Ri|/mi≡1(mod 4).i=1,2,3,所以R1?R2?R3?F5,此時式(2)不成立,所以GR不是Ramanujan圖.

(3)令

|λ|=

由定理4可知,GR0×R是Ramanujan圖

設

μA,B=

此時,GR0×R是Ramanujan圖

(4)

因為

所以式(4)不成立,除非

(5)

又因為

所以當s≥3時,由式(1)可知,

即式(5)不成立,所以GR0×R不是Ramanujan圖.

下面考慮1≤s≤2的情況.

子情形1.1s=1.

此時,式(5)等價于

m0m1((|R0|/m0)-1)((|R1|/m1)-1)<

若m0m1≥4或|R0|/m0≥9,則以上不等式不成立,所以GR0×R不是Ramanujan圖.

假設m0m1≤3,|R0|/m0≤8.

由引理6可知m0m1=1或m0m1=3.又因為|R0|/m0≡3(mod 4),|R1|/m1≡1(mod 4),所以m0=m1=1或m0=3,m1=1.

當m0=m1=1時,R0?F3或R0?F7.

R0×R1?F3×F5,F7×F5,

F7×F9,F7×F13,F7×F17,

F7×F25,F7×F29,F7×F37或F7×F41.

將其依次代入式(4)中,式(4)均不成立,所以GR0×R不是Ramanujan圖.

當m0=3,m1=1時,R0?Z9或Z3[X]/(X2).

子情形1.2s=2.

此時,式(5)等價于

因為|R0|/m0≡3(mod 4),|Ri|/mi≡1(mod 4),i=1,2,則R0?F3,R1?R2?F5,此時式(4)不成立,所以GR0×R不是Ramanujan圖.

此時,GR0×R是Ramanujan圖

(6)

因為

所以式(6)不成立,除非

(7)

當s≥3時,由式(1)可知,

即式(7)不成立,所以GR0×R不是Ramanujan圖.

下面考慮1≤s≤2的情況.

子情形2.1s=1.

此時,式(7)等價于

8((|R0|/m0)-1).

若m0m1≥3或|R1|/m1>49,則以上不等式不成立,所以GR0×R不是Ramanujan圖.

假設m0m1≤2,|R1|/m1≤49.

因為|R0|/m0≡3(mod 4),|R1|/m1≡1(mod 4),則由引理6可知,m0=m1=1.于是

R1?F5,F9,F13,F17,F25,F29,F37,F41或F49,

R0×R1?F3×F9,F3×F13,F3×F17,

F3×F25,F3×F29,F3×F37,F3×F41,

F3×F49或F7×F49.

將其依次代入式(6)中,得GF3×F9是Ramanujan圖.

子情形2.2s=2.

此時,式(7)等價于

4((|R0|/m0)-1)2.