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} に到達するには、1次のエントロピー比較を超えて F\mathcal{F} の厳密な組合せ的離散構造を活用する必要がある。

既知の最良の結果

  • 任意の有限合併閉集合族 F≠{∅}\mathcal{F} \neq \{\emptyset\} には出現頻度が少なくとも 3−52≈0.38197\frac{3 - \sqrt{5}}{2} \approx 0.38197 の元が存在し（ギルマーに続くアルワイス・ホアン・セルケ、チェイス・ロヴェット、ペボディ、サウィン、2022年）、さらに≈0.38234\approx 0.38234 へと改良されている（2023年）。
  • 完全な 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 をとる積分布では2値エントロピーが h(2p−p2)≤h(p)h(2p - p^2) \le h(p) を満たすため、単一分布のエントロピー評価は 3−52\frac{3 - \sqrt{5}}{2} で頭打ちとなる。
重み平均化と局所構造還元F\mathcal{F} がサイズ 11 や 22 の小さい集合を含む場合や、台集合のサイズ nn に対して ∣F∣|\mathcal{F}| が大きい場合に 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