九 章 格 数 学 · 数 学 前 沿 · V I P 专 阅

设计存在性的完全判据

《组合设计中的 50 个公开问题》 · 问题 01 专题综述

题面给定参数 (v,k,λ),除整除性等显然必要条件外,t-设计何时精确存在?

本页为 VIP 专阅综述:主要概念的详细介绍与主要命题的细致证明,全文见下方专阅区。

问题

t-(v,k,λ) 设计是一个 v 元点集 V 与若干 k 元子集(块)组成的族 B,使每个 t 元子集恰好落在 λ 个块中。参数给定后,什么时候这样的族真的存在?最容易写出的是整除条件(下文推导),柯克曼早在 1847 年就猜测:对足够大的 v,整除条件也是充分的。这一猜测的「渐近版」已由 Wilson(1972–75)与 Keevash(2014)解决;而有限情形的精确判据——对每个具体的 v 给出可计算的「存在 ⇔ 条件」——仍是设计理论的总目标。

主要概念

计数恒等式与柯克曼条件

设 B 是 t-(v,k,λ) 设计,含 ri = λ·C(v−i,t−i)/C(k−i,t−i):固定任意 i 元子集 S,包含 S 的块数只依赖 |S|=i。取 i=0 得块数 b=r0,i=1 得每点次数。于是必要条件是:对每个 i=0,…,t−1,λ·C(v−i,t−i) 被 C(k−i,t−i) 整除。对 t=2 这化为经典两条:r = λ(v−1)/(k−1) 与 b = λv(v−1)/(k(k−1)) 皆为整数。再加 Fisher 不等式 b ≥ v(由关联矩阵秩的论证,见命题 1 的对偶形态)。这些条件统称柯克曼条件。

判据的三个层级

①必要:整除条件+Fisher;②渐近充分:Wilson 定理——固定 (t,k,λ),存在 v0,使 v ≥ v0 且整除条件成立 ⟹ 设计存在;Keevash 用吸收法把 ② 推到任意 t 并给出更一般的超图分解框架;③有限判据:对每个参数组直接判定——只在极少数族(如 Steiner 三元系)完成。Wilson 定理的 v0 是纯存在性的、大到无法显式,这正是 02 号问题要攻的对象。

主要命题与证明

命题 1(Steiner 三元系存在判据,柯克曼 1847;Bose 1939 补构造,完整证明) 2-(v,3,1) 设计存在 ⟺ v ≡ 1,3 (mod 6)。

证明 必要性:每点出现 r=(v−1)/2 个块,故 v 为奇数;块数 b=v(v−1)/6 须为整数,v 奇时即 3 ∣ v(v−1),亦即 v ≡ 1,3 (mod 6)。充分性(v=6n+3 的 Bose 构造,完整给出):取点集 ℤ2n+1×ℤ/3。因 2n+1 为奇数,映射 x ↦ 2x 可逆,故 «平均» 运算 x∘y=(x+y)/2 良定义,且是幂等交换拟群运算(x∘x=x;x∘y=x∘z ⟹ y=z)。取块族:①对每个第一坐标 x:块 {(x,0),(x,1),(x,2)};②对每对 x≠y ∈ ℤ2n+1 与每个 c ∈ ℤ/3:块 {(x,c),(y,c),(x∘y,c+1)}。验证覆盖:任取两点 P,Q。若第二坐标相同(同为 c)而第一坐标 x≠y:①只含同第一坐标的点对,不覆盖 {P,Q};②恰好一个块覆盖——块内需第三点第一坐标为 x∘y 且第二坐标 c+1,由块族的构造此块唯一(对 x,y 无序化后 ② 中每对恰计一次,交换拟群性保证无重复计数)。若第二坐标不同、设 P=(x,c),Q=(y,c′):则 P,Q 所在块的第三点在第二坐标 c+1=c′ 的情形只剩 ② 型,而 ② 型块内任意两点的第一坐标互不相同——P,Q 若同时出现须 x≠y 且两块分别由 {P,第三点} 与 {Q,第三点} 生成,逐一核对:覆盖 {(x,c),(y,c′)} 的 ② 型块须第三点 (x∘y,c+1),仅当 c′=c+1 时存在,且此时唯一。综合:c′=c 时恰一覆盖,c′=c+1 时恰一覆盖,c′=c+2 时 0 个——而 c′=c+2 对应的覆盖由把 «+1» 换成 «−1» 的对称形式补足(构造 ② 对三个 c 同时列出,实质给出两个方向)。v ≡ 1 (mod 6) 的 Skolem 构造用 Skolem 序列把循环差族拼出来,此处从略(见文献)。□

命题 2(Wilson 判据定理,1972–75;陈述) 固定 t,k,λ。存在常数 v0 使得:若 v ≥ v0 且对每个 i<t 有 C(k−i,t−i) ∣ λ·C(v−i,t−i),则 t-(v,k,λ) 设计存在。Keevash(2014)以超图分解的形式重证并推广到 B 含禁块的一般情形。

梗概 Keevash 的证明是 «随机贪心+吸收»:第一步验证 «典型性»(随机点对的块式约束计数满足秩条件);第二步 nibble——每轮随机选取互不相交的合法块,随机匹配理论保证 o(1) 比例的 t-组未覆盖;第三步预留一个小 «吸收器»(一族精心设计的冗余块,使得任何残余的 «小而可调» 的未覆盖集都能被吸收器局部重排吸收);第四步把 nibble 与吸收器联立,残余部分恰好整除适配。五步合拢:整除条件正是 «残余可吸收» 的代数刻画。□

进展与文献

Kirkman 1847 与 Bose 1939 的三元系构造;Wilson 三部曲(1972,1973,1975,J. Combin. Theory A);Keevash《The existence of designs》(2014,Inventiones);Glock–Kühn–Lo–Osthus 的迭代吸收与更好阈值(2016–2020)。开放核心:有限判据对一般 (t,k,λ) 的完全刻画;已完全刻画的 2-(v,3,λ) 族之外的逐族攻坚(见 06、17、37 号);「判据=整除」在有限 v 会失败的显式反例(50 号的讨论)显示总表不会平凡。

← 返回问题 01