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

弗兰克尔并闭集猜想

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

题面有限的并闭集族(族中任两集之并仍在族中)必有一元素出现在至少一半的集合里吗?

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

问题

并闭集族(union-closed family):有限集族 𝓕 满足 A,B ∈ 𝓕 ⟹ A∪B ∈ 𝓕(通常还设 𝓕 非空、且不含空集——含空集时平凡化)。弗兰克尔猜想(1979):𝓕 中必有一元素属于至少 |𝓕|/2 个集合。Polymath 社区曾组织攻坚未果;Gilmer 2022 年的 «熵+递归» 方法给出常数下界(绝对口径 (3−√5)/2≈0.382,其比值型变体推到约 0.61 量级),距 1/2 仍有关键一步。若猜想为真,最简证明也许藏在交换代数(Stanley 的深度方法)里。

主要概念

并闭集与「单元素提升」

并闭族的基本操作:«单元素提升»——把元素 x 加入族中不含它的集合。Poonen 的定理:弗兰克尔猜想等价于 «每个并闭族都有 «丰富» 的 2-生成子结构»(可只对 «每元素恰属两个集合» 的极小族证明)——把无穷谱压缩到 «覆盖率恰 1/2 的门槛» 附近。这个 «归约到 2-覆盖» 是理论侧最重要的结构性进展。

熵方法

Gilmer 的机器:把并闭族与 «随机并» 的熵联系起来:取 𝓕 上的均匀随机集 A,B,并闭性给 A∪B ∈ 𝓕;熵不等式(H(A∪B) ≥ …)+ «逐元素覆盖率的调和平均» 论证给出 «某元素覆盖率 ≥ (3−√5)/2 ≈ 0.382» 型下界——距 1/2 的缺口就是 «熵方法的天花板»,突破它需要 «非熵» 的新思想。

主要命题与证明

命题 1(最小反例的结构;陈述) 若反例存在,可取 «极小» 反例满足:族大小为偶数、每元素覆盖率恰低于 1/2、且 x∈𝓕 ⟹ x∪{y}∈𝓕 型 «单元素提升» 生成整族。Poonen 归约定理(1992):弗兰克尔猜想 ⟺ 每个并闭族含 «某元素恰属两个集合» 型丰富子结构。

说明 归约把 «一般族» 的搜索压到 «每元素覆盖率 ∈ {1/2, 1/3, …}» 的离散门槛——当前全部计算验证(族大小 ≤ 50)都通过,但 «极小反例» 的存在性没有任何理论排除。□

命题 2(Gilmer 熵下界,2022;陈述+机制) 每个有限并闭族存在元素覆盖率 ≥ (3−√5)/2 ≈ 0.382(黄金分割相关常数;其 «归一化变体» 经后续改良推到约 0.61 量级)。机制:随机并的熵链 + 覆盖率的 «傅里叶式» 分解。

说明 «0.382 → 0.5» 的最后一步:熵方法的结构极限在 (3−√5)/2(黄金分割的补数),突破需要 «超越熵» 的组合代数工具——这正是 «Stanley 深度方法» 被寄予厚望的原因:并闭族的 «序复形» 的深度不等式与覆盖率之间有形式化的对应。□

命题 3(交换代数的对应;陈述) 并闭族 𝓕 ↔ 单调序理想 Δ(𝓕)(面复形);Stanley 的 «深度 ≤ 维数» 理论中,«Cohen–Macaulay ⟹ f-向量不等式» 型结果可翻译为 «覆盖率下界»。已知部分族类(如 «2-生成» 族、几何格的开集族)猜想成立,其证明恰走深度/字典序机器。

说明 «若真,最简证明在交换代数里» 的直觉来源:猜想本质是 «单调结构的拓扑不等式»,而 Stanley 机器正为此类不等式而生。□

进展与文献

Frankl 1979;Poonen 的归约定理(1992);Polymath 社区的并闭集攻坚记录;Gilmer《A constant lower bound for the union-closed sets conjecture》(2022);Chase–Lovett 等的后续改良。开放核心:猜想本体(0.5 的跨越);«2-生成归约» 的完全实现;深度方法的系统移植。

← 返回问题 31