图论多项式(Graph Polynomials)

  在 Weighted First-Order Model Counting (WFOMC) 的题目中经常用到图论多项式，所以学了一些东西，整理一下。

色多项式(Chromatic Polynomial)

  这应该算是最简单的一种图论多项式了。

  我们用 $G = (V,E)$ 表示一个无向图，其中 $|V| = n$。然后我们用 $D = (V,E)$ 表示一个有向图。
  我们可以定义各种各样的色多项式：

• $\chi_G(x)$ 表示无向图 $G$ 的色多项式，当 $x$ 为正整数时，它表示用 $x$ 种颜色给点染色、使得任意一条边的两点颜色不同的方案数；
• $\bar \chi_D(x)$ 表示有向图 $D$ 的非严格色多项式，当 $x$ 为正整数时，它表示用 $x$ 种颜色给点染色、使得若有边 $u \to v$ 则 $color(u) \le color(v)$ 的方案数；
• $\chi_D(x)$ 表示有向图 $D$ 的严格色多项式，当 $x$ 为正整数时，它表示用 $x$ 种颜色给点染色、使得若有边 $u \to v$ 则 $color(u) < color(v)$ 的方案数。

  以下这几个不算是多项式，但也是很有用的概念：

• $\chi^*_G(x)$ 表示 $G$ 的精确染色方案数（英文喜欢称为 surjective 满射），当 $x$ 为正整数时，它表示恰好用 $x$ 种颜色给点染色（即颜色 $1, \cdots, x$ 每种至少被用一次）、使得任意一条边的两点颜色不同的方案数；
• $\bar \chi^*_D(x)$ 表示有向图 $D$ 的精确非严格染色方案数，当 $x$ 为正整数时，它表示恰好用 $x$ 种颜色给点染色、使得若有边 $u \to v$ 则 $color(u) \le color(v)$ 的方案数；
• $\chi^*_D(x)$ 表示有向图 $D$ 的精确严格染色方案数，当 $x$ 为正整数时，它表示恰好用 $x$ 种颜色给点染色、使得若有边 $u \to v$ 则 $color(u) < color(v)$ 的方案数。

  为什么精确的这几个不是多项式呢？因为 $x > n$ 时它们的值都为 $0$，这定义不出有限度数的多项式。那一开始的三个为什么是有限度数的呢？因为显然有：

Lemma 1. (精确染色方案数和色多项式的关系)

$$\begin{aligned} \chi(x) &= \sum_{i=1}^n \binom{x}{i} \chi^*(i) \\ &= \sum_{i=1}^n \frac{x(x-1) \cdots (x-i+1)}{i!} \chi^*(i). \end{aligned} \tag{1}$$

  这个就可以用来说明色多项式都是关于 $x$ 的 $n$ 次多项式，并且 $n$ 次项的系数是 $\frac{\chi^*(n)}{n!}$。

  色多项式的美妙之处在于它在负数点处的取值。负数点值的意义并不显然，但是能表示重要的组合意义。举两个例子。

有向图色多项式的负数点

Lemma 2. 记 $acyc(D)$ 表示 $D$ 缩环之后得到的 DAG，记 $|V(acyc(D))|$ 表示 $acyc(D)$ 的点数。对于任意 $x \in \mathbb R$，

$$\begin{aligned} \chi_D(x) &= \begin{cases} (-1)^n \bar \chi_D(-x), & D \text{ is acyclic,} \\ 0, & \text{otherwise,} \end{cases} \\ \bar \chi_D(x) &= (-1)^{|V(acyc(D))|} \chi_{acyc(D)}(-x). \end{aligned}$$

  也就是说，如果 $D$ 是个 DAG，那么负数点的意义就是把严格转化为非严格、把非严格转化为严格；而如果 $D$ 是有环的，那么从非严格转化为严格的过程会缩环，从严格转化为非严格的过程会过滤掉有环图。

  证明至少有两种。以下我们只需证明 $D$ 为 DAG 时的情况就好了。

