关于cycle-like-graph的独立多项式

关于cycle-like graph的独立多项式引言 独立多项式是组合数学中一个很重要的研究方向，它在染色问题、匹配问题等多个重要的问题中能起到至关重要的作用。但是，对于独立多项式的研究现在还并不完善。关于一些性质良好的图，我们希望能够明确的知道其独立多项式根的情况以及是否具有单峰性或log凹性，对此有很多数学家进行了不懈的尝试，但至今成果仍不足以令人满意，未解决的猜想还有很多。比如关于树以及二部图的独立多项式是否具有上述性质。本文将讨论一种特殊的图cycle-like graph是否具有上述的良好性质。这种图脱胎于1中介绍的path-like graph，是一种性质良好且具有一定代表意义的图，下面的讨论将是对1中结论的一个扩展。本文最终将会说明cycle-like graph仍然具有与path-like graph 相同的一个良好性质，即在特定条件下根全为实根，因此在该条件下它也是log凹、单峰的。为了开始证明上述结论，一些定义和引理是有必要的。设G =(V,E) 是点集为V，边集为E的图，Nv表示v及其邻点。U为V的一个子集，GU表示由VU生成的G的子图。称G中一组两两不相邻的点集为G的一个独立集，其大小定义为该点集所含点的个数。大小最大的独立集称作最大独立集，其大小设为(G)。接下来定义独立多项式I(G,x)如下。 其中表示大小为k的独立集的个数。称一个多项式 是log-concave的，如果其系数满足对于任意的i，1in-1，都有。称一个多项式是单峰的，如果其系数满足存在j，0jn，有。显然，满足log凹性的多项式一定也是单峰的。接下来在2中的结论是一个基础的结论，它将会十分有用：引理1.1 若多项式 ()的根全为实根，则数列是log-concave的，显然，也是log-concave的。有了这个引理，如果能够证明一个独立多项式的根全为实根，那么我们所希望的性质，log凹性与单峰性自然满足。接下来给出关于path-like graph以及cycle-like graph的一系列定义。我们把长度为n的-path记作P(t,n)=(V,E)，其中V=，E=| 显然，当t=2时，P(t,n)就是长度为n+1的path。若是一个图，G，U如上定义，v是G以外的一个点，那么定义G*(U，v)如下：V(G*(U，v)=Vv, E(G*(U，v)= u,v|uU。若对于的每一个点均作此处理，每一点对应一个相应的图G且与其中的点集U相连，即令G*(U，v)中的点v遍历的点集，得到的图记作(G,U)，那么此时我们可以给出1中path-like graph的定义：P(t,n)(G,U)。这里需要做几个说明。首先1中的结论是对于任意的t2,n0均成立的。但由于本文并未用到t=2之外的情况（也就是只用到了1中的第一个case），所以做约定如下:记I(P(2,n)(G,U),x)为，后文中出现的均为该独立多项式，这与1中的记号是相同的。类似的，我们引出本文定义的cycle-like graph：(G,U)。其中表示包含n个点的cycle。同样，我们也做约定如下：记I(G,U),x)仍为，后文中出现的均指代该多项式，为避免歧义特此说明。至此，可以给出本文的最终结果。定理1.2 设b(x)=I(G,x)，c(x)=I(GU,x)。若deg(b)=deg(c)+2，c|b(in Zx)，且b，c的根全为实根，则对于任意的n1，全为实根。值得注意的是，满足这样看似苛刻条件的图并不是很难找到，比如用完全图去掉一条边或去掉两条相临边得到的图作为G，全部点集V作为U，这个情形是满足上述条件的。关于这个定理的证明将会在第二章给出。为了证明定理1.2，这里给出两个在计算独立多项式时必不可少的基本引理。它们可以在2中找到。为了方便起见，我们将其归为一个引理。引理2.1 G1与G2是不相交的两个图，I(G1G2,x)=I(G1,x)*I(G2,x)。对于G中任意一点v，I(G,x)=I(G-v,x)+x*I(G- Nv,x)。 这两个引理十分直观，并不难证明，这里不过多的讨论了。接下来将会给出两个1中的结论。由于本文是1的一个扩展，所以下面给出的引理是我们进一步计算证明的关键。首先介绍一个符号。若|g成立，|g不成立，我们称恰好整除g，记作|g。引理2.2 若deg(b)=deg(c)+2，c|b(in Zx)，并且b，c的根全为实根，则 | |(/)通过的递推公式使用数学归纳法可得到这个结论。因为b，c的根均为实根，由这个引理可知，想要得到关于的根的结论，去掉上述次方的b，c后剩下的多项式将会是核心。在1中对于这个问题已有了相当完整的解答，下面的定理将会全面的给出这个核心多项式的性质。引理2.3 若deg(b)=deg(c)+2，c|b(in Zx)，并且b，c的根全为实根， 记=/(*)。则有对于任意的有 = 其中=+x，=+2xdeg()= n为偶数时 有n+1个根，有n+2个根，其中是的两个根。满足下面条件：0n为奇数时 有n个根，有n+1个根，其中的两个根在之间。满足下面条件：0上面这个引理是1中case 1的核心结论，可以看到这个引理已经包括了全为实根的结论了。不仅如此，它还给出了与它前两项的根之间的关系。这里需要指出，无论是这个引理的结论还是证明方法都极其重要。这个加强命题是通过数学归纳法得到证明的，在未知是否全为实根时，利用引理中后半段作为归纳假设可以推出的根落在哪些区间内，这个方法和结论都将在后面的证明中出现，到时再详细阐述。有了引理2.3，我们可以开始证明定理1.2了。首先由引理2.1可知显然是全实根的。时 由引理2.1有 再由引理2.2可得 所以，只需证明对于任意的满足根全为实根即可。这等价于证明对于任意的满足根全为实根。接下来我们分两种情况讨论。Case 1 n为偶数此时由引理2.3可知，有n+1个根，有n+2个根，其中是的两个根。满足下面条件：0注意到上面出现的所有多项式均只含有实根，且由，b，c，都是独立多项式，系数全为非负整数可知、所有的根均为互不相同的负实根（当然还有一个0根），所以系数也均为非负整数。又观察到、在零点处变号的性质，可以得知的根应分别落在如下n+2个区间内：这实际上就是前文所提到的引理2.3的证明过程中得到的结论，而这种利用根的交叉分布以及全实根函数在零点处变号性质的巧妙方法正是本文的核心方法，利用这个思路，我们可以同理解决下面的问题。设的n+2个根为 由和在零点处变号的性质不难看出，的根应落在如下n+2个区间内：此时是n+2次多项式，所以至此已得到我们所要证明的结论。Case 2 n为奇数此时由引理2.3可知，有n个根，有n+1个根，其中的两个根在之间。满足下面条件：0由于这里的证明与之前完全相同，此处略去说明。的根应分别落在如下n+1个区间内：设的n+1个根为 的根应落在如下n+1个区间内：此时是n+1次多项式，所以至此已得到我们所要证明的结论。综上所述，定理1.2得证。结论经过一些尝试，我们明确了由path和cycle衍生出的两种基本图path-like graph、cycle-like graph的独立多项式性质。实际上，如果一个图不含有度超过2的点，那么它一定可以由无交的path和cycle做并运算得到，也就是说对于map或一些特殊的图，如果能够解决三度点的问题，那么map-like graph或其他点度较低的图也将有类似的结论。不仅如此，在上面的证明中可以看出，对于cycle的处理是使用了引理2.1将