大問題

20世紀

1. 1932
   エルデシュの食い違い問題組合せ論と離散数学, 算術と数論. 任意の無限 $\pm 1$ 数列は、ある斉次等差数列 $d, 2d, \dots, nd$ に沿っていくらでも大きな部分和をもつ。2015年にテレンス・タオによって証明された。エルデシュテレテレンス・タオ, 2015
2. 1935
   ハッピーエンド問題（エルデシュ・セケレシュ）組合せ論と離散数学, 幾何学. 凸 $n$ 角形の存在を保証するには、平面上の一般の位置に何個の点が必要か。1933年にエスター・クラインが $n = 4$ の場合を提起し、彼女とジョージ・セケレシュの結婚につながったことからポール・エルデシュが「ハッピーエンド問題」と名付けた。予想されている厳密値 $\mathrm{ES}(n) = 2^{n-2} + 1$ は $n \le 6$ でのみ証明されているが、2016年にアンドリュー・スクが漸近評価 $\mathrm{ES}(n) = 2^{n + o(n)}$ を確立した。エルデシュ未解決
3. 1941
   加法的基底に関するエルデシュ・トゥーラン予想算術と数論, 組合せ論と離散数学. 自然数の集合が2元の和によって十分大きいすべての整数を覆う（位数 $2$ の漸近的基底である）ならば、2元の和としての表し方がいくらでも多くなる整数が必ず存在するか。1941年にポール・エルデシュとパール・トゥーランが提唱した予想 $\limsup_{n \to \infty} r_A(n) = \infty$ は現在も未解決である。エルデシュ未解決
4. 1946
   エルデシュの単位距離問題幾何学, 組合せ論と離散数学. 平面上の $n$ 個の点のうち、距離 $1$ にある対は最大いくつあるか。上界は $O(n^{4/3})$ であり、2026年の代数的整数論に基づく構成により $u(n) = \Omega(n^{1+c})$ が示され、エルデシュの $n^{1+o(1)}$ 予想は反証された。エルデシュ未解決
5. 1948
   エルデシュ–シュトラウス予想算術と数論. 1948年にポール・エルデシュとエルンスト・G・シュトラウスによって定式化されたこのエジプト分数予想は、$4/n$ が常に3つの正の整数の逆数の和として表せるかを問う。約数 $d \mid n$ に対する分解は定数倍によって $n$ の分解を与えるため、$n = p$ が素数の場合について証明すれば十分である。簡単な代数的恒等式によって $p \not\equiv 1 \pmod{24}$ を満たす素数は直ちに解決され、より大きな法による被覆系がほとんどの剰余類を排除することで $n = 10^{17}$ までのコンピュータ検証が可能となっているが、有限個の恒等式からなる完全な被覆系は存在し得ない。エルデシュ未解決
6. 1960
   エルデシュ・ラドのひまわり予想組合せ論と離散数学. どの2つの共通部分もすべて一致するような $r$ 個の集合（ひまわり）を含まない $w$ 元集合の族は、最大でどれほど大きくなり得るか。1960年にポール・エルデシュとリチャード・ラドが階乗上界 $w! (r - 1)^w$ とともに提唱したこの予想は、2019年にアルワイス、ロヴェット、ウー、チャンによって画期的な進展（のちに $(C r \log w)^w$ まで改良）を見たが、純粋な指数上界 $C_r^w$ は未解決である。エルデシュ未解決
7. 1972
   エルデシュ・フェイバー・ロヴァース予想組合せ論と離散数学. どの2つも高々1頂点しか共有しないサイズ $n$ の $n$ 個のクリークの和集合は、常に $n$ 色で適切に頂点彩色できるか。1972年にポール・エルデシュ、ヴァンス・フェイバー、ラースロー・ロヴァースによって提起されたこの予想は、2021年にカン、ケリー、キューン、メトゥク、オストフスによって十分大きなすべての $n$ について証明され（2023年に Annals of Mathematics に掲載）、一方で小さな $n \le 12$ は計算機で検証済みであり中間の値のみが未解決として残っている。エルデシュ解決済み
8. 1973
   等差数列に関するエルデシュ予想算術と数論, 組合せ論と離散数学. 逆数和が $\sum_{n \in A} \frac{1}{n} = \infty$ ならば、$A$ は任意の長さの等差数列を含むか。$k = 3$ の場合はトーマス・ブルームとオロフ・シサスク（2020年）により証明されたが、$k \ge 4$ はすべて未解決である。エルデシュ未解決
9. 1977
   エルデシュ・ハイナル予想組合せ論と離散数学. 一般の $n$ 頂点グラフでは対数サイズ $\Theta(\log n)$ のクリークまたは独立集合しか保証されないのに対し、ポール・エルデシュとアンドラーシュ・ハイナルは1977年、任意の固定された誘導部分グラフ $H$ を禁止すれば多項式サイズ $n^{\delta_H}$ のクリークまたは独立集合が強制されると予想した。エルデシュ未解決