中国学术期刊网 » 论文 » 理学论文 » 数学论文 » 多边形连接不同对图构形中超平面相交关系的影响论文正文

多边形连接不同对图构形中超平面相交关系的影响

中国学术期刊网【数学论文】 编辑:天问 山东大学学报(理学版) 2016-11-04多边形连接不同对图构形中超平面相交关系的影响论文原文发表在《山东大学学报(理学版)杂志》,经中国学术期刊网小编精心整理,仅供您参考。

关键词: 超平面构形 特征多项式 图构形 L-等价 π-等价
摘要: 图构形是构形领域研究的与图相关的一类超平面构形。给出了多边形简单相连和点相连的定义, 研究简单相连多边形对应的图构形的特征多项式, 并给出其具体表达式。通过具体例子说明多边形连接方式和连接顺序的不同对图构形中超平面相交关系的影响。

0 引言

超平面构形是指有限维向量空间中有限个超平面所形成的集合。通常将超平面构形简称为构形。构形理论是一门新兴的学科, 由于其涵盖内容广泛以及研究手法多样, 受到越来越多学者的关注[1]。目前, 构形的主要研究内容之一,是围绕着解决Terao猜想“构形的自由性只取决于其组合结构”展开的。由于Shi构形和Catalan构形具有高度的对称性, 并且与反射群具有密切的联系, 因此学者们从这两类构形以及它们的推广形式入手, 深入研究构形的自由性[2-8]。

构形理论中有一类构形是由图定义的构形, 称为图构形。本文只考虑简单图, 即不含平行边也不含自环的无向图。图构形受到学者们青睐的原因之一是具有n个顶点的简单图G所对的图构形AAG是An-1型Coxeter构形的一个子构形; 原因之二是图构形AG的很多组合、代数、拓扑性质与G的性质具有密切联系。例如, 文献[9]中指出, 图构形AG是超可解的当且仅当G是一个弦图, 即G的每个长度至少为4的圈都包含弦。另外, 文献[10]中指出, 图构形AG是超可解的当且仅当AG是自由的。这两个结论说明, G的组合结构完全决定了AG的超可解性和自由性。由于图构形具有这样好的性质, 符号图、增益图、ψ图等简单图的推广形式对应的图构形的超可解性和拓扑性质也得到了学者们的关注[11-17]。

特征多项式是构形的一个组合不变量, 对它的研究具有重要的意义[18-19]。本文利用构形中的“删除-限制”原理, 通过建立简单图的着色多项式与其对应图构形的特征多项式之间的关系, 研究了简单相连多边形对应的图构形的特征多项式, 给出简单相连多边形对应的图构形的特征多项式与多边形相连的顺序与方式均无关的结论, 并给出了特征多项式的具体表达形式。最后, 通过一个例子说明若干多边形按不同方式简单相连和按不同顺序简单相连, 对构形中超平面相交关系的影响。

1 基本概念

设K是一个域, V是域K上的维向量空间, 将V中有限个超平面所组成的集合称为一个超平面构形, 记为A,简称为构形。将Q(A)=∏H∈AαH称为构形A的定义多项式, 其中αH∈K[x1, …, x]满足ker(αH)=H, x1, …, x是V的对偶空间V*的基底。如果构形A中的每一个超平面都经过原点, 称构形A为中心构形, 否则称为非中心构形。

设A是一个构形, 用L(A)表示A中任意个超平面的非空交集所形成的集合, 定义L(A)中的一个偏序为X≤Y⇔Y⊆X, 称L(A)为构形A的相交偏序集。定义Möbius函数

μA=μ:L(A)×L(A)→Z

如下:

μ(X,X)=1,如果X∈L(A)∑X≤Z≤Yμ(X,Y)=0,如果X,Y,Z∈L(A),AX
定义A的特征多项式

χ(A,t)=∑X∈L(A)μ(X)tdim(X),

式中μ(X)=μ(V, X)。定义构形A的Poincaré多项式

π(A,t)=∑X∈L(A)μ(X)(−t)r(X),

式中r(X)=codimVX。构形A的特征多项式和Poincaré多项式的关系为

χ(A,t)=tπ(A,−1 t )。

设(A1, V1)和(A2, V2)是2个构形, 且V=V1⊕V2, 定义其乘积构形(A1×A2, V)为:

A1×A2={H1⊕V2|H1∈A1}∪{V1⊕H2|H2∈A2}。

