輪圖和聯(lián)圖對應圖構形的特征多項式

高瑞梅, 楊文金, 代 群

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

0 引 言

超平面構形是一類具有非孤立奇點的超曲面, 是有限維向量空間中有限個超平面形成的集合. 超平面構形在組合學、代數(shù)學、代數(shù)組合學、拓撲學等領域應用廣泛[1]. 目前, 構形的研究主要集中于構形自由性理論的Terao猜想及復空間中構形余集的拓撲性質等問題上[2-6]. 研究表明, 構形的Orlik Soloman代數(shù)的Poincaré多項式, 以及復構形補空間的Betti數(shù)都與特征多項式聯(lián)系密切. 因此, 關于重構形、子空間構形、圖構形等的特征多項式也得到廣泛關注[7-9].

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

1 預備知識

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

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

構形A的特征多項式χA(t)定義為

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

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

稱AG是G對應的圖構形. 若G有n個頂點, 則AG是n維向量空間中的一個中心構形.

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

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

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

2 主要結果

2.1 輪圖對應構形的特征多項式

將圖G對應圖構形的特征多項式簡稱為G的特征多項式, 記為χG(t).

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

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

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

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

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

證明: 對n利用數(shù)學歸納法. 當n=3時, 3-輪圖對應的特征多項式為

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

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

χ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-輪圖的特征多項式為

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

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

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

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的特征多項式為

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

簡記為t(n).

定理2n-路Pn的特征多項式為

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

證明: 對n利用數(shù)學歸納法. 當n=1時, 易得

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

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

由引理1知,

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

證畢.

定理3n-路Pn的特征多項式還可表示為

其中:

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), 結論成立.

例3由定理3可知, 4-路的特征多項式為

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

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

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

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

由定理3和引理4可得:

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

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