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

大集合 LS(3,4,n)

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

题面3-(n,4,1)(Steiner 四元系)的大集合存在吗?

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

问题

大集合 LS(t,k,n):把全部 t-子集(共 C(n,t) 个)划分成 «每块 k 点、构成 S(t,k,n) 设计» 的不相交部分——«设计的铺满»。2-(n,3,1) 的大集合(把全部三元组划分成互不相交的 Steiner 三元系)已由陆家羲(1983–84)与 Teirlinck 独立解决——陆家羲的大集合定理是中国组合数学的世纪成就(其在世时只发出一部分,身后补齐)。本问题:3-(n,4,1)(Steiner 四元系)的大集合存在吗?t≥3 的 «大集合谱» 几乎空白(只有零星 n),这是以中国人命名的问题谱系的延续。

主要概念

大集合的整除与 «设计的设计»

LS(2,3,n) 存在 ⟺ C(n,3) 被 C(n,2)/3 除得尽(每个 STS 占 C(n,2)/3 块)⟺ n ≡ 1,3 (mod 6) 且 n≠7——陆家羲–Teirlinck 定理给出完全判据(整除条件的充分性在 «大集合» 这一层成立)。t≥3:LS(3,4,n) 需 C(n,3) 被 C(n,2)/4·… 的整除链,且 «每层是一个 SQS» 的 «设计之设计» 结构使构造难度跳档。

陆家羲的机器

陆的证明是 «分同余类的递归构造»:从 «初等大集合»(小 n)出发,用 «框架»(frame)与 «补全» 技术逐级放大;Teirlinck 的独立证明走 «群作用» 路线。两条路线的 «t≥3 版» 都需要 «SQS 框架»——这是当前缺口。

主要命题与证明

命题 1(LS(2,3,n) 的整除必要条件,完整证明) LS(2,3,n) 存在 ⟹ n ≡ 1,3 (mod 6) 且 n ≠ 7(n ≥ 3)。

证明 大集合把 C(n,3) 个三元组划分为若干互不相交的 STS(n)。每个 STS(n) 的块数 b = n(n−1)/6,故部分数 = C(n,3)/b = [n(n−1)(n−2)/6]/[n(n−1)/6] = n−2——整数恒成立,计数层面无新增约束。因此必要条件全部来自 «每个部分本身是 STS»:由 STS 判据(01 号命题 1),n ≡ 1,3 (mod 6);再加上不相交性的可行:n=7 时 STS(7) 唯一(Fano 平面),两个部分必相交,无法铺满,排除。□

命题 2(陆家羲–Teirlinck 定理,1983–87;陈述) 对一切 n ≡ 1,3 (mod 6)、n ≥ 9,存在 LS(2,3,n)(互不相交的 STS(n) 恰好 n−2 个铺满全部三元组)。证明是分同余类的递归构造大工程。

说明 陆家羲的六篇论文(1983《Discrete Mathematics》刊出前四篇,身后 1984–89 补齐)与 Teirlinck 的独立证明共同闭合此题——«整除 ⟺ 存在» 在大集合层面对 t=2 完全成立,反衬 t≥3 的空白。□

命题 3(t≥3 的零星与空白;陈述) LS(3,4,n):已知零星(小 n 的计算构造与 «n ≡ 2,4 (mod 6) 且更大整除» 的候选参数);一般判据、连 «渐近存在»(Keevash 框架的大集合版)都未建立。t≥4 几乎全空白。

说明 «Keevash 的大集合版» 需要把吸收机器同时用于 «设计与设计之间的不相交铺满»—— «两层吸收» 是当前的理论瓶颈。□

进展与文献

陆家羲《可分离平衡不完全区组设计的存在性》系列与《Discrete Mathematics》六篇;Teirlinck 1987 的大集合工作;Colbourn–Dinitz《Handbook》的大集合章。开放核心:LS(3,4,n) 的判据;«两层吸收» 的理论;t≥4 谱系。

← 返回问题 37