和集合予想

和集合閉集合予想はフランクル予想とも呼ばれ、1979 年にペーテル・フランクルが提起した組合せ論の未解決問題です。集合族は、その族に属する任意の 2 つの集合の和集合がその族に属する場合、和集合閉集合であると言われます。この予想は次のように述べられています。

空集合のみを含む族を除くすべての有限和閉集合族には、族内の集合の少なくとも半分に属する要素が存在する。

ティモシー・ガワーズ教授はこれを「組合せ論における最もよく知られた未解決問題の一つ」と呼び、この予想は「簡単なはずのように思えます（そしてその結果、長年にわたって多くの誤った証明を引き起こしてきました）。なぜそれが簡単ではないのかを理解するための良い方法は、それを証明するために午後を費やすことです。あなたが考えていたあの巧妙な平均化の議論は機能しません...」と述べています^[1]

集合の族

${\displaystyle \varnothing ,\{1\},\{1,2\},\{2,3,4\},\{1,2,3,4\}}$

は 5 つの異なる集合から成り、和集合として閉じています。元は5 つの集合のうち 3 つに含まれており (元 も 3 つに含まれています)、この場合、予想は成立します。 ${\displaystyle 1}$${\displaystyle 2}$

和集合閉族にシングルトン が含まれている場合(上記の例のように)、その要素は族の集合の少なくとも半分に出現する必要がある ことは簡単に示せます。${\displaystyle \{a\}}$${\displaystyle a}$

この予想に反例があるなら、有限集合のみからなる反例も存在する。したがって、一般性を失うことなく、与えられた和集合閉族内のすべての集合が有限であると仮定する。^[2]

有限の空でない集合 が与えられたとき、のすべての部分集合からなる冪集合は和集合である。 の各元は、の部分集合のちょうど半分に含まれます。したがって、一般に、族の集合の半分以上に含まれる元を求めることはできません。つまり、この予想の境界は鋭いのです。 ${\displaystyle U}$ ${\displaystyle P(U)}$${\displaystyle U}$${\displaystyle U}$${\displaystyle U}$

和集合予想が真となるのは、交差閉集合系がの集合の最大半数に の要素を含む場合であり、ここで は集合体、つまり系 のすべての要素の和集合です。 ${\displaystyle X}$${\displaystyle U(X)}$${\displaystyle X}$${\displaystyle U(X)}$${\displaystyle X}$

次の事実は同等性を示しています。

まず、集合系が和集合閉集合である場合、かつその補集合が交差集合閉集合である場合に限り、その集合系が和集合閉集合であることを示します。

補題 1. が宇宙 を持つ集合の和集合閉族である場合、内の集合 に対する補集合の族は交差に関して閉じている。 ${\displaystyle X}$${\displaystyle U(X)}$${\displaystyle X}$

証明。集合系の補集合を と定義します。 ${\displaystyle X}$${\displaystyle X^{c}:=\{U(X)-S:S\in X\}}$

をの任意の集合とし、とは両方とも に含まれます。は和集合なのでは に含まれ、したがって の補集合、はに含まれます。の要素は にも にも含まれません。 ${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle X}$${\displaystyle U(X)-X_{1}}$${\displaystyle U(X)-X_{2}}$${\displaystyle X^{c}}$${\displaystyle X}$${\displaystyle X_{1}\cup X_{2}=X_{3}}$${\displaystyle X}$${\displaystyle X_{3}}$${\displaystyle U(X)-X_{3}}$${\displaystyle X^{c}}$${\displaystyle X_{1}}$${\displaystyle X_{2}}$

そして、これはまさに、との補集合の共通集合 です。したがって、の補集合 が共通集合閉である場合に限り、は和集合閉です。 ${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle (U(X)-X_{1})\cap (U(X)-X_{2})}$${\displaystyle X}$${\displaystyle X}$${\displaystyle X^{c}}$

次に、集合系が少なくとも半数の集合に要素を含む場合、その補集合は最大で半数の集合に要素を含むことを示します。

補題 2. 集合系がその集合の半分に要素を含むのは、補集合系がその集合の多くても半分に要素を含む場合のみである。証明。簡単。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle X^{*}}$

したがって、が集合の和集合閉族である場合、集合の宇宙に対する補集合の族は交差に関して閉じており、 の集合の少なくとも半分に属する要素は、補集合の多くとも半分に属します。したがって、この予想の同等の形式（元々述べられた形式）は、複数の集合を含む任意の交差集合閉族に対して、族内の集合の多くとも半分に属する要素が存在するというものです。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle U(X)}$${\displaystyle X}$

