MathLabs

未解決問題、組合せ論と離散数学、1960年に提起

エルデシュ・ラドのひまわり予想

未解決エルデシュ

任意の整数 r≥3r \ge 3 に対して rr のみに依存する定数 Cr>0C_r > 0 が存在し、各集合の要素数が高々 ww である集合族 F\mathcal{F} が ∣F∣≥Crw|\mathcal{F}| \ge C_r^w を満たすならば、必ず rr-ひまわり（または Δ\Delta-システム）、すなわちすべての i≠ji \neq j に対して Si∩Sj=KS_i \cap S_j = K（共通の芯 KK）を満たす相異なる rr 個の集合 S1,…,Sr∈FS_1, \dots, S_r \in \mathcal{F} を含む。

提起者, 1960ポール・エルデシュ
研究の最前線 2026年時点

2026年現在、ww-一様集合族における rr-ひまわり問題の最良の上界は ∣F∣≥(Crlog⁡w)w|\mathcal{F}| \ge (C r \log w)^w である（アルワイス・ロヴェット・ウー・チャン、2019年およびラオ、2020年に続くベル・チュエルエチャ・ヴァルンケ、2021年）。この評価はより強い (1/r,1/r)(1/r, 1/r)-近似（ロバスト）ひまわりに対して成り立っており、ロバストひまわりに対しては log⁡w\log w の因子が実際に最良（タイト）であることが知られている。したがって、r=3r = 3 の場合であっても残りの log⁡w\log w 因子を取り除いて CrwC_r^w に到達するには、花びらの厳密な非交差性と確率的なロバスト非交差性を区別する新しい手法が必要となる。

既知の最良の結果

  • サイズ ∣F∣≥(Crlog⁡w)w|\mathcal{F}| \ge (C r \log w)^w の任意の ww 元集合族は rr-ひまわりを含む（アルワイス・ロヴェット・ウー・チャン、2019年；ラオ、2020年；ベル・チュエルエチャ・ヴァルンケ、2021年）。
  • {0,1}n\{0, 1\}^n（あるいは F3n\mathbb{F}_3^n）における弱いひまわり予想は、スライスランク多項式法により指数上界 cnc^n（c<2c < 2）で証明されている（ナスルンド、サウィン、2017年）。

使われた手法と限界

手法達成したこと限界
κ-スプレッド集合系とシャノン・エントロピー符号化一般の集合族を κ\kappa-スプレッド族（どの非空部分集合も κ−∣T∣∣F∣\kappa^{-|T|} |\mathcal{F}| 個を超える集合に含まれない族）に帰着させ、密度 12r\frac{1}{2r} のランダム集合が 11 に近い確率で F\mathcal{F} の元を含むことを示して (Crlog⁡w)w(C r \log w)^w を導いた。密度 12r\frac{1}{2r} のランダム集合がサイズ ww の集合を高い確率で覆うにはスプレッド係数が κ=Ω(rlog⁡w)\kappa = \Omega(r \log w) である必要があり、ロバストひまわりに対しては log⁡w\log w の因子が不可欠となる。
スライスランク多項式法台集合のサイズ nn が固定されている場合に、{0,1}n\{0, 1\}^n のひまわりを含まない部分集合に対して指数上界 (3/22/3)n≈1.8899n(3 / 2^{2/3})^n \approx 1.8899^n を証明した。評価が各集合のサイズ ww ではなく台集合全体のサイズ nn に指数的に依存するため、n≫wn \gg w の場合には機能しない。

未解決の問い

  • サイズ C3wC_3^w 以上の任意の ww 元集合族が必ず 33-ひまわりを含むような絶対定数 C3>0C_3 > 0 は存在するか。
  • r=3r = 3 を固定したとき、上界 (Crlog⁡w)w(C r \log w)^w を Crw(log⁡w)o(w)C_r^w (\log w)^{o(w)} へと改良できるか。

参考文献

  1. Paul Erdős, Richard Rado (1960). Intersection theorems for systems of sets · DOI:10.1112/jlms/s1-35.1.85
  2. Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang (2021). Improved bounds for the sunflower lemma · DOI:10.4007/annals.2021.194.3.5 · arXiv:1908.08483