• 证明 1：

  来自 [AB20]，从几何来理解。
  把颜色序列 $color(1), \cdots color(n)$ 理解为 $n$ 维空间的一个点。当只允许 $color(i) \in \{0,1\}$ 时，记所有可行点组成的多面体为 $\Pi$，如果允许 $color(i) \in \{0,1,\cdots,x\}$，则该多面体变成 $x\Pi$（即边界的每个点每一维坐标乘上 $x$）。
  我们可以发现 $\chi_D(x)$ 表示 $(x+1)\Pi$ 的内部整点（不含边界）数量（注意这只在 $D$ 为 DAG 时成立），而 $\bar \chi_D(x)$ 表示 $(x-1)\Pi$ 的整点数量。记 $E_{\Pi}$ 表示 $\Pi$ 的 Ehrhart's Polynomial（即 $E_{\Pi}(x)$ 表示 $x\Pi$ 的整点数量）。关于 Ehrhart's Polynomial 有一个性质是：

$$E_{\Pi}(-x) = (-1)^n (x\Pi\text{ 的内部整点数}).$$

  因此

$$\chi_D(x) = (-1)^n E_{\Pi}(-x-1) = (-1)^n \bar\chi_D(-x).$$

• 证明 2：

  来自 [Sta70]，纯组合意义证明。所以几乎被我不看论文自己脑补出来了
  我们先给 $D$ 的节点重新标号，使得如果有边 $u \to v$ 那么 $u<v$。我们知道这样的标号方法肯定存在，而且不影响 $\chi_D(x)$ 和 $\bar\chi_D(x)$，因为它们与点标号无关。这样做是为了方便下面使用拓扑序。
  下面介绍一种非严格染色方案到拓扑序的映射：每次在入度为 $0$ 的点里找颜色最小的，如果有多个点就选标号最小的点，执行 $n$ 次就得到了一个拓扑序。
  那么对于一个拓扑序 $t_1, \cdots, t_n$，它包含的非严格染色方案如下：

$$\forall i>1, \begin{cases} color(t_{i-1}) \le color(t_i), & t_{i-1} < t_i, \\ color(t_{i-1}) < color(t_i), & t_{i-1} > t_i. \end{cases}$$

  同理，定义一种严格染色方案到拓扑序的映射：每次在入度为 $0$ 的点里找颜色最小的，如果有多个点就选标号最大的点，执行 $n$ 次就得到了一个拓扑序。那么对于一个拓扑序 $t_1, \cdots, t_n$，它包含的严格染色方案如下：

$$\forall i>1, \begin{cases} color(t_{i-1}) < color(t_i), & t_{i-1} < t_i, \\ color(t_{i-1}) \le color(t_i), & t_{i-1} > t_i. \end{cases}$$

  记 $w_s$ 表示有 $s$ 对相邻元素满足 $t_{i-1}<t_i$ 的拓扑序数量，则有

$$\begin{aligned} \chi_D(x) &= \sum_{s=0}^{n-1} w_s \binom{x+s}{n}, \\ \bar\chi_D(x) &= \sum_{s=0}^{n-1} w_s \binom{x-s+n-1}{n}. \end{aligned}$$

  因此有

$$\bar \chi_D(-x) = (-1)^n \chi_D(x).$$

无向图色多项式的负数点

  关键就是要发现 $\chi_G(x)$ 等价于先给 $G$ 无环定向然后给点染色使得如果有边从 $u$ 到 $v$ 那么 $u$ 的颜色小于 $v$ 的颜色的方案数，即

$$\chi_G(x) = \sum_{D \text{ 是 }G\text{ 的无环定向 }} \chi_D(x).$$

  比较容易理解，因为无向图每一种染色方案都唯一对应一种无环定向方案，枚举每一种无环定向然后严格染色就可以得到所有原来的染色方案。
  所以负数点的意义，结合 Lemma 2 就是

$$\chi_G(-x) = \sum_{D \text{ 是 }G\text{ 的无环定向 }} \bar \chi_D(x). \tag{2}$$

应用——无向图的无环定向(Acyclic Orientation)

  记 $a_G$ 表示给定一个 $n$ 个点的无向图 $G$，给每条边定向使得该图无环的方案数。

Lemma 3. $a_G = (-1)^n \chi_G(-1).$

  证明多种多样，甚至有用拟阵来证的（wiki 给的文章就是），还有胡说八道的（比如 [EG21]）……

