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

完备设计定理的显式化与算法化

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

题面Keevash 2014 证明整除条件加 v 充分大则 t-设计存在——能否给出有效的 v 阈值与多项式时间的构造算法?

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

问题

Keevash 2014 年证明了设计存在性的完备渐近判据(01 号命题 2),但证明是 «存在性论证»:阈值 v0 不可显式、构造过程依赖非构造性的选择。本问题问两件事:①给出有效的 v0(哪怕天文数字,只要可写下来);②给出多项式时间的构造算法(输出显式的设计,而非仅证明其存在)。

主要概念

吸收法与迭代吸收

吸收法的骨架是 «近似+修正»:随机贪心(nibble)先覆盖几乎全部,剩下的 «残余» 由预留的吸收器修正。修正能力的关键是可调性:吸收器是一族带冗余的块,对任何 «足够小且整除适配» 的残余需求 L,都能在吸收器内局部交换块而恰好产出 L。Glock–Kühn–Lo–Osthus 的迭代吸收把 «一次修正» 升级为 «分层修正»:按块规模分层,逐层吸收,使阈值从 «巨大» 压到 «指数级但仍巨大»——存在性有效化迈出实质一步,但离 «可计算» 仍远。

算法化的三道坎

①nibble 是随机的——去随机化需要 «伪随机替代»(典型性条件的显式验证);②吸收器的构造目前依赖存在性引理(先证吸收器存在再保留它)——显式构造吸收器是算法化的真正瓶颈;③输出规模:块数 b = λ·C(v,t)/C(k,t) 本身是 vt 级,故 «多项式时间» 指输出多项式时间(vt 级已是输出下界)。

主要命题与证明

命题 1(Rödl 定理,1985,即爱尔德什–哈纳尼猜想;陈述+架构) 固定 k,t。存在部分 t-(v,k,1) 族覆盖 V 的至少 (1−o(1)) 比例的 t-子集,且族中块互不相同。

梗概 把 «未覆盖的 t-子集» 与 «可用块» 组织成超图 H:顶点是 t-子集,边是一个 k-块所含的全部 t-子集。求 H 的几乎完美匹配:每轮均匀随机选一条边(块),删去其覆盖的顶点。Pippenger–Spencer 的超图匹配定理(码长条件:任何小顶点集的 «邻域交互» 有界)保证可执行 «许多轮»,每轮残余比例乘以 (1−δ);k,t 固定时残余比例指数衰减到 0。□

命题 2(Keevash 主定理的五步架构) 整除条件成立且 v 充分大时 t-设计存在。证明分五步:①典型性验证(显式秩条件);②nibble 得 (1−ε) 覆盖;③残余结构 L 的 «整除适配» 分析(残余恰落在吸收器可调的陪集上);④吸收器重排产出 L;⑤参数一致性闭合。每一步都是非构造性的:③④ 需要 «先证存在再保留»。

梗概 ④ 的机制值得细看:吸收器本质是一个 «万能模板»——它同时包含 «用块 A 换块 B» 的所有局部重排轨道。整除条件保证残余需求 L 的 «类型向量» 落在模板的类型格之内,格上的生成元对应模板的重排轨道;由格的生成性,L 可写成生成元的非负组合,逐个执行即得。□

命题 3(算法化现状,2021–2023) 对固定参数 (t,k,λ):随机多项式时间构造已实现(Kang–Kelly–Kühn–Methuku–Osthus 等的算法化吸收:把典型性改为显式验证、吸收器改为 «可计算保留»);确定性构造与有效 v0 阈值仍未得到。特别地,t=4,5 的任意大显式构造已是可实现的工程目标。

现状说明 算法化的核心替换有两处:nibble 的随机轮被 «伪随机分块» 替代(按格点分割点集、显式验证局部密度);吸收器的 «先证存在» 被 «显式小模板» 替代(对固定 (t,k,λ),模板可穷举搜索得到)。这两处替换在小参数可行,一般参数的模板搜索本身仍超多项式。□

进展与文献

Rödl《On a packing and covering problem》(1985);Keevash《Counting designs》(2018,给出计数版);Glock–Kühn–Lo–Osthus 的迭代吸收系列;Kang–Kelly–Kühn–Methuku–Osthus 的算法化设计(2021–2023)。开放核心:确定性多项式构造(与 48 号 «设计的算法复杂性» 互为表里);t≥6 的任何显式构造族(与 03 号衔接);有效阈值的显式上界(哪怕 2↑↑v 型)。

← 返回问题 02