关于cycle-likegraph的独立多项式

1、7关于cycle-like graph的独立多项式引言独立多项式是组合数学中一个很重要的研究方向，它在染色问题、匹配问题等多个重要的问题中能起到至关重要的作用。但是，对于独立多项式的研究现在还并不完善。关于一些性质良好的图，我们希望能够明确的知道其独立多项式根 的情况以及是否具有单峰性或10g凹性，对此有很多数学家进行了不懈的尝试， 但至今成果仍不足以令人满意，未解决的猜想还有很多。比如关于树以及二部图 的独立多项式是否具有上述性质。本文将讨论一种特殊的图cycle-like graph是否具有上述的良好性质。这种图脱胎于1中介绍的path-like graph,是一种性质良好且具有一定代表意

2、义的 图，下面的讨论将是对1中结论的一个扩展。本文最终将会说明cycle-like graph 仍然具有与path-like graph相同的一个良好性质，即在特定条件下根全为实根， 因此在该条件下它也是10g凹、单峰的。为了开始证明上述结论，一些定义和引理是有必要的。设G =(V,E)是点集为V,边集为E的图，Nv表示v及其邻点。U为V的 一个子集，G-U表示由V U生成的G的子图。称G中一组两两不相邻的点集作最大独立集，其大小设为 (G)I(G,x)SkXkk 0为G的一个独立集，其大小定义为该点集所含点的个数。大小最大的独立集称a(G)接下来定义独立多项式I(G,x)如下。2 I(G)s

3、0s1x s2xL s (G)x ')其中sk表示大小为k的独立集的个数称一个多项式P(x)一一，2的 i, 1<i<n-1,都有 ai在 j, 0vjvn,有 a0司na xi是log-concave的，如果其系数满足对于任意i 0ai向1。称一个多项式是单峰的，如果其系数满足存L aj aj 1 Lan。显然，满足log凹性的多项式一定也是单峰的接下来在2中的结论是一个基础的结论，它将会十分有用:n引理1.1若多项式P(x) axi ( ai 0)的根全为实根，则数列是 i 0log-concave 的， 显然, 也是 log-concave 的。有了这个引理，如果能够

