ひまわり（数学）

集合論や極限組合せ論などの数学の分野において、ひまわり集合またはひまわり系^[1]とは、すべての可能な異なる集合のペアが同じ共通部分を共有する集合の集合である。この共通共通部分はひまわり 核と呼ばれる。${\displaystyle \Delta }$

この名前は、ヒマワリ集合のベン図を直感的に配置したときに、植物のヒマワリとの視覚的な類似性から生まれました。ヒマワリ集合の共有要素が図の中央に集まっており、共有されていない要素が共有要素の周囲に円形に分布しているとします。すると、ベン図が完成すると、共通要素と 1 つ以上の固有要素を囲む葉状のサブセットが、花びらの外観を呈します。

ひまわりに関連して生じる主な研究課題は、与えられた集合の集合の中に、どのような条件下で大きなひまわり（多くの集合を持つひまわり）が存在するか、である。-補題、ひまわり補題、エルデシュ-ラドのひまわり予想は、与えられた集合の中に大きなひまわりが存在することを示唆する、より弱い条件を次々に与えており、後者は極限組合せ論の最も有名な未解決問題の一つである。^[2]${\displaystyle \Delta }$

が上の集合系、つまり集合 の部分集合の集まりであるとします 。 の集合がひまわり（または-システム）とは、のそれぞれの相異なるおよびに対して となるのサブセットが存在する場合です。言い換えると、内のすべての集合が要素の同じ共通サブセットを共有する場合、集合系または集合の集合はひまわりです。 の要素は、共通サブセットに存在するか、要素のうちの多くとも 1 つにしか存在しません。 の要素は、サブセットの一部にのみ共有され、他の部分には共有されません。この共通集合 は空の場合があり、互いに素なサブセットの集合もひまわりであることに注意してください。同様に、それぞれが同じ要素を含む集合の集合も、自明にひまわりです。 ${\displaystyle W}$${\displaystyle U}$${\displaystyle U}$${\displaystyle W}$${\displaystyle \Delta }$${\displaystyle S}$${\displaystyle U}$ ${\displaystyle A}$${\displaystyle B}$${\displaystyle W}$${\displaystyle A\cap B=S}$${\displaystyle W}$${\displaystyle W}$${\displaystyle U}$${\displaystyle S}$${\displaystyle W}$${\displaystyle U}$${\displaystyle W}$${\displaystyle S}$

ヒマワリの研究は、一般的に、集合系にヒマワリが含まれる場合、特に集合系が必ずヒマワリを含むほど十分に大きい場合に焦点を当てています。

具体的には、研究者らは、関数を非負整数に対して解析します。関数 は、あらゆる集合の濃度が最大 であるような任意の集合系に対して、 が集合より多い場合、 には集合のひまわりが含まれるような最小の非負整数として定義されます。このような が存在することは明らかではありませんが、エルデシュとラドーの基本的で単純な結果であるデルタシステム定理は、それが存在することを示しています。 ${\displaystyle f(k,r)}$ ${\displaystyle k,r}$ ${\displaystyle n}$${\displaystyle W}$${\displaystyle S\in W}$${\displaystyle k}$${\displaystyle W}$${\displaystyle n}$${\displaystyle W}$${\displaystyle r}$${\displaystyle n}$

エルデシュ-ラドのデルタシステム定理（ひまわりの補題の系）：

各、に対して、 という整数が存在し、 -集合の集合系の濃度が より大きい場合、 にはサイズ のヒマワリが含まれます。 ${\displaystyle k>0}$${\displaystyle r>0}$${\displaystyle f(k,r)}$${\displaystyle F}$${\displaystyle k}$${\displaystyle f(k,r)}$${\displaystyle F}$${\displaystyle r}$

文献では、は集合ではなく集合であると想定されることが多いため、 には任意の集合が最大で 1 回しか出現できない。ダミー要素を追加することで、のすべての集合が濃度 を持つような集合系のみを考えれば十分であるため、ひまわりの補題は「 -一様」集合系に対しても成り立つと同等に表現されることが多い。 ^[3]${\displaystyle W}$${\displaystyle W}$${\displaystyle W}$${\displaystyle W}$${\displaystyle k}$${\displaystyle k}$

エルデシュとラド（1960、p.86）は、ひまわりの補題を証明した。これは、^[4]

${\displaystyle f(k,r)\leq k!(r-1)^{k}.}$

つまり、およびが正の整数である場合、の集合の以上の濃度 の集合系には、少なくとも の集合を持つヒマワリが含まれます。 ${\displaystyle k}$${\displaystyle r}$${\displaystyle W}$${\displaystyle k!(r-1)^{k}}$${\displaystyle k}$${\displaystyle r}$