• 证明 1：

  就给上面的 (2) 式代入 $x=1$ 就好了，对于任何有向图都有 $\bar \chi_D(1) = 1$，于是得出结论。

• 证明 2：

  来自 [Sta73]，不想证明直接引用的话就引用这篇。
  思路本质上跟证明 1 差不多，只不过他没有用到有向图色多项式，而是定义了一个 $\bar \chi_G(x)$ 表示先给 $G$ 无环定向然后给点染色使得如果有边从 $u$ 到 $v$ 那么 $u$ 的颜色小于等于 $v$ 的颜色的方案数，然后再用结构归纳法证了一个关系：

$$\bar\chi_G(x) = (-1)^n \chi_G(-x).$$

  最后令 $x=1$，$\bar\chi_G(x)$ 的意义就变成了无环定向数，于是就得出了 Lemma 3。

  这个结构归纳证明是挺美妙的，只不过现在懂了无向图色多项式和有向图色多项式的关系之后，就会觉得这个只是在兜圈子了。

• 证明 3：

  参考 [EG21] 自己脑补的组合意义证明。
  [EG21] 的 8.3、8.4 节讲的就是 acyclic orientation，给了一个长长的生成函数证明，但很可惜是错的，它提出的“等价类”的概念并不 well-defined。
  不过它最后的式子 (8.26) 倒是很有启发意义——通过染色方案数的容斥来得到定向方案数。

  回顾 Lemma 1，如果代入 $x=-1$，会得到

$$\chi_G(-1) = \sum_{i=1}^n (-1)^i \chi^*_G(i).$$

  所以 Lemma 3 就变成了

$$a_G = \sum_{i=1}^n (-1)^{n+i} \chi^*_G(i). \tag{3}$$

  这东西看着就很容斥。因为一种精确染色方案可以唯一确定一个定向方案（比如规定边的方向是从小颜色连向大颜色），所以我们证明，每一种定向方案所对应的（精确严格）染色方案中，只有一种能留下来。
  Recall 上面 Lemma 2 那儿用到的其中一种有向图染色方案到拓扑序的映射：不妨设 $D$ 是个有标号图（没标号随便标一个即可），每次在入度为 $0$ 的点里选一个颜色最小的，如果有多个点就选择标号最小的。执行 $n$ 次，这就得到了一个拓扑序。
  在一个定向方案的所有（精确严格）染色方案中，我们保留拓扑序字典序最大的那个，这个染色方案是唯一的，且要使用所有 $n$ 种颜色（即在 (3) 式右边系数是 $1$）。其余的精确染色方案必能两两对应，且正负相消。假设 $\sigma^*$ 是拓扑序最大的染色方案，$\sigma^1$ 是某个拓扑序非最大的染色方案，它们的拓扑序分别为：

$$\begin{aligned} topo(\sigma^*) = \cdots, &i, \cdots, \cdots \\ topo(\sigma^1) = \cdots, &j, \cdots, i, \cdots \end{aligned}$$

  其中 $j$ 所在的位置是 $topo(\sigma^*)$ 与 $topo(\sigma^1)$ 从左往右第一个不同的位置。

  如果 $\sigma^1_i$ 在 $\sigma^1$ 里是唯一的，则构造 $\sigma^2$ 如下：先令 $\sigma^2 := \sigma^1$，然后把排在 $i$ 后面的所有点的颜色减 $1$，再给 $\sigma^2_i$ 减 $1$ 并将 $i$ 移到恰当的位置。如果 $\sigma^1_i$ 不唯一，则构造 $\sigma^2$ 如下：先令 $\sigma^2 := \sigma^1$，然后把颜色大于 $\sigma^2_i$ 的点的颜色都加 $1$，再给 $\sigma^2_i$ 加 $1$ 并将 $i$ 移到恰当的位置。
  可以发现，$\sigma^2$ 经过这套变换也会变成 $\sigma^1$，并且一个精确染色经过变换后仍然是最多使用 $n$ 种颜色的精确染色，所以所有非字典序最大的染色方案是两两对应的。并且，$\sigma^1$ 和 $\sigma^2$ 的颜色数正好差 $1$，所以它们正负相消。
  因此 (3) 式右边每一个定向方案只有一个系数为 $1$ 的精确染色被保留，所以得到 $a_G$。

