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

可解设计存在性

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

题面给定 (v,k,λ),可解(柯克曼型)设计的个数有公式吗?

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

问题

可解设计(12 号:块可分平行类)的存在性渐近已入 Keevash 框架;本问题问 «计数与显式构造»:给定的 (v,k,λ) 可解设计有几个(公式)?显式构造的算法有多高效?它是 «从柯克曼到 Keevash» 这条线的设计教育接口:柯克曼三元系是最著名的 «课堂级» 设计(十五女学生),而现代理论(吸收法)尚未给出它的 «计数公式» 与 «高效构造»——这条断层恰是教学与研究的天然桥梁。

主要概念

计数的 «类骨架» 障碍

不可解设计的计数(40 号)的主项由 «随机贪心» 主导;可解设计要求 «类骨架»(平行类的划分)—— «先排类、再填块» 的两步计数使 «主项» 需要新的变分:类的 «结构熵» 与块的 «填充熵» 的联合优化。目前连 «可解 STS(v) 的个数» 的主项公式都没有(不可解 STS 的主项已知)。

显式构造的 «可教性»

柯克曼三元系的 «教材构造»(starter + 平移)覆盖所有 v ≡ 3 (mod 6)——这是设计理论里罕见的 «完全显式且可教» 的族。«可教性» 的推广(可解 SQS、可解 2-(v,k,λ))是 «设计教育» 的实际需求:每多一个 «可教族»,课程就多一座桥。

主要命题与证明

命题 1(可解 STS 的存在下界,完整推导骨架) 可解 STS(v)(KTS(v))的个数 ≥ «显式构造族的个数»:starter 构造给 «至少 exp(c v log v)» 量级的下界(每个 «合法 starter» 生成一族;合法 starter 的计数由 «差覆盖» 的组合学给出)。

骨架 starter = «差覆盖对集»:(v−1)/2 对 {xi,yi},差 ±(xi−yi) 取遍非零元。合法 starter 的个数 = «1-因子分解» 型计数(差集的 «完美配对» 数)——其计数本身是开放问题(与 18 号 P1F 的计数同族),«下界» 来自 «贪心配对的存在性»。□

命题 2(不可解与可解的主项比值;陈述) «可解设计占设计的比例» 是开问题:直觉 «可解性是 codimension 型约束 ⟹ 比例 → 0»,但目前没有 «可解设计的上界» 技术把它定量——«类骨架» 的计数理论是缺口本体。

说明 这一 «比例» 问题在 «图因子分解» 侧已有对应(«随机图可 1-因子分解» 的阈值理论)——移植的候选工具现成,缺的是 «设计的类结构» 的翻译。□

命题 3(教学接口;陈述) 可解设计的 «可教族» 清单:KTS(v)(starter 机器,12 号命题 2)、Kirkman 四元系的部分族、Room 方(47 号)的循环族——每族的 «构造证明» 都是一堂 «组合工程» 课。«从柯克曼到 Keevash» 的课程线(构造 → 整除 → 吸收)已被证明是设计理论教学的可行框架。

说明 本问题是 «纯理论问题» 与 «教学工程» 的复合体——设计理论中少见的 «双重身份» 开放题。□

进展与文献

Ray-Chaudhuri–Wilson 1971;Keevash 2014(存在性);与 12、18、40、47 号的交叉文献;设计教学侧的 «柯克曼» 文献(Cummins 等)。开放核心:可解设计的主项计数;«比例» 问题的定量化;可教族的扩张。

← 返回问题 46