如果在坐标变换之下, 构形A可以写成A=A1×A2, 则称构形A是可约的, 否则称A是不可约的。若A=A1×A2, 则π(A, t)=π(A1, t)π(A2, t)。

对于构形A和B, 如果存在一个保序双射φ:L(A)→L(B), 则称A和B是L-等价的; 如果π(A, t)=π(B, t), 则称A和B是π-等价的。L-等价的2个构形一定是π-等价的, 而π-等价的2个构形未必是L-等价的。

设G=(V(G), E(G))是n个顶点的简单图, 其中V(G)是顶点集, E(G)是边集。定义

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

称AG是G对应的图构形。显然, 图构形均是中心构形。将图G对应的图构形的特征多项式简称为G的特征多项式, 并记为χG(t)。

2 主要结论

在此部分主要给出n个多边形简单相连所得简单图的特征多项式。首先, 给出几个引理和基本定义。

下面是根据构形中经典的“Deletion-Restriction”原理得到的有关图构形特征多项式的结论。

引理2.1[20] 设G是一个简单图, 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.2[20] 设G是一个n边形, n≥3, 则G的特征多项式为

χG(t)=(t−1)n+(−1)n(t−1)。

关于两个简单图的连接方式, 给出下面两种方式。

定义2.1 设G1, G2是2个简单图, 且存在

e1={i1,j1}∈E(G1),e2={i2,j2}∈E(G2),

满足

deg(ik)=deg(jk)=2,k=1,2。

若将G1和G2进行粘接, 使得G1的边e1和G2的边e2重合, 则称G1和G2的这种连接方式是简单相连。若G1和G2有且只有一个公共点, 则称G1和G2的这种连接方式是点相连。

下面, 给出两个多边形简单相连和点相连的具体例子, 对于两种相连方式给出一个直观表述。

例2.1 一个六边形和一个四边形简单相连, 一个五边形和一个三角形点相连的例子如图 1所示。

图 1
图 1 简单相连和点相连的例子
Fig. 1 The examples of simply-connected and point-connected graphs
引理2.3 设简单图G1和G2分别有m和n个顶点, m, n≥3, 且这两个图是点相连的, 则G1∪G2的特征多项式为

χG1∪G2(t)=1 t χG1(t)χG2(t)

证明 由于G1和G2是点相连的, 因此图构形AG1∪G2是可约的, 即AG1∪G2=AG1×AG2, 因此πG1∪G2(t)=πG1(t)πG2(t), 故

χG1∪G2(t)=tm+n−1πG1∪G2(−1 t )=tm+n−1πG1(−1 t )πG2(−1 t )=1 t [tmπG1(−1 t )][tnπG2(−1 t )]=1 t χG1(t)χG2(t)。

由于t|χG1(t)且t|χG2(t), 因此表达式1 t χG1(t)χG2(t)确实是一个多项式。

定理2.1 设有k个多边形, 顶点个数分别为n1, n2, …, nk, 其中k≥1, n1, n2, …, nk≥4, 若此k个多边形按顺序两两简单相连, 则所得的简单图的特征多项式与连接的方式无关。

证明 用数学归纳法证明。当k=1时结论显然。

假设多边形个数为k时结论成立。当多边形个数为k+1时, 有k+1个多边形按顺序两两简单相连。由于相邻多边形连接的方式不同, 可以得到不同的图, 设G1、G2是其中任意两个,只考虑G1(或G2)中最后2个多边形, 设G1(或G2)中最后2个多边形的公共边为e1(或e2), 则G1-e1(或G2-e2)为k个多边形按顺序两两简单相连, 顶点个数分别为n1, n2, …, nk-1, nk+nk+1-2, 由归纳假设, 可知

χG1−e1(t)=χG2−e2(t)。

下面考虑G1/e, G1/e是图H1和一个(nk+1-1)边形I1点相连后的图, 其中H1是G1中的前k个多边形按照G1中的方式两两简单相连, 并且第k个多边形的边e1缩为一点后的图形。由引理2.3可知,

χG1/e(t)=1 t χH1(t)χI1(t)。

类似地, 对于图G2/e, 可找到H2和I2, 并且χG2/e(t)=1 t χH2(t)χI2(t)。由归纳假设, 可知χH1(t)=χH2(t)。由于I1和I2均为(nk+1-1)边形, 由引理2.2可知, χI1(t)=χI2(t)。因此χG1/e1(t)=χG2/e2(t)。再由引理2.1可知,

