分数团覆盖的零错误容量上界

形式陈述

设 $G$ 是有限非空混淆图， $\mathcal K(G)$ 为其全部非空团，包括单点团。给每个团 $K$ 赋非负权重 $z_K$ ，要求每个顶点被至少一单位权重覆盖：

\sum_{K\ni v}z_K\ge1\qquad\text{对每个 }v.

分数团覆盖数是线性规划

\overline\chi_f(G)= \min\left\{\sum_Kz_K:z_K\ge0,\ \sum_{K\ni v}z_K\ge1\right\}.

它也等于补图的分数着色数。对Shannon 零错误容量，有

\Theta(G)\le\overline\chi_f(G). \tag{1}

更强地，每份总权重为 $T$ 的可行覆盖都提供所有块长的证书

\alpha(G^{\boxtimes n})\le T^n. \tag{2}

这里只需一个可行覆盖就能给上界，不必先求出最优解。[1, §I]

直觉

一个团内的输入两两可能混淆，所以零错误码最多从这个团取一个点。如果每个顶点都已经被团覆盖了一次，那么把每个团“最多贡献一个码字”的限制按权重相加，就得到全局上界。

分数权重允许重复使用彼此重叠的团，每个只支付部分成本。这有时比把顶点分成整数个团更省，也更容易写出对称证书。

例子与边界

$C_5$ 的极大团就是五条边。每条边赋权 $1/2$ ，每个顶点恰被两条边包含，所以覆盖总量为1；总权重为 $5/2$ 。因此

\alpha(C_5^{\boxtimes n})\le(5/2)^n, \qquad\Theta(C_5)\le5/2.

整数团覆盖至少需要3个团：两条边最多覆盖4个顶点，第三个团不可少。因此分数化确实改善了3这一粗界。

不过 theta进一步把上界降到 $\sqrt5\approx2.2361$ ，而 $5/2=2.5$ 。一个证书方便检查，不代表它已经达到真实容量。

设 $I$ 是独立集。逐项交换有限求和，

\begin{aligned} |I|&\le\sum_{v\in I}\sum_{K\ni v}z_K\\ &=\sum_Kz_K|I\cap K|\\ &\le\sum_Kz_K=T. \end{aligned}

第一步使用每个被选顶点获得至少1的覆盖，最后一步使用独立集与任意团至多相交一点。不能把“一个输出对应的支持集合”以外的团排除掉：本页的图参数允许所有团，这一点将在反馈问题中形成区别。

若 $K_1,\ldots,K_n$ 都是 $G$ 的团，则 $K_1\times\cdots\times K_n$ 是 $G^{\boxtimes n}$ 的团：任意两个不同串，在每个坐标上都相等或相邻。

给这个乘积团权重 $z_{K_1}\cdots z_{K_n}$ 。某个顶点串 $(v_1,\ldots,v_n)$ 获得的覆盖量为

\prod_{i=1}^n\left(\sum_{K_i\ni v_i}z_{K_i}\right)\ge1,

而全部乘积团总权重为 $(\sum_Kz_K)^n=T^n$ 。对长码再应用一次计数，便得到式 (2)。这比只证明 $\alpha(G)\le T$ 多了关键一步：证书能随块长一起构造。

推论与应用

\overline\chi_f(G) =\max\left\{\sum_vw_v:w_v\ge0,\ \sum_{v\in K}w_v\le1\ \forall K\right\}.

对偶给每个顶点质量，限制任一团承载的总质量不超过1。它不是一般独立集的凸包：顶点质量可以同时分布在相邻点上。

在 $C_5$ 上令所有 $w_v=1/2$ ，每条边质量为1，所有单点团也满足约束，总质量为 $5/2$ 。原问题的边权 $1/2$ 与对偶的点权 $1/2$ 目标相同，因此双方都最优。还可把五条边的不等式相加，直接得 $2\sum_vw_v\le5$ 。

有时文献把这个对偶量记作 $\alpha^*(G)$ ，但“分数独立数”还可能指只用边约束的其他松弛。这里明确要求所有团的不等式；例如 $K_3$ 的三点各赋 $1/2$ 虽满足边约束，却违反整团质量至多1。

给出若干团及权重后，覆盖条件和总权重可直接检查；若只列出部分团，得到的最优覆盖仍是容量上界，但可能比使用全部团更松。

图可能有指数多个极大团。因此“这是LP”不表示已经有一个关于图顶点数的无条件多项式时间精确算法；还须处理约束或变量的生成问题。作为教学与证明工具，显式对称覆盖常比完整求最优更有用。

反馈容量也出现分数打包，但约束来自信道实际输出的支持超边，而非图的全部团。两份LP的数值在五边形信道中恰好相同，一般却不能因此互换。

参考资料

[1] László Lovász, On the Shannon Capacity of a Graph, 1979，§I：分数顶点打包、对偶团覆盖与 Shannon 上界。本文展开乘积覆盖证书与五边形原对偶计算。