上記では集合の族の観点から述べられているが、フランクルの予想は格子理論の問題としても定式化され研究されてきた。格子は、 2 つの要素xとyに対して、その両方より小さいか等しい唯一の最大要素 ( xとyの交点) と、その両方より大きいか等しい唯一の最小要素 ( xとyの結合点) が存在するような半順序集合である。集合Sのすべての部分集合の族は、集合包含によって順序付けられ、交点が集合論的な交差で表され、結合が集合論的な和で表された格子を形成する。このようにして形成された格子はブール格子と呼ばれる。フランクルの予想の格子理論バージョンは、任意の有限格子には、任意の2 つの小さい要素の結合ではない要素 x が存在し、 x以上の要素の数は最大で格子の半分になり、格子がブール格子の場合にのみ等しくなるというものです。Abe (2000) が示すように、格子に関するこのステートメントは、和集合に対するフランクルの予想と同等です。つまり、各格子は和集合族に変換でき、各和集合族は格子に変換できるため、変換されたオブジェクトに対するフランクルの予想が真であれば、元のオブジェクトに対する予想が真であることを意味します。この格子理論バージョンの予想は、格子のいくつかの自然なサブクラスに対して真であることが知られています^[3]が、一般的な場合には未解決のままです。

和集合予想のもう 1 つの同等の定式化では、グラフ理論を使用します。無向グラフでは、独立集合は、どの 2 つも互いに隣接していない頂点の集合です。独立集合は、より大きな独立集合のサブセットでない場合、最大です。どのグラフでも、最大独立集合の半分以上に現れる「重い」頂点は、それ自体が独立集合を形成している必要があります。したがって、グラフが空でない場合は、最大独立集合の半分以下に現れる頂点である、少なくとも 1 つの重くない頂点が常に存在します。和集合予想のグラフ定式化では、すべての有限の空でないグラフには、2 つの隣接する重くない頂点が含まれていると述べています。グラフに奇数サイクルが含まれている場合、 これは自動的に真になります。これは、すべての重い頂点の独立集合がサイクルのすべてのエッジをカバーすることができないためです。したがって、この予想のより興味深いケースは、奇数サイクルを持たない2 部グラフの場合です。この予想の別の同等の定式化は、すべての二部グラフには、二部グラフの両側に1つずつ、計2つの頂点が存在し、これらの2つの頂点のそれぞれは、グラフの最大独立集合の最大半分に属しているというものである。この予想は、弦二部グラフ、二部直列並列グラフ、および最大次数3の二部グラフに当てはまることが知られている。^[4]

この予想は、和集合族の多くの特殊なケースで証明されている。特に、次の場合に真であることが知られている。

• 最大46セットのファミリー、^[5]
• 和集合が最大12個の要素を持つ集合の族、^[6]
• 最小の集合が1つまたは2つの要素を持つ集合の族、^[7]
• 未発表のプレプリントによれば、ある定数に対して、少なくとも-元集合の部分集合の族が存在する。 ^[8]${\displaystyle ({\tfrac {1}{2}}-\varepsilon )2^{n}}$${\displaystyle n}$${\displaystyle \epsilon >0}$
• 短鎖が3以下、長鎖がn-1以上の集合族：^[9]

2022年11月に、以下の主張の証明を主張するプレプリントが投稿されました。^{[10] [11]}

空集合のみを含む族を除くすべての和集合閉族には、族内の集合の少なくとも 0.01 の割合に属する要素が存在します。

証明では、確率的およびエントロピー的方法を使用して、そのような境界を得ました。この論文内の推測は、 の下限分数の改善の可能性を示唆しました。和集合の推測自体は、分数 に対応します。 ${\displaystyle (3-{\sqrt {5}}\,)/2\approx 0.38197}$${\displaystyle 0.5}$

数日後、下限分数を とするプレプリントが3本投稿されました。^[12]その後すぐに、下限を に上げるプレプリントが2本投稿されました。^{[13] [14]}${\displaystyle (3-{\sqrt {5}}\,)/2}$${\displaystyle 0.38234}$