Tutte 多项式(Tutte Polynomial)

记 $T_G(x,y)$ 表示 $G$ 的 Tutte 多项式，它的其中一种定义是这样的：

$$T_G(x,y) = \sum_{A \subseteq E} (x-1)^{cc(A) - cc(E)} (y-1)^{cc(A) + |A| - n},$$

其中 $cc(A)$ 表示图 $(V,A)$ 的连通块数。这里要求 $0^0 = 1$。

  Tutte 多项式堪称无向图的万金油，它实在有太多的意义（多数抄自 wiki，少数抄自网上课件）：

• $T_G(2,1)$ 表示 $G$ 有多少子图是森林；
  • 因为 $x-1 = 1$ 所以 $(x-1)^{cc(A)-cc(E)}$ 这一项就没了，而 $y-1 = 0$ 就要求子图必须满足 $cc(A)+|A|-n=0$，所以是森林。
• $T_G(1,1)$ 表示 $G$ 有多少子图是生成森林（即连通块的数量与原图一致），当 $G$ 连通时表示 $G$ 的生成树数量；
  • 同理，相比森林，多要求了一个 $cc(A)=cc(E)$。
• $T_G(1,2)$ 表示 $G$ 的生成子图数量；
  • 只要求 $cc(A)=cc(E)$。
• ……

  负数点的意义也很神奇：

• $(-1)^{n-cc(E)} x^{cc(E)} T_G(1-x,0)$ 是 $G$ 的色多项式 $\chi_G(x)$；
  • 证明就是左边边展开之后会变成 $\sum_{A \subseteq E} x^{cc(A)}(-1)^{|A|}$，它就是容斥得出染色方案数。
• $T_G(2,0)$ 表示 $G$ 的无环定向方案数；
  • 上式代入 $x=-1$ 即得到。
• $T_G(0,2)$ 表示 $G$ 的强连通定向方案数；
• $T_G(1,0)$ 表示 $G$ 的无环定向且只有一个起点的方案数（无论起点是谁），如果 $G$ 不连通则是各个连通块的方案数乘起来；
• $T_G(0,0)$ 判断 $G$ 是否有边；
• $T_G(-1,0)$ 判断 $G$ 是否是二分图；
• $T_G(0,-1)$ 判断 $G$ 是否是欧拉图（存在欧拉回路）；
• ……

  复平面点的意义也很神奇，但我不会（

  所以显然“任意给定一个无向图，求其 Tutte 多项式”或者“任意给定一个无向图和一个平面点 $(x,y)$，求其 Tutte 多项式在 $(x,y)$ 处的值”这样的问题都是 $\mathsf{\sharp P}$-hard 甚至是 complete 的。

B-Polynomial

  这个是 [AB20] 提出的 Tutte 多项式在有向图上的扩展：

$$B_D(q,y,z) = \sum_{f: V \to [q]} y^{|f^>|} z^{|f^<|},$$

其中 $f$ 枚举的是一种点染色方案，$f^> = \{(x,y) | (x,y) \in E \land f(x) < f(y)\}$，$f^< = \{(x,y) | (x,y) \in E \land f(x) > f(y)\}$。（我沿用了作者的箭头符号，是有点奇怪的）

  一些意义：

• $[y^{|E|}]B_D(q,y,1)$ 是 $D$ 的严格色多项式 $\chi_D(q)$；
• $B_D(q,1,0)$ 是 $D$ 的非严格色多项式 $\bar\chi_D(q)$；
• ……

Reference

• [AB20] Jordan Awan and Olivier Bernardi. Tutte polynomials for directed graphs. In Journal of Combinatorial Theory, Series B 2020.
• [Sta70] Richard P. Stanley. A chromatic-like polynomial for ordered sets. In Proc. 2nd Chapel Hill Conf. on Combinatorial Mathematics and Its Applications 1970.
• [Sta73] Richard P. Stanley. Acyclic Orientations of Graphs. In Discrete Mathematics 1973.
• [EG21] Ömer Eğecioğlu, and Adriano M. Garsia. Lessons in Enumerative Combinatorics 2021.