4、证明一个独立多项式的根全为实根，那么我们所希 望的性质，10g凹性与单峰性自然满足。接下来给出关于path-like graph以及cycle-like graph的一系列定义。我们把长度为n的kt-path记作P(t,n)=(V,E),其中V= WL vt n 1,E= Vi,Vi j |1 i t n 2,1min t 1,tn i 1显然，当t=2时，P(t,n)就是长度为n+1的pathv)如下：V(G*(U , v)=V uv, E(G*(U , v)= 一个点均作此处理，每一点对应一个相应的图若F是一个图，G, U如上定义，v是G以外的一个点，那么定义 G*(U , u,v|ueU

5、。若对于r的每G且与其中的点集U相连，即令G*(U, v)中的点v遍历r的点集，得到的图记作rv(GU),那么此时我们可以给出1中 path-like graph 的定义：P(t,n)V(G,U) 0这里需要做几个说明。首先1中的结论是对于任意的t 2,n 0均成立的。 但由于本文并未用到t=2之外的情况(也就是只用到了 1中的第一个case,所 以做约定如下：记I(P(2,n)V(G,U),x)为pn ,后文中出现的pn均为该独立多项式， 这与1中的记号是相同的。类似的，我们引出本文定义的 cycle-like graph: On V(G,U)0其中g表示包 含n个点的cycle。同样，我们

6、也做约定如下：记I( cn (GU),x)仍为Cn,后文 中出现的Cn均指代该多项式，为避免歧义特此说明。至此，可以给出本文的最终结果。定理 1.2 设 b(x)=I(G,x), c(x)=I(G U,x)0 若 deg(b)=deg(c)+2, c|b(in Zx), 且b, c的根全为实根，则对于任意的n 1, Cn全为实根。值得注意的是，满足这样看似苛刻条件的图并不是很难找到， 比如用完全图 去掉一条边或去掉两条相临边得到的图作为 G,全部点集V作为U,这个情形 是满足上述条件的。关于这个定理的证明将会在第二章给出为了证明定理1.2,这里给出两个在计算独立多项式时必不可少的基本引理。它

7、们可以在2中找到。为了方便起见，我们将其归为一个引理。引理 2.1 G1 与 G2 是不相交的两个图，I(G1 uG2,x)=I(G1,x)*I(G2,x)。对于 G 中任意一点 v, I(G,x)=I(G-v,x)+x*I(G- Nv,x)。这两个引理十分直观，并不难证明，这里不过多的讨论了。接下来将会给出两个1中的结论。由于本文是1的一个扩展，所以下面给 出的引理是我们进一步计算证明的关键。首先介绍一个符号。若fm|g成立，fm1|g不成立，我们称fm恰好整除g,记作fm|g。引理2.2若deg(b)=deg(c)+2, c|b(in Zx),并且 b, c的根全为实根，则nn 1nb 2

8、 | Pnc- |(Pn/b2 )通过Pn的递推公式使用数学归纳法可得到这个结论。因为b, C的根均为实根，由这个引理可知，想要得到关于 Pn的根的结论, 去掉上述次方的b, C后剩下的多项式将会是核心。在1中对于这个问题已有了 相当完整的解答，下面的定理将会全面的给出这个核心多项式的性质。引理 2.3 若 deg(b)=deg(c)+2, c|b(in Zx),并且 b, c 的根全为实根，n n 1记n = Pn/(b2 *c=)。则有对于任意的n 2有b._ -% 1 xrn 2 n = crn 1 xrn 2n为偶数n为奇数b 其中r0=+x, cr1 =b +2xcn deg(rn)

9、=nn为偶数n为奇数n为为为为xrn 2有n+1个根 i,Ln,0,、有n+2个根 J , nA其中n 1<L < n 2<0 2bn是一的两个根。满足下面条件:2 2 c1< 1< 2< 2<L < n < n 1< n 2<222b 一n为为为为xrn 2有n个根 1,L , ni,0, rn 1有n+1个根 i,L, -,其中一的 c两个根在n 1, n 3之间。满足下面条件： -2-1< 1< 2< 2<L< 1< 吧< 它 < 上 <L< n i<0上面

10、这个引理是1中case 1的核心结论，可以看到这个引理已经包括了 rn全 为实根的结论了。不仅如此，它还给出了rn与它前两项的根之间的关系。这里需要指出，无论是这个引理的结论还是证明方法都极其重要。这个加强命题是通过数学归纳法得到证明的，在未知。是否全为实根时，利用引理中后半段作为归纳假设可以推出rn的根落在哪些区间内，这个方法和结论都将在后面的证明 中出现，到时再详细阐述。有了引理2.3,我们可以开始证明定理1.2 了。首先由引理2.1可知C3 P1b xcb2 cb2(b 3x)显然是全实根的。 c2n 4 时由引理 2.1 有 Cn Pn 2b xcb Pn 4n n 1再由引理2.2可

11、得Cn b ' c- (rn 2 xrn 4)所以，只需证明rn2 xrn 4对于任意的n 4满足根全为实根即可。这等价于证明rn xrn 2对于任意的n 2满足根全为实根。接下来我们分两种情况讨论。Case 1 n为偶数止匕时由弓I理2.3可知，xrn 2有n+1个根 J ,0,0, 971有n+2个根 cb 1,L , 02,其中n , n是一的两个根。满足下面条件：1 22 2 c1< 1< 2< 2<L < n < n < n < n <L < n 2<0 1212222注意到上面出现的所有多项式均只含有实根，且

12、由Pn, b, c,都是独立多项式，系数全为非负整数可知 xrn 2、brn 1所有的根均为互不相同的负实根(当c然xrn 2还有一个0根),所以系数也均为非负整数。又观察到 xrn 2、brn1在零 c点处变号的性质，可以得知 1的根应分别落在如下n+2个区间内:(, 1卜(1,2)L( n, n1卜(n 2,n 1) L(n 1,nZn 2,0)22 12 22这实际上就是前文所提到的引理 2.3的证明过程中得到的结论，而这种利用 根的交叉分布以及全实根函数在零点处变号性质的巧妙方法正是本文的核心方 法，利用这个思路，我们可以同理解决下面的问题。设n的n+2个根为 1, 2,L , n 2

13、由rn和xn 2在零点处变号的性质不难看出，rn xrn 2的根应落在如下n+2个区间内：(, 1)、( 1, 2)L ( n, n )、( n，n )L ( n1, n)、( n 2,0) 1212222n Xrn2此时是n+2次多项式，所以至此已得到我们所要证明的结论。Case 2 n为奇数止匕时由弓I理2.3可知，x72有n个根 1,L,n1,0，n1有n+1个根b. 1,L , n 1，其中-的两个根在n 1, n 3之间。酒足下面条件：c花2"1< 1< 2< 2<L < n 1< n 1 < n 3 < n 1<L &

14、lt; n 1 <0"2""2""2" "T由于这里的证明与之前完全相同，此处略去说明。n的根应分别落在如下n+1个区间内：(,1)、(1,2)L( n 1, n 1)、(n 3,n 1 ) L( n,n 1)、(n 1,0) 设n的n + 1个根为 1, 2,L , n 1n Xrn2的根应落在如下n+1个区间内：(, 1)、( 1, 2)L ( n1, n1)、( n3, n1)L ( n, n 1)、( n 1,0) "2" -2-2 n X7 2此时是n+1次多项式，所以至此已得到我们所要证明的结论。综上所述，定理1.2得证。结论经过一些尝试，我们明确了由 path和cycle衍生出的两种基本图 path-like graph、cycle-like graph的独立多项式性质。实际上，如果一个图不含有度超过 2 的点，那么它一定可以由无交的 path和cycle做并运算得到，也就是说对于 map 或一些特殊的图，如果能够解决三度点的问题，那么 map-like gr