1979年にピーター・フランクルが交差閉集合族の観点からこの予想を述べたため、この予想は通常彼の功績とされ、フランクル予想と呼ばれることもある。この予想の和集合閉バージョンの最も古い出版はダファス（1985年）によるものと思われる。2013年までのこの予想に関する研究の歴史は、ブルーンとシャウト（2015年）によって出版された。

• 阿部哲也 (2000). 「強い半モジュラー格子とフランクルの予想」. Algebra Universalis . 44 (3–4): 379–382. doi :10.1007/s000120050195. S2CID  120741780.
• Alweiss, Ryan; Huang, Brice; Sellke, Mark (2022-11-21). 「Union-Closed Sets Conjecture の改良された下限値」. arXiv : 2211.11731 [math.CO].
• Vuckovic, Bojan; Zivkovic, Miodrag (2017). 「フランクルの予想の12要素のケース」(PDF) . IPSI BgD Transactions on Internet Research . 13 (1): 65. {{cite journal}}: (ヘルプ)|doi-access=が必要です|doi=
• Bošnjak, Ivica; Marković, Peter (2008). 「フランクルの予想の11要素の場合」. Electronic Journal of Combinatorics . 15 (1): R88. doi : 10.37236/812 .
• Bruhn, Henning; Charbit, Pierre; Schaudt, Oliver; Telle, Jan Arne (2015). 「和集合閉集合予想のグラフ定式化」. European Journal of Combinatorics . 43 : 210–219. arXiv : 1212.4175 . doi :10.1016/j.ejc.2014.08.030. MR  3266293. S2CID  2373192.
• Bruhn, Henning; Schaudt, Oliver (2015-11-01). 「Union-Closed Sets Conjecture の歩み」.グラフと組合せ論. 31 (6): 2043–2074. arXiv : 1309.3297 . doi :10.1007/s00373-014-1515-0.
• Chase, Zachary; Lovett, Shachar (2022-11-21). 「近似和集合閉予想」. arXiv : 2211.11689 [math.CO].
• Cambie, Stijn (2022-12-23). 「エントロピーアプローチを用いた和集合予想のより良い境界」. arXiv : 2212.12500 [math.CO].
• Duffus, D. (1985). Rival, I. (ed.).オープン問題セッション. グラフと順序. D. Reidel. p. 525.
• ギルマー、ジャスティン (2022-11-16)。「和集合予想の定数下限」。arXiv : 2211.09055 [ math.CO ]。
• Karpas, Ilan (2017). 「Union-Closed Families に関する 2 つの結果」. arXiv : 1708.01434 [math.CO].
• Tian, Chenxiao (2021). 「高さ H(𝓕)≤ 𝟑 および H(𝓕)≥ 𝐧 - 𝟏 に対して、Union-closed Sets の予想が成り立つ」. arXiv : 2112.06659 [math.CO].
• Lo Faro, Giovanni (1994)。「Union-closed sets の予想: 改善された境界」。J . Combin. Math. Combin. Comput . 16 : 97–102. MR  1301213。
• モリス、ロバート( 2006)。「FC 族とフランクルの予想の改良された境界」。ヨーロッパ 組合せ論ジャーナル。27 ( 2): 269–282。arXiv : math /0702348。doi : 10.1016/j.ejc.2004.07.012。MR 2199779。S2CID 17633023  。
• Poonen, Bjorn (1992). 「Union-closed family」. Journal of Combinatorial Theory . Series A. 59 (2): 253–268. doi : 10.1016/0097-3165(92)90068-6 . MR  1149898.
• ラインホールド、ユルゲン (2000)。「フランクルの予想は下半モジュラー格子に対して正しい」。グラフと組合せ論。16 (1): 115–116。doi :10.1007/s003730050008。S2CID  12660895。
• Roberts, Ian; Simpson, Jamie (2010). 「和集合閉集合予想に関する注記」(PDF) . Australas. J. Combin . 47 : 265–267.
• Sarvate, DG; Renaud, J.-C. (1989). 「和集合閉集合予想について」Ars Combin . 27 : 149–153. MR  0989460.
• Sawin, Will (2022-11-21). 「和集合予想の改良された下限値」. arXiv : 2211.11504 [math.CO].
• Yu, Lei (2022-12-01). 「Union-Closed Sets Conjecture の次元フリー境界」. arXiv : 2212.00658 [math.CO].

• フランクルの和集合予想、オープン問題ガーデン。
• 和集合予想 (1979)。DB West が収集した Open Problems – Graph Theory and Combinatorics に収録。