エルデシュ-ラドのひまわりの補題は、帰納法によって直接証明できます。まず、 は、集合系がサイズ の相異なる集合のコレクションでなければならないため、これらの集合の集合はひまわりを作ります。一般的なケースでは、には集合を持つひまわりがないと仮定します。次に、 がペアワイズ ディスジョイント集合の最大のコレクションであると考えます (つまり、 は空集合であり、 のすべての集合はいずれかの と交差します)。 にはサイズ のひまわりがないこと、およびペアワイズ ディスジョイント集合のコレクションはひまわりであると仮定したため、 です。 ${\displaystyle f(1,r)\leq r-1}$${\displaystyle W}$${\displaystyle r}$${\displaystyle W}$${\displaystyle r}$${\displaystyle A_{1},A_{2},\ldots ,A_{t}\in W}$${\displaystyle A_{i}\cap A_{j}}$${\displaystyle i=j}$${\displaystyle W}$${\displaystyle A_{i}}$${\displaystyle W}$${\displaystyle r}$${\displaystyle t<r}$

とする。それぞれが濃度 を持つので、 の濃度はで制限される。を と定義する。${\displaystyle A=A_{1}\cup A_{2}\cup \cdots \cup A_{t}}$${\displaystyle A_{i}}$${\displaystyle k}$${\displaystyle A}$${\displaystyle kt\leq k(r-1)}$${\displaystyle W_{a}}$${\displaystyle a\in A}$

${\displaystyle W_{a}=\{S\setminus \{a\}\mid a\in S,\,S\in W\}.}$

すると、 はのような集合系になりますが、 のすべての要素には の要素があります。さらに、 のすべてのひまわりは、すべての集合 を単純に足し戻すことで、のひまわりに対応します。つまり、 にはサイズ のひまわりが存在しないという仮定により、 のサイズはによって制限される必要があります。 ${\displaystyle W_{a}}$${\displaystyle W}$${\displaystyle W_{a}}$${\displaystyle k-1}$${\displaystyle W_{a}}$${\displaystyle W}$${\displaystyle a}$${\displaystyle W}$${\displaystyle r}$${\displaystyle W_{a}}$${\displaystyle f(k-1,r)-1}$

どの集合ものいずれかと交差するため、 は と交差し、したがって 内の集合の少なくとも 1 つに対応します。 ${\displaystyle S\in W}$${\displaystyle A_{i}}$${\displaystyle A}$${\displaystyle W_{a}}$

${\displaystyle |W|\leq \sum _{a\in A}|W_{a}|\leq |A|(f(k-1,r)-1)\leq k(r-1)f(k-1,r)-|A|\leq k(r-1)f(k-1,r)-1.}$

したがって、 の場合、 にはサイズ集合の集合ヒマワリが含まれます。したがって、 であり、定理が成り立ちます。^[2]${\displaystyle |W|\geq k(r-1)f(k-1,r)}$${\displaystyle W}$${\displaystyle r}$${\displaystyle k}$${\displaystyle f(k,r)\leq k(r-1)f(k-1,r)}$

ひまわり予想は、エルデシュとラド（1960、p. 86）の予想のいくつかのバリエーションの1つであり、各 に対して、のみに依存するある定数に対してが成り立つというものです。 の値が固定されていても、この予想は未解決のままです。たとえば、ある に対して が成り立つかどうかはわかっていません。^[5] 2021年に発表されたアルワイス、ラヴェット、ウー、チャンの論文は、この予想に向けて最も進歩しており、に対してが成り立つことを証明しています。^{[6] [7]}論文の最初のバージョンが発表されてから1か月後、ラオは まで境界を明確にしました。^[8]現在最もよく知られている境界は です。^[9]${\displaystyle r>2}$${\displaystyle f(k,r)\leq C^{k}}$${\displaystyle C>0}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r=3}$${\displaystyle f(k,3)\leq C^{k}}$${\displaystyle C>0}$${\displaystyle f(k,r)\leq C^{k}}$${\displaystyle C=O(r^{3}\log(k)\log \log(k))}$${\displaystyle C=O(r\log(rk))}$${\displaystyle C=O(r\log k)}$

エルデシュとラドーは、 における次の下限を証明しました。これは、元のひまわりの補題が において最適であるという主張に等しいです。 ${\displaystyle f(k,r)}$${\displaystyle r}$

定理。${\displaystyle (r-1)^{k}\leq f(k,r).}$

