未解决问题,组合数学与离散数学,1979年提出
并闭集猜想(弗兰克尔猜想)
未解决
设 F 是不全为空集(F={∅})的有限集构成的有限集族,且对并运算封闭(对任意 A,B∈F,其并集 A∪B∈F)。则在基础集 ⋃A∈FA 中存在一个元素 x 属于 F 中至少一半的集合,即 #{A∈F:x∈A}≥21∣F∣。
研究前沿 截至2026年截至2026年,弗兰克尔的 21 猜想仍然悬而未决,目前最优的一般常数下界略高于 23−5≈0.38197(≈0.38234,余磊,2023)。关键在于,萨温与阿尔韦斯–黄–塞尔克证明了由于存在近似并闭的概率分布,23−5 是吉尔默单分布独立同分布熵方法的精确屏障。若要推进到 21,必须在高阶上利用集族 F 的精确离散组合结构。
已知最佳结果
- 每个有限并闭集族 F={∅} 都存在出现频率至少为 23−5≈0.38197 的元素(阿尔韦斯–黄–塞尔克、蔡斯–洛维特、皮博迪与萨温,2022,继吉尔默之后),并于2023年进一步提升至≈0.38234。
- 完整的 21 猜想对基础集规模 n≤12 以及满足 ∣F∣≤50 的所有并闭集族均成立(博什尼亚克–马尔科维奇,2008;罗伯茨–辛普森,2010)。
使用的方法及其局限
| 方法 | 取得的结果 | 局限所在 |
|---|
| 独立随机子集的香农熵方法(吉尔默方法) | 独立抽样 A,B∈F 使得 A∪B∈F,利用条件熵的次模性证明当所有边缘概率低于 23−5 时必有 H(A∪B)>H(A),从而导出矛盾。 | 对于每个坐标以概率 p>23−5 取 1 的二元乘积分布,二元熵满足 h(2p−p2)≤h(p),使得单分布熵方法在 23−5 处受阻。 |
| 权平均与局部构型化归 | 在 F 包含规模为 1 或 2 的小集合,或 ∣F∣ 相对于基础集规模 n 较大时,证明了 21 下界。 | 当 F 中最小非空集合的规模随 n 增长且 ∣F∣ 仅呈 n 的多项式或亚指数规模时,该方法失效。 |
尚未解决的问题
- 每个有限并闭集族 F={∅} 是否都包含一个属于至少 21∣F∣ 个集合的元素?
- 多样本或高阶信息论不等式能否大幅突破 23−5 屏障并逼近 21?