问题
覆盖数 C(v,k,t):v 元集上,取最少多少个 k 元子集(块),能使每个 t 元子集都含于某块。它是 «Steiner 系放不下时的最佳近似»:若整除条件满足且 Steiner t-设计存在,则 C = λ·C(v,t)/C(k,t)(λ=1 的理想值);否则要付 «冗余税»。问题分两层:渐近层(Rödl 定理已解决:C ~ C(v,t)/C(k,t))与精确层——对给定的 v mod 一组小数(如 v mod 6 时的 C(v,4,3))给出精确值。精确层至今只在部分同余类完成,Schönheim 下界与最优构造之间的缺口是主战场。《覆盖设计手册》(Colbourn–Dinitz 系)厚逾千页,精确值表仍大片空白。
主要概念
下界机器
Schönheim 下界:C(v,k,t) ≥ ⌈(v/k) · C(v−1,k−1,t−1)⌉(递归展开到底为 C(v−t+1, k−t+1, 1) = ⌈(v−t+1)/(k−t+1)⌉)。直观:固定一点 x,含 x 的块删去 x 后是 (v−1,k−1,t−1) 覆盖;每点至少被 «某数目» 的块覆盖。LP/分数下界:把 «每块权 ≤1、每 t-组被权 ≥1» 的分数覆盖的对偶写成线性规划,其值(可显式计算)常比 Schönheim 更强。计数下界:t-组共 C(v,t) 个、每块盖 C(k,t) 个 ⟹ C ≥ C(v,t)/C(k,t)(平凡但同余性质重要)。
构造侧
构造的上界来源三类:①截断:把 Steiner/已知设计删点删块(例如从 C(v+1,k,t) 得 C(v,k,t) ≤ …);②递归拼接:用小覆盖做 «局部模板»、大集做 «全局骨架»;③逐类攻坚:固定 (k,t)(如 (4,3)),对每个 v mod 模数 M 逐一确定精确值——这是 «C(v,4,3) 工程» 的做法。
主要命题与证明
命题 1(Schönheim 下界,1964,完整证明) C(v,k,t) ≥ ⌈(v/k)·C(v−1,k−1,t−1)⌉。
证明 设覆盖族含 b 个块。对每点 x,设 d(x) 为含 x 的块数。删块中点 x:族 {B∖{x} : x ∈ B} 是 (⟨v−1⟩,k−1,t−1) 覆盖——因为任何 (t−1)-组 S 加上 x 是 t-组,被某块 B ⊇ S∪{x} 覆盖。故 d(x) ≥ C(v−1,k−1,t−1) 对每点 x 成立。计数 incidences:b·k = Σx d(x) ≥ v·C(v−1,k−1,t−1),即 b ≥ (v/k)·C(v−1,k−1,t−1);b 为整数,取上取整。□
命题 2(Rödl 定理,1985;陈述) 固定 k,t。当 v→∞,C(v,k,t) = (1+o(1))·C(v,t)/C(k,t)——渐近意义下 «冗余税» 消失。证明即 02 号命题 1 的 nibble 机器(对偶使用:覆盖 = 匹配的补)。
说明 注意 o(1) 项的有效估计依赖参数;对精确值工程它只提供 «极限方向»,同余类的 «最后一遍整数修正» 仍须逐类手算。□
命题 3(C(v,4,3) 的样板;陈述) 固定 k=4,t=3。Schönheim 展开给 C(v,4,3) ≥ ⌈v/4·⌈(v−1)/3·⌈(v−2)/2⌉⌉⌉。当 SQS(v)(即 3-(v,4,1))存在(v ≡ 2,4 mod 6)时下界取等:C = C(v,3)/4 = v(v−1)(v−2)/24。其余同余类(v ≡ 0,1,3,5 mod 6)的精确值是 «最后一遍修正» 攻坚的经典战场:每个类对应一组 «最少冗余块数» 的确定问题。
说明 SQS 存在性(Hanani 定理)见 17 号命题 1 的同一台机器;这里只使用其结论。□
进展与文献
Schönheim 1964;Erdős–Hanani 猜想与 Rödl 定理(1985);Mills 对 C(v,4,3)、C(v,5,4) 的系列精确值;Colbourn–Dinitz《Handbook of Combinatorial Designs》的覆盖数表。开放核心:C(v,5,4)、C(v,6,5) 族的同余类清单(与 07 号的 Turán 型对偶问题成对);分数 LP 下界与 Schönheim 型下界的统一;«覆盖数表» 的算法化自动填充(SAT 引擎已在小参数建功,见 25–29 号的引擎复用)。