証明。異なる要素のシーケンスの集合はひまわりではありません。がひまわりのない -集合の最大集合のサイズを表すものとします。 がそのような集合であるとします。 の追加要素集合を取り、の互いに素なコピーの1 つに含まれる各集合に 1 つの要素を追加します。 互いに素なコピーと追加された要素の和集合を取り、この集合 と表します。 の要素が追加されたコピーはの分割を形成します。 がひまわりを含まないことがわかります。が互いに素な分割の 1 つに含まれる場合、H がひまわりを含まないという仮定により、任意の集合の選択はひまわりを含まないためです。 そうでない場合、分割の複数の集合から集合が選択される場合、分割は しかないため、1 つの分割から 2 つを選択する必要があります。 これは、すべての集合ではなく、少なくとも 2 つの集合に共通の要素があることを意味します。 したがって、これは集合のひまわりではありません。 ${\displaystyle k=1}$${\displaystyle r-1}$${\displaystyle h(k-1,r)}$${\displaystyle k-1}$${\displaystyle r}$${\displaystyle H}$${\displaystyle r-1}$${\displaystyle r-1}$${\displaystyle H}$${\displaystyle r-1}$${\displaystyle H^{*}}$${\displaystyle H}$${\displaystyle r-1}$${\displaystyle H^{*}}$${\displaystyle (r-1)|H|\leq |H^{*}|}$${\displaystyle H^{*}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r-1}$${\displaystyle r}$

より強力な結果は次の定理です。

定理。${\displaystyle f(a+b,r)\geq (f(a,r)-1)(f(b,r)-1)}$

証明。と を2 つのヒマワリのない族とします。Fの各集合について、 のすべての集合をに追加して、多くの集合を作成します。この集合の族を と表記します。内のすべての の和集合を取ります。これにより、ヒマワリのない集合 の族が生成されます。${\displaystyle F}$${\displaystyle F^{*}}$${\displaystyle A}$${\displaystyle F^{*}}$${\displaystyle A}$${\displaystyle |F^{*}|}$${\displaystyle F_{A}}$${\displaystyle F_{A}}$${\displaystyle A}$${\displaystyle F}$${\displaystyle |F^{*}||F|}$

に対するエルデシュ-ラドひまわり問題の最良の下限値は、アボット、ハンセン、ザウアーによるものです。 ^{[10] [11]}この下限値は50年以上改善されていません。 ${\displaystyle r=3}$${\displaystyle 10^{\frac {k}{2}}\leq f(k,3)}$

ひまわり補題は理論計算機科学において数多くの応用がある。例えば、1986年にラズボロフはひまわり補題を用いて、クリーク言語には（超多項式）サイズの単調回路が必要であることを証明した。これは当時の回路計算量理論における画期的な成果であった。ハスタッド、ジュクナ、プドラックはこれを用いて深さ回路の下限を証明した。また、ヒッティングセット問題のパラメータ化された複雑性にも応用され、与えられた集合族から少なくとも1つの要素を含む小さな要素集合を見つけるための固定パラメータの扱いやすいアルゴリズムを設計した。 ^[12]${\displaystyle n^{\log(n)}}$${\displaystyle 3}$ ${\displaystyle AC_{0}}$

エルデシュ-ラド -システム定理と本質的に同等の-補題のバージョンは、k-集合の可算な集合には可算無限のひまわりまたは-システムが含まれることを述べています。 ${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta }$

-補題は、有限集合のすべての無数集合には無数な -系が含まれることを述べています。 ${\displaystyle \Delta }$${\displaystyle \Delta }$

-補題は、強制的半集合における互いに互換性のない要素の集合のサイズに上限を課すための証明で使用される、組み合わせ集合論のツールです。たとえば、連続体仮説が成り立たないことがツェルメロ-フランケル集合論と矛盾しないことを示す証明の要素の 1 つとして使用できます。これは、 Shanin  (1946) によって導入されました。${\displaystyle \Delta }$

が の可算な部分集合の サイズのコレクションであり、連続体仮説が成り立つ場合、サイズの- 部分系が存在します。を列挙します。 について、 とします 。Fodorの補題により、がで常に に等しいようなをで定常的に固定します。 がにあるときはいつでも となるような の濃度を構築します。連続体仮説を使用すると、の可算な部分集合は - 個しかないため、さらに間引きを行うことでカーネルを安定化できます。 ${\displaystyle W}$${\displaystyle \omega _{2}}$${\displaystyle \omega _{2}}$${\displaystyle \omega _{2}}$${\displaystyle \Delta }$${\displaystyle \langle A_{\alpha }:\alpha <\omega _{2}\rangle }$${\displaystyle W}$${\displaystyle \operatorname {cf} (\alpha )=\omega _{1}}$${\displaystyle f(\alpha )=\sup(A_{\alpha }\cap \alpha )}$${\displaystyle S}$${\displaystyle \omega _{2}}$${\displaystyle f}$${\displaystyle \beta}$${\displaystyle S}$${\displaystyle S'\subseteq S}$ ${\displaystyle \omega _{2}}$${\displaystyle i<j}$${\displaystyle S'}$${\displaystyle A_{i}\subseteq j}$${\displaystyle \omega _{1}}$${\displaystyle \beta }$

• キャップセット

• ティエマン、ルネ。エルデシュとラドーのひまわり補題 (Isabelle/HOL における形式的証明の開発、形式的証明のアーカイブ)