輪圖和聯(lián)圖對(duì)應(yīng)圖構(gòu)形的特征多項(xiàng)式

高瑞梅, 楊文金, 代 群

(1. 長(zhǎng)春理工大學(xué) 理學(xué)院, 長(zhǎng)春 130022； 2. 北京工業(yè)大學(xué) 信息學(xué)部, 北京 100124)

0 引 言

超平面構(gòu)形是一類(lèi)具有非孤立奇點(diǎn)的超曲面, 是有限維向量空間中有限個(gè)超平面形成的集合. 超平面構(gòu)形在組合學(xué)、代數(shù)學(xué)、代數(shù)組合學(xué)、拓?fù)鋵W(xué)等領(lǐng)域應(yīng)用廣泛[1]. 目前, 構(gòu)形的研究主要集中于構(gòu)形自由性理論的Terao猜想及復(fù)空間中構(gòu)形余集的拓?fù)湫再|(zhì)等問(wèn)題上[2-6]. 研究表明, 構(gòu)形的Orlik Soloman代數(shù)的Poincaré多項(xiàng)式, 以及復(fù)構(gòu)形補(bǔ)空間的Betti數(shù)都與特征多項(xiàng)式聯(lián)系密切. 因此, 關(guān)于重構(gòu)形、子空間構(gòu)形、圖構(gòu)形等的特征多項(xiàng)式也得到廣泛關(guān)注[7-9].

目前, 構(gòu)形理論的一個(gè)主要研究對(duì)象是Coxeter構(gòu)形, 即Coxeter群的反射超平面構(gòu)成的集合. 其中Al-1-型Coxeter構(gòu)形, 即辮構(gòu)形{xi-xj=0|1≤i

1 預(yù)備知識(shí)

設(shè)K是一個(gè)域,V是域K上的n維向量空間,V中有限個(gè)超平面組成的集合稱(chēng)為一個(gè)超平面構(gòu)形, 簡(jiǎn)稱(chēng)構(gòu)形, 記為A. 用L(A)表示A中超平面所有非空交集構(gòu)成的集合. 對(duì)于x,y∈L(A), 如果x?y, 則定義x≤y, 即L(A)是反包含關(guān)系確定的一個(gè)偏序集,L(A)稱(chēng)為A的交叉偏序集. 定義M?bius函數(shù)μ:L(A)×L(A)→如下：

1) 如果x∈L(A), 則μ(x,x)=1;

構(gòu)形A的特征多項(xiàng)式χA(t)定義為

其中μ(x)=μ(V,x). 設(shè)G=(V(G),E(G))是簡(jiǎn)單圖, 即不含重邊也不含自環(huán)的無(wú)向圖, 其中:V(G)是頂點(diǎn)集;E(G)是邊集. 定義

AG={xi-xj=0|(i,j)∈E(G)},

稱(chēng)AG是G對(duì)應(yīng)的圖構(gòu)形. 若G有n個(gè)頂點(diǎn), 則AG是n維向量空間中的一個(gè)中心構(gòu)形.

定義1[13]設(shè)n為一個(gè)正整數(shù), 一個(gè)n-圈Cn定義為一個(gè)包含n個(gè)頂點(diǎn)和n條邊的圖, 且滿(mǎn)足下列性質(zhì)： 將邊記為e1,e2,…,en, 頂點(diǎn)記為a1,a2,…,an, 對(duì)每個(gè)j,ej的端點(diǎn)是aj-1和aj, 其中: 1≤j≤n;a0=an.

定義2[13]由一個(gè)n-圈添加一個(gè)新的頂點(diǎn), 并將該頂點(diǎn)與圈的所有n個(gè)頂點(diǎn)相連, 得到的圖稱(chēng)為n-輪圖, 記為Wn.

定義3[13]設(shè)n是一個(gè)正整數(shù), 一個(gè)n-路Pn定義為一個(gè)包含n條邊和(n+1)個(gè)頂點(diǎn)的圖, 且滿(mǎn)足下列性質(zhì)： 將邊記為e1,e2,…,en, 頂點(diǎn)記為a0,a1,…,an, 對(duì)每個(gè)j,ej的端點(diǎn)是aj-1和aj, 1≤j≤n.

2 主要結(jié)果

2.1 輪圖對(duì)應(yīng)構(gòu)形的特征多項(xiàng)式

將圖G對(duì)應(yīng)圖構(gòu)形的特征多項(xiàng)式簡(jiǎn)稱(chēng)為G的特征多項(xiàng)式, 記為χG(t).