χG1(t)=χG1−e1(t)−χG1/e1(t)=χG2−e2(t)−χG2/e2(t)=χG2(t)。

定义2.2 定义如下的几个符号:

P(n):=(t-1)n+(-1)n(t-1), n∈Z+;

s⊕t:=一个s边形和一个t边形简单相连后的简单图的特征多项式, s, t≥4;

s⊕t:=一个s边形和一个t边形点相连后的简单图的特征多项式,s, t≥4。

由引理2.2和定义2.2可知, 一个n边形的特征多项式为P(n)。另外, 定义2.2中的符号“⊕”和“⊗”可以自然推广到k个多边形上(k > 2)。

引理2.4 对任意的m, n∈Z+, 有P(m+1)P(n+1)=t(t-1)P(m+n)-(t-1)P(m)P(n)。

证明 由定义2.2可知,

t(t−1)P(m+n)−(t−1)P(m)P(n)=t(t−1)m+n+1+(−1)m+nt(t−1)2−[(t−1)m+n+1+(−1)n(t−1)m+2+(−1)m(t−1)n+2+(−1)m+n(t−1)3]=(t−1)m+n+2+(−1)n+1(t−1)m+2+(−1)m+1(t−1)n+2+(−1)m+n(t−1)2=P(m+1)P(n+1)。

定理2.2 设有k个多边形, 顶点个数分别为n1, n2, …, nk, 其中k≥1, n1, n2, …, nk≥4, 若此k个多边形按顺序两两简单相连, 则所得的简单图的特征多项式为

n1⊕n2⊕⊕nk=P(n1)P(n2)P(nk) [t(t−1)]k−1 。

证明 由定理2.1可知, k个多边形按顺序两两简单相连, 所得简单图的特征多项式是唯一的。另外, 由于t(t-1)|P(ni), (i=1, …, k), 故定理中的表达式确实是一个多项式。

用数学归纳法证明此定理。当k=1时, 结论显然成立。

假设多边形个数为k时结论成立。当多边形个数为k+1时, 设最后两个多边形的公共边为e, 应用引理2.1, 2.3, 2.4, 有如下结论:

n1⊕nk+⊕nk+1=n1⊕⊕nk−1⊕(nk+nk+1−2)−[n1⊕⊕nk−1⊕(nk−1)]⊗(nk+1−1)=p(n1)P(nk−1)P(nk+nk+1−2) [t(t−1)]k−1 −1 t P(n1)P(nk−1)P(nk−1) [t(t−1)]k−1 P(nk+1−1)=p(n1)P(nk−1) [t(t−1)]k−1 [P(nk+nk+1−2)−1 t P(nk−1)P(nk+1−1)]=p(n1)P(nk−1) [t(t−1)]k [t(t−1)P(nk+nk+1−2)−(t−1)P(nk−1)P(nk+1−1)]=p(n1)P(nk−1) [t(t−1)]k P(nk)P(nk+1)=P(n1)P(nk+1) [t(t−1)]k 。

归纳完成, 结论成立。

推论2.1 设有k个多边形, 顶点个数分别为n1, n2, …, nk, 其中k≥1, n1, n2, …, nk≥4, 此k个多边形按任意顺序两两简单相连, 所得到的简单图的特征多项式均为定理2.2中的结果。

证明 由定理2.2中的特征多项式的表达形式可知, n1, n2, …, nk不管如何排列, 均不改变特征多项式的结果, 因此推论正确。

推论2.2 设有k个n边形(k≥1, n≥4)两两简单相连, 所得到的简单图的特征多项式为

P(n)k [t(t−1)]k−1 =[(t−1)n+(−1)n(t−1)][(−1)n+n−1∑i=2(−1)i(t−1)n−i]k−1。

例2.2 3个多边形简单相连的不同情况如图 3所示, 它们的特征多项式均为

P(4)P(5)P(6) [t(t−1)]2 =t(t−1)(t−2)(t2−2t+2)(t2−3t+3)(t4−5t3+10t2−10t+5)。

G1, G2具有相同的特征多项式, 是因为由定理2.1, 特征多项式与简单相连的方式无关。G1, G3具有相同的特征多项式, 是因为由推论2.1, 特征多项式与3个多边形相连的顺序无关。由于G1, G2, G3的特征多项式相同, 因此它们的Poincaré多项式也相同, 故G1, G2, G3所对应的图构形AG1, AG2, AG3是两两π-等价的。