MathLabs

未解决问题,组合数学与离散数学,1979年提出

并闭集猜想(弗兰克尔猜想)

未解决

设 F\mathcal{F} 是不全为空集(F≠{∅}\mathcal{F} \neq \{\emptyset\})的有限集构成的有限集族,且对并运算封闭(对任意 A,B∈FA, B \in \mathcal{F},其并集 A∪B∈FA \cup B \in \mathcal{F})。则在基础集 ⋃A∈FA\bigcup_{A \in \mathcal{F}} A 中存在一个元素 xx 属于 F\mathcal{F} 中至少一半的集合,即 #{A∈F:x∈A}≥12∣F∣\#\{A \in \mathcal{F} : x \in A\} \ge \frac{1}{2} |\mathcal{F}|。

研究前沿 截至2026年

截至2026年,弗兰克尔的 12\frac{1}{2} 猜想仍然悬而未决,目前最优的一般常数下界略高于 3−52≈0.38197\frac{3 - \sqrt{5}}{2} \approx 0.38197(≈0.38234\approx 0.38234,余磊,2023)。关键在于,萨温与阿尔韦斯–黄–塞尔克证明了由于存在近似并闭的概率分布,3−52\frac{3 - \sqrt{5}}{2} 是吉尔默单分布独立同分布熵方法的精确屏障。若要推进到 12\frac{1}{2},必须在高阶上利用集族 F\mathcal{F} 的精确离散组合结构。

已知最佳结果

  • 每个有限并闭集族 F≠{∅}\mathcal{F} \neq \{\emptyset\} 都存在出现频率至少为 3−52≈0.38197\frac{3 - \sqrt{5}}{2} \approx 0.38197 的元素(阿尔韦斯–黄–塞尔克、蔡斯–洛维特、皮博迪与萨温,2022,继吉尔默之后),并于2023年进一步提升至≈0.38234\approx 0.38234。
  • 完整的 12\frac{1}{2} 猜想对基础集规模 n≤12n \le 12 以及满足 ∣F∣≤50|\mathcal{F}| \le 50 的所有并闭集族均成立(博什尼亚克–马尔科维奇,2008;罗伯茨–辛普森,2010)。

使用的方法及其局限

方法取得的结果局限所在
独立随机子集的香农熵方法(吉尔默方法)独立抽样 A,B∈FA, B \in \mathcal{F} 使得 A∪B∈FA \cup B \in \mathcal{F},利用条件熵的次模性证明当所有边缘概率低于 3−52\frac{3 - \sqrt{5}}{2} 时必有 H(A∪B)>H(A)H(A \cup B) > H(A),从而导出矛盾。对于每个坐标以概率 p>3−52p > \frac{3 - \sqrt{5}}{2} 取 11 的二元乘积分布,二元熵满足 h(2p−p2)≤h(p)h(2p - p^2) \le h(p),使得单分布熵方法在 3−52\frac{3 - \sqrt{5}}{2} 处受阻。
权平均与局部构型化归在 F\mathcal{F} 包含规模为 11 或 22 的小集合,或 ∣F∣|\mathcal{F}| 相对于基础集规模 nn 较大时,证明了 12\frac{1}{2} 下界。当 F\mathcal{F} 中最小非空集合的规模随 nn 增长且 ∣F∣|\mathcal{F}| 仅呈 nn 的多项式或亚指数规模时,该方法失效。

尚未解决的问题

  • 每个有限并闭集族 F≠{∅}\mathcal{F} \neq \{\emptyset\} 是否都包含一个属于至少 12∣F∣\frac{1}{2} |\mathcal{F}| 个集合的元素?
  • 多样本或高阶信息论不等式能否大幅突破 3−52\frac{3 - \sqrt{5}}{2} 屏障并逼近 12\frac{1}{2}?

参考文献

  1. Justin Gilmer (2022). A constant lower bound for the union-closed sets conjecture · arXiv:2211.09055 [预印本,未经同行评审]
  2. Henning Bruhn, Oliver Schaudt (2015). The journey of the union-closed sets conjecture · DOI:10.1007/s00373-014-1515-0