引理1[14]設(shè)e=(i,j)∈E(G),G-e表示圖G去掉邊e后的圖,G/e表示圖G中的邊e縮為一點(diǎn), 再將所得圖中的重邊用單邊代替后得到的圖. 3個(gè)簡(jiǎn)單圖G,G-e,G/e的特征多項(xiàng)式之間的關(guān)系為

χG(t)=χG-e(t)-χG/e(t).

引理2[9]k個(gè)n-圈(k≥1,n≥3)簡(jiǎn)單相連所得圖G的特征多項(xiàng)式為

定理1n-輪圖Wn(n≥3)的特征多項(xiàng)式為

χWn(t)=t(t-2)[(t-2)n-1+(-1)n].

證明: 對(duì)n利用數(shù)學(xué)歸納法. 當(dāng)n=3時(shí), 3-輪圖對(duì)應(yīng)的特征多項(xiàng)式為

χW3(t)=t(t-1)(t-2)(t-3)=t(t-2)[(t-2)2+(-1)3].

假設(shè)對(duì)(n-1)-輪圖, 結(jié)論成立. 先考慮n-輪圖, 設(shè)e為Wn中圈的一條邊, 則Wn-e為(n-1)個(gè)3-圈簡(jiǎn)單相連所得的圖.Wn/e為(n-1)-輪圖. 因此由引理2和歸納假設(shè), 可得

χWn-e(t)=t(t-1)(t-2)n-1,

χWn/e(t)=t(t-2)[(t-2)n-2+(-1)n-1].

再由引理1, 可得

χWn(t)=χWn-e(t)-χWn/e(t)=t(t-2)[(t-2)n-1+(-1)n].

證畢.

例1由定理1知, 如圖1所示的5-輪圖的特征多項(xiàng)式為

χW5(t)=t(t-1)(t-2)(t-3)(t2-4t+5).

2.2 聯(lián)圖的特征多項(xiàng)式

定義4設(shè)G1={V1,E1},G2={V2,E2}均為簡(jiǎn)單圖, 且G1∩G2=?. 定義G1與G2的聯(lián)圖G1∨G2的頂點(diǎn)集和邊集分別為

V(G1∨G2)=V1∪V2,

E(G1∨G2)=E1∪E2∪{(i,j)|i∈V1,j∈V2}.

定義5(m-1)-路與(n-1)-路的聯(lián)圖記為G(m,n).

例2聯(lián)圖G(2,3)如圖2所示.

引理3[14]完全圖Kn的特征多項(xiàng)式為

χKn(t)=t(t-1)(t-2)…(t-n+1),

簡(jiǎn)記為t(n).

定理2n-路Pn的特征多項(xiàng)式為

χPn(t)=t(t-1)n.

證明: 對(duì)n利用數(shù)學(xué)歸納法. 當(dāng)n=1時(shí), 易得

χP1(t)=t(t-1),

結(jié)論成立. 假設(shè)對(duì)(n-1)-路, 結(jié)論成立. 下面考慮n-路的情形, 取e=en, 則Pn-e為(n-1)-路和孤立點(diǎn)an的不相交并集,Pn/e為(n-1)-路. 因此由歸納假設(shè), 可得

由引理1知,

χPn(t)=χPn-e(t)-χPn/e(t)=t(t-1)n.

證畢.

定理3n-路Pn的特征多項(xiàng)式還可表示為

其中:

t(k)=t(t-1)…(t-k+1),k=2,3,…,n+1;

B=(1n-1,2n-1,…,(n-1)n-1,nn-1)T.

證明: 由定理2可知, 需先證下列等式成立：

由于式(1)的左右兩端都有因式t(t-1), 即需證下列等式成立：

令

f(t)=(t-1)n-1,

由于C=AB, 則A-1C=B, 即

則

由于

deg(f(t))=deg(g(t))=n-1且g(i)=f(i)(i=2,3,…,n+1),

則g(t)=f(t), 結(jié)論成立.

例3由定理3可知, 4-路的特征多項(xiàng)式為

χG(t)=t(5)+6t(4)+7t(3)+t(2).

引理4[15]設(shè)G1,G2是簡(jiǎn)單圖, 則G1,G2的聯(lián)圖G的特征多項(xiàng)式為

χG(t)=χG1(t)°χG2(t),

其中“°”表示t(k)°t(l)=t(k+l).

由定理3和引理4可得:

定理4聯(lián)圖G(m,n)的特征多項(xiàng)式為

例4聯(lián)圖G(3,4)的特征多項(xiàng)式為