p_{c} (F) \leq K q (F) lo g ℓ (F)

カーン＝カライ予想

Kahn-Kalai conjecture

16年残った予想の証明を、2人は一晩で確かめた。

でたらめに線を引いたグラフに形が現れる確率の境目は、数えるだけの見積もりの高々log倍。2006年の予想が、2022年に6ページの論文で証明された。

年代: 2006〜2022年
習う: 大3以上・確率・統計・ランダムグラフ
レベル: 大学(例題 5 問)
人物: ジェフ・カーン、ギル・カライ、ミシェル・タラグラン、パク・ジニョン、ファム・フイ・トゥアン、ポール・エルデシュ、アルフレッド・レーニ

数学情報科学物理学

逸話

提案した2人が疑った予想

「たぶん、成り立たないと予想するほうが理にかなっているだろう」。2006年、ジェフ・カーンとギル・カライは、自分たちの予想を述べた論文の1ページ目に、こう書き添えた。点をでたらめに線で結んでいくと、三角形やすべての点をめぐる道のような形は、ある確率を境に急に現れる。その境目は、数を数えるだけの素朴な見積もりと高々 $lo g$ の倍率しか違わない、という予想である。

16年後、答えは「成り立つ」と出た。2022年3月31日、スタンフォード大学のパク・ジニョンとファム・フイ・トゥアンが、証明をarXivに公開したのである。最初の版は、わずか6ページだった。

この一文は、謙遜ではなかった。2人は続けて、反証も簡単ではなさそうで、反例が見つかればそれも面白い、と記している。証明が出た直後の2022年4月2日、カライは自分のブログで「ジェフと私は反例を懸命に探したが、見つかったのは、もっと一般的で強い形の、反証できない予想ばかりだった」と振り返った。

パクの経歴は、数学者としては遠回りに見える。スタンフォード大学の同窓会誌によると、韓国で大学を卒業したとき、パクには仕事が要った。数学者になりたかったが、なり方が分からない。そこで中学校で7年、数学を教えた。

午後の教室で、黒板の前に立つ教師と、ノートに向かう生徒たちの後ろ姿(画像生成 AI で描いたイメージ) — 韓国で大学を出たあと、パクは中学校で7年、数学を教えた（スタンフォード大学の同窓会誌による）画像生成AIで描いたイメージ

アメリカのラトガース大学で博士課程に進むと、指導を受けたのは予想を立てた本人のカーンだった。2019年には、カーンら3人と、予想を弱めた形を証明している。2020年に学位を取り、プリンストン高等研究所を経て、スタンフォード大学に移った。

ジェフ・カーンしきい値は数えるだけの見積もりのlog倍以内だと、カライと予想した

スタンフォードでは、博士課程の学生だったファムと、別の問題に何か月も取り組んでいた。そこで得た考えが、予想を解く手がかりになった。「その考えが浮かんでからは、本当にうまくいくと確かめるのに一晩で足りた」とファムは言う。同じ取材に、パクは笑って「簡単でした」と答えた。ファムの指導教員ジェイコブ・フォックスは、2人の証明を「魔法のよう」と評している。

夜の研究室の机に、灯りのついたスタンドと開いたノート、2つのコーヒーカップが置かれている(画像生成 AI で描いたイメージ) — 2022年3月、2人は着想が正しいことを一晩で確かめた（スタンフォード大学の同窓会誌による）画像生成AIで描いたイメージ

パク・ジニョン中学校の教師を経て、ファムとカーン＝カライ予想を証明した

ファム・フイ・トゥアン博士課程の学生のとき、パクとカーン＝カライ予想を証明した

起源

1960年の「意外な結果」

ランダムグラフの研究は、ハンガリーのポール・エルデシュとアルフレッド・レーニに始まる。1960年の論文で2人は、 $n$ 個の点の間に線を1本ずつでたらめに足していく過程を「グラフの進化」と呼び、進化を調べるとかなり意外な結果に行き着く、と書いた。いくつもの基本的な性質が、線の数がある関数よりずっと多ければほぼ確実に成り立ち、ずっと少なければほぼ確実に成り立たない。2人はこの関数を「しきい値関数」と名づけた。

境目の位置は、形によって違う。1960年の論文によると、線の数が点の数の $c$ 倍に近いとき、三角形の数は平均 $(2 c)^{3} /6$ のポアソン分布に近づく。三角形は、線の数が点の数に比例するあたりで現れる。一方、1959年の論文では、グラフが連結になる、つまりすべての点が1つにつながるのは、線がおよそ $\frac{1}{2} n lo g n$ 本に達したころだと示されていた。だから、全体をつなぐには、三角形のときより $lo g n$ に比例して多くの線が要る。

1987年には、ベーラ・ボロバシュとアンドリュー・トマソンが、線を足しても崩れない性質なら、どれもしきい値関数を持つと証明した。では、境目の位置を、どこまで素朴に見積もれるのだろうか。

2006年のカーンとカライの出発点は、決まったグラフ $H$ を含むかどうかの問題だった。 $H$ とその部分グラフの個数の期待値が、どれも1を超える $p$ を素朴な見積もりにする。 $H$ の大きさが決まっていれば、この見積もりは本当の境目と定数倍しか違わない。ところが、すべての点を2つずつ組にする完全マッチングや、すべての点を1周するハミルトン閉路では、見積もりは $1/ n$ の程度なのに、本当の境目は $(lo g n) / n$ にある。点が1つでも孤立すれば、どちらも作れないからだ。

2人は、この $lo g n$ が最悪の場合だと予想した。論文では、グラフに限らない形でも予想を述べている。有限の集合 $X$ の要素を確率 $p$ で選び、選んだ集合が性質 $F$ を持つ確率が1/2になる $p$ を $p_{c} (F)$ とする。数えるだけで分かる下限 $q (F)$ と比べて、 $p_{c} (F) \leq K q (F) lo g ∣ X ∣$ となる定数 $K$ がある、という主張である。

ギル・カライしきい値は数えるだけの見積もりのlog倍以内だと、カーンと予想した

2010年、ミシェル・タラグランは計算機科学の国際会議の論文で、この下限に使う条件を「 $p$ で小さい」と呼び、条件をゆるめた分数版の予想を出した。 $lo g ∣ X ∣$ を、性質を最小限に満たす集合の大きさ $ℓ (F)$ の $lo g$ に縮めた形である。2019年、キース・フランクストン、カーン、バルガヴ・ナラヤナン、パクがこの分数版を証明した。2022年にはパクとファムが、分数にしない元の予想を $lo g ℓ (F)$ の形で証明する。論文は2024年、『Journal of the American Mathematical Society』に載った。同じ年、2人は米国産業応用数理学会（SIAM）のデーネシュ・ケーニグ賞を受けている。

もっとも、2006年の論文には、グラフに絞ったもう1つの予想があった。部分グラフの期待値だけで決まる見積もりを使う、より強い主張である。2026年7月の国際数学者会議の時点でも、こちらは解けていない。

証明

安い被覆が見つからないとき

有限の集合 $X$ から、各要素を確率 $p$ で独立に選んだ集合を $X_{p}$ と書く。 $n$ 点のグラフなら、 $X$ は引ける $(2 n)$ 本の線である。性質 $F$ は、要素を足しても崩れない増加的な性質とする。 $X_{p}$ が $F$ を持つ確率 $μ_{p} (F)$ は $p$ とともに0から1まで増えるので、ちょうど1/2になる $p$ が1つ決まる。これがしきい値 $p_{c} (F)$ である。 $ℓ (F)$ は、 $F$ を最小限に満たす集合のうち最も大きいものの要素の数で、三角形なら3、全体がつながる性質なら $n - 1$ になる。ただし、2より小さいときは2とする。

集合の族 $G$ を、 $F$ のどの集合も $G$ のどれかを含むようにとり、被覆と呼ぶ。 $X_{p}$ が $F$ を持てば、 $G$ のどれかが $X_{p}$ に丸ごと入る。その個数の期待値で確率を押さえる
$μ_{p} (F) \leq S \in G \sum p^{∣ S ∣}$
全体がつながったグラフは、点vから出るn−1本のうち少なくとも1本を含む。この1本ずつの集合を並べた族は被覆で、費用は（n−1）pになる。
右辺を被覆の費用と呼ぶ。費用が1/2以下の被覆があるとき $F$ は「 $p$ で小さい」といい、そうなる最大の $p$ が期待値のしきい値 $q (F)$ である。手順1から、数えるだけの下限が出る
$q (F) \leq p_{c} (F)$
パクとファムは逆向きを示した。 $F$ を最小限に満たす集合の族を $H$ とし、 $H$ は $p$ で小さくない、つまりどの被覆も費用が1/2を超えるとする。 $n = ∣ X ∣$ 、 $L$ を大きな定数として、 $X$ から大きさ $w$ の集合 $W$ をでたらめに選ぶ
$w = L p n$
$H$ の集合 $S$ ごとに、 $W \cup S$ に含まれる $H$ の集合 $S^{'}$ のうち、 $W$ の外に出る部分 $S^{'} ∖ W$ が最も小さいものを選び、その部分を最小の断片 $T (S, W)$ とする。断片が大きい $S$ については断片を集めて被覆 $U (W)$ にし、小さい $S$ の断片は次の回に回す
$∣ T (S, W) ∣ \geq 0.9 ℓ \Rightarrow T (S, W) \in U (W)$
証明の要は、この被覆の費用を数える一歩にある。先に $Z = W \cup T$ を決め、 $Z$ に含まれる $H$ の集合 $S^$ を、 $Z$ だけを見て1つ選ぶ。 $T$ が最小の断片なので $T \subseteq S^$ となり、 $T$ は $S^$ の部分集合 $2^{ℓ}$ 通りのどれかに決まる。 $∣ T ∣ = m$ となる $(W, T)$ の組は高々 $(w + m n) 2^{ℓ} \leq (w n) (L p)^{- m} 2^{ℓ}$ 通りなので
$W \sum U \in U (W) \sum p^{∣ U ∣} \leq (w n) m \geq 0.9 ℓ \sum L^{- m} 2^{ℓ} < (w n) L^{- 0.8 ℓ}$
W ∪ Sに収まる集合のうち、Wからはみ出す部分が最も小さいもののはみ出しがT。Z = W ∪ Tに収まるどの集合Ŝも、Tを丸ごと含む。
両辺を $W$ の選び方の数 $(w n)$ で割ると、被覆の費用の期待値は $L^{- 0.8 ℓ}$ より小さい。断片は回ごとに0.9倍以下に縮むので、これを $lo g_{0.9} (1/ ℓ)$ 回ほどくり返し、選んだ集合を合わせる。 $C$ を定数として
$∣ W_{1} \cup \dots \cup W_{γ} ∣ \approx C L p n lo g ℓ$
集めた被覆が $H$ 全体を覆うか、合わせた集合が $H$ のどれかを含むかの、どちらかが必ず起きる。覆う場合は費用が1/2を超えるはずなので、マルコフの不等式から、その確率は小さい
$Pr (\sum_{U} p^{∣ U ∣} > \frac{1}{2}) \leq 2 E [\sum_{U} p^{∣ U ∣}] \to 0$
したがって、大きさ $C L p n lo g ℓ$ のでたらめな集合は、ほぼ確実に $F$ を持つ。 $p$ を $q (F)$ より少し大きくとり、大きさを決めた選び方を、確率 $K p lo g ℓ$ で1つずつ選ぶ選び方に置き換えると
$p_{c} (F) \leq K q (F) lo g ℓ (F)$

手順5の数え上げが、論文の中心にある補題の証明のほぼすべてである。証明全体も、arXivの第2版で8ページ、雑誌の版で9ページに収まる。ただ、定数 $K$ の値は、論文でも詰めていない。

途中の計算

孤立点が生むlog

$n$ 点のどの2点も確率 $p$ で結ぶグラフで、2つの形の境目を手で求める。 $n p$ は、1点から出る線の数の平均である。

三角形の数の期待値を書く
$E [X_{△}] = (3 n) p^{3} \approx \frac{( n p ) ^{3}}{6}$
期待値を1/2とおいて解く
$n p = 3^{1/3} \approx 1.44$
三角形の数をポアソン分布で近似する
$Pr (X_{△} \geq 1) \approx 1 - e^{- (n p)^{3} /6}$
確率を1/2とおいて解く
$n p = (6 ln 2)^{1/3} \approx 1.61$
1点が孤立する確率を書く
$(1 - p)^{n - 1} \approx e^{- n p}$
孤立点の数の期待値を書く
$E [X_{0}] = n (1 - p)^{n - 1} \approx n e^{- n p}$
期待値を1とおいて解く
$n p = ln n$

孤立点の数をポアソン分布で近似すると、孤立点が1つも無い確率は $e^{- n e^{- n p}}$ になる。点の数を100倍にすると、この曲線は $ln 100 \approx 4.6$ だけ右へずれる。

全域木の数の期待値をケイリーの公式で書く
$E [X_{tree}] = n^{n - 2} p^{n - 1}$
期待値を1/2とおき、 $n = 100$ で解く
$n p = 5 0^{1/99} \approx 1.04$

三角形では、期待値で見積もった1.44と、確率が1/2になる1.61の差は1.1倍にとどまる。しかし、全体がつながる性質では違う。エルデシュとレーニの結果から、 $n p = ln n + c$ のとき全体がつながる確率は $e^{- e^{- c}}$ に近づく。これを1/2とおくと $c = - ln ln 2 \approx 0.37$ で、 $n = 100$ なら $n p \approx 4.97$ と見積もれる。全域木の期待値で見積もった1.04の4.8倍で、 $ℓ = 99$ の $ln$ 、4.6とほぼ同じ大きさだ。全域木はいくらでもあるのに、孤立点が1つ残るだけで、全体はつながらない。

応用

全員に届くゴシップの送り先

大きな分散システムでは、1つの知らせを全部の計算機に配るのに、ゴシップと呼ぶ方式を使うことがある。知らせを受け取った計算機が、でたらめに選んだ何台かに転送していく。では、1台あたり何台に送れば、全員に届くのだろうか。

2003年、アンヌ＝マリー・ケルマレック、ロラン・マスリエ、アヤルヴァディ・ガネーシュは、この問いを、矢印でつなぐランダムグラフで解いた。 $n$ 台のどの2台の間にも確率 $p$ で送り先の矢印を引くとき、 $p = (ln n + c) / n$ なら、最初の1台から全員に届く確率は $e^{- e^{- c}}$ に近づく。1台あたりの送り先の平均は $n p = ln n + c$ である。

$n = 10, 000$ 台で計算してみる。 $ln n \approx 9.21$ なので、全員に届く確率を99%にするには $c \approx 4.60$ 、送り先は1台あたり約13.8台になる。95%でよければ約12.2台で済む。送り先が平均1台なら、どの台も平均1通は受け取る計算になるが、どこからも選ばれない台が平均 $n e^{- 1}$ 台、約3,700台残る。矢印が確率 $ε$ で切れるなら $p$ を $1 - ε$ で割ればよいことも、3人は示した。切れる割合が10%なら、99%に要る送り先は約15.3台に増える。

つまり、送り先が $ln n$ とともに増えるのは、どこからも選ばれない台が最後まで残るからだ。数えるだけの見積もりなら1台あたり1台ほどで足りそうに見えるが、本当に要る数はその $ln n$ 倍になる。パクとファムの定理によれば、どんな増加的な性質でも、この開きは $K lo g ℓ$ 倍を超えない。

例題と解説

期待値と確率のずれを測る

例題 1基本線と三角形の期待値

10点のどの2点も、確率0.3で独立に線で結ぶ。

（1）線の本数の期待値を求めよ。

（2）三角形の数の期待値を求めよ。

解説を見る

（1）2点の組は $(2 10) = 45$ 組で、どの組も確率0.3で線になる。

45 \times 0.3 = 13.5

（2）3点の組は $(3 10) = 120$ 組で、3本とも引かれる確率は $0. 3^{3} = 0.027$ である。期待値の線形性から次のとおり。

120 \times 0.027 = 3.24

三角形どうしが線を共有していても、期待値は組ごとの確率を足すだけで求まる。

例題 2入試確率を期待値で上から押さえる

20点のどの2点も、確率 $p$ で独立に線で結び、三角形の数を $X$ とする。

（1） $Pr (X \geq 1) \leq E [X]$ を示せ。

（2） $p = 0.05$ のとき、三角形が1つ以上ある確率は0.15未満であることを示せ。

（3） $E [X] = \frac{1}{2}$ となる $p$ を求めよ。

解説を見る

（1） $X$ は0以上の整数なので、次のように押さえられる。

Pr (X \geq 1) = k \geq 1 \sum Pr (X = k) \leq k \geq 1 \sum k Pr (X = k) = E [X]

（2） $(3 20) = 1, 140$ なので、（1）から次のとおり。

E [X] = 1, 140 \times 0.0 5^{3} = 0.1425 < 0.15

（3） $1, 140 p^{3} = \frac{1}{2}$ を解く。

p = (\frac{1}{2 , 280})^{1/3} \approx 0.0760

これより小さい $p$ では、三角形が現れる確率は1/2に届かない。三角形の全体を被覆にとった、証明の手順1と同じ評価である。

例題 3難関孤立点の期待値と全域木の期待値

100点のどの2点も、確率 $p = 0.02$ で独立に線で結ぶ。

（1）決まった1点が孤立する確率を、小数第3位まで求めよ。

（2）孤立点の数の期待値を求めよ。

（3）全域木の数の期待値が $1 0^{27}$ を超えることを示せ。 $n$ 点の全域木が $n^{n - 2}$ 通りあること（ケイリーの公式）を使ってよい。

解説を見る

（1）ほかの99点のどれとも結ばれない確率である。

0.9 8^{99} = e^{99 l n 0.98} \approx e^{- 2.000} \approx 0.135

（2）100点それぞれの確率を足す。

100 \times 0.9 8^{99} \approx 13.5

（3）全域木は99本の線からなるので、1つの全域木がそろう確率は $0.0 2^{99}$ である。

lo g_{10} (10 0^{98} \times 0.0 2^{99}) = 196 + 99 lo g_{10} 0.02 \approx 196 - 168.2 = 27.8

期待値は約 $1 0^{27.8}$ で、 $1 0^{27}$ を超える。それでも孤立点が平均13.5個あるので、全体がつながっていることはまずない。

例題 4大学チェビシェフの不等式で押さえる

例題3と同じグラフで、孤立点の数を $X_{0}$ とする。

（1）異なる2点 $u$ , $v$ がともに孤立する確率を求めよ。

（2） $X_{0}$ の分散を求め、チェビシェフの不等式で $Pr (X_{0} = 0)$ を上から押さえよ。

（3）全体がつながる確率は0.1未満であることを示せ。

解説を見る

（1） $u$ と $v$ からそれぞれ残りの98点への線と、 $u$ と $v$ を結ぶ線の、合わせて197本がどれも引かれない。

0.9 8^{197} \approx 0.0187

（2） $X_{0}$ は、各点が孤立するとき1になる量の和なので、2乗の期待値は $E [X_{0}]$ に、異なる2点の組 $100 \times 99$ 通りの確率を足したものになる。

E [X_{0}^{2}] = 13.53 + 9, 900 \times 0.01869 \approx 198.5

Var (X_{0}) = 198.5 - 13.5 3^{2} \approx 15.4

$X_{0} = 0$ なら、期待値から13.53以上離れている。

Pr (X_{0} = 0) \leq \frac{Var ( X _{0} )}{13.5 3 ^{2}} \approx 0.084

（3）全体がつながっていれば孤立点は無いので、その確率は $Pr (X_{0} = 0)$ 以下、つまり0.1未満である。全域木の数の期待値が $1 0^{27}$ を超えるのは、全域木が、まれにしか起きない線の多いグラフにまとめて現れるからだ。

例題 5大学被覆を2つ作って費用を比べる

10点を2点ずつ5組に分け、各組を線で結んだものを完全マッチングと呼ぶ。10点のグラフが完全マッチングを含む、という性質を $F$ とする。

（1）1点 $v$ から出る9本の線を、1本ずつの集合にして並べた族 $G_{1}$ は $F$ の被覆であることを示し、費用が1/2以下になる $p$ の範囲を求めよ。

（2）完全マッチング全体の族 $G_{2}$ について、費用が1/2以下になる $p$ の範囲を求めよ。10点の完全マッチングは945通りある。

（3） $q (F)$ について、何がいえるか。

解説を見る

（1）完全マッチングでは $v$ もどこかの点と組になるので、 $v$ から出る線を1本は含む。費用は $9 p$ である。

9 p \leq \frac{1}{2} ⟺ p \leq \frac{1}{18} \approx 0.056

（2）完全マッチングは5本の線からなるので、費用は $945 p^{5}$ である。

945 p^{5} \leq \frac{1}{2} ⟺ p \leq (\frac{1}{1 , 890})^{1/5} \approx 0.221

（3） $G_{2}$ も被覆なので、 $F$ は $p \leq 0.221$ で小さい。したがって $q (F) \geq 0.221$ である。 $q$ は、ありとあらゆる被覆のうち、最も大きな $p$ まで費用を1/2以下に保てるものを使って決まる。

図示

開き方は形で決まる

期待値が1/2になるnp（破線）と、確率が1/2になるnp（実線）を対数目盛りで並べた。三角形では2本がほぼ重なり、全体がつながる性質では、点の数が増えるほど離れる。

三角形の2本は、点の数を大きくしたときの極限の値で、点の数によらない。全体がつながる性質では、破線は1のあたりから動かず、実線だけが $ln n + 0.37$ に沿って右へ逃げていく。開きは1万点で9.6倍、100万点で14倍になり、 $ℓ = n - 1$ の $ln$ 、9.2と13.8に近い。

シミュレーション

線を1本ずつ足す

線ごとに乱数を1つ決めておき、 $n p$ のつまみを上げると、乱数が $p$ より小さい線が順に現れる。曲線は、同じ点の数で作った300個のランダムグラフのうち、その形を持つものの割合で、乱数で作った1例である。破線は期待値が1/2になる位置、実線は割合が1/2を超える位置を示す。破線はその点の数で計算した値なので、手で求めた極限の1.44などとは少しずれる。形を「全体がつながる」に切り替えて点の数を10から60まで動かすと、2本の比は $ln (n - 1)$ とほぼ同じ速さで伸びる。

広がる学問

臨界確率を見積もる学問

数学ランダムグラフやランダムハイパーグラフに決まった構造が現れる確率の境目を、数え上げから求めるときに使う。 $n$ 個の点から3点ずつの組をでたらめに選ぶとき、全部の点をちょうど1回ずつ覆う組の集まりが現れる境目は、 $n^{- 2} lo g n$ の程度である。2008年にヨハンソン、カーン、ヴーが難しい証明で示したこの結果は、今ではフランクストンらの定理と完全マッチングの数え上げから短く出る。
情報科学 単調なブール関数が1を返す確率が、入力の各ビットを1にする確率 $p$ とともにどこで1/2を超えるかを、見積もるときに使う。増加的な性質は単調なブール関数そのもので、被覆は、変数の論理積を論理和でつないだ単調な選言標準形（DNF）にあたる。パクとファムの定理は、 $p$ が $p_{c} / (K lo g ℓ)$ より小さければ、真になる項の数の期待値が1/2以下のDNFで、その関数を上から押さえられると言い換えられる。
物理学 格子の辺を確率 $p$ で残すボンドパーコレーションで、端から端までつながる確率が急に立ち上がる臨界確率を調べるときに、同じ「増加的な性質のしきい値」の枠組みを使う。正方格子の臨界確率がちょうど1/2になることを、ハリー・ケステンが1980年に証明した。カーンとカライの2006年の論文も、確率を $p$ で微分すると各辺の影響の和になるというルッソの公式を、しきい値を調べる道具に挙げている。

いまの研究と事業

残った第2の予想

2022年ジェイン（イリノイ大学シカゴ校）とファム（スタンフォード大学）： $n$ 行 $n$ 列のマスに $n$ 種類の記号を、どの行と列にも1回ずつ入れたものがラテン方陣である。行と列と記号の三つ組を確率 $p$ ででたらめに選ぶとき、その中にラテン方陣が現れる境目を $Θ (lo g n / n)$ と決めた。キーヴァッシュも独立に示している。ラテン方陣の集まりの上に、どの三つ組の集まりにも偏らない確率分布を作り、パクとファムの定理 $p_{c} \leq K q lo g ℓ$ に当てはめた。出典はarXiv:2212.06109とパクの国際数学者会議の論文。
2025年ダブロフ（カーネギーメロン大学）、カーン（ラトガース大学）、パク（ニューヨーク大学）：2006年の論文に残った第2の予想に取り組んだ。部分グラフの期待値だけで決まる見積もり $p_{E} (H)$ を使い、 $p_{c} (H) = O (p_{E} (H) lo g n)$ と予想する強い形である。3人はこれを $O (p_{E} (H) lo g^{3} n)$ まで詰めた。 $H$ がまばらで $p_{E} (H) < 1/ (3 n)$ となる場合には、予想どおりの形を示している。出典はarXiv:2508.14269。
2026年ディスキンとクライトナー：カライが4月にブログで始めた、人とAIが一緒に考える共同研究で、6月に2006年の論文の予想7への反例を寄せた。予想7は、ルッソの公式で書いた不等式 $p μ_{p}^{'} (F) \geq μ_{p} (F) lo g_{p} μ_{p} (F)$ について、どの $C$ にも小さな $ε$ があり、 $ε p_{c} / lo g n$ から $p_{c}$ までのどこかで、左辺が右辺の $C lo g (1/ p)$ 倍以内に収まるという主張で、カーン＝カライ予想を示すために2人が描いた道筋の一部だった。カライによると、反例はChatGPT 5.5 Proを使って組み立て、証明支援系Leanでも確かめた。8月のブログでカライは、予想7も反証されたと記した。出典は共同研究のページと8月1日の記事。
2026年パク（ニューヨーク大学）：7月、フィラデルフィアの国際数学者会議の招待講演「しきい値」で、残る問題をまとめた。タラグランの離散凸性予想もその中にある。ある定数 $k$ があって、 $μ_{p} (A) \geq 3/4$ となる族 $A$ なら、 $A$ のどの $k$ 個の和集合にも含まれない集合の族 $A^{(k)}$ は $p$ で小さい、という主張である。パクとファムの定理は $k = 1$ で $p$ を $lo g ℓ$ の分だけ小さくした形にあたり、タラグランは、この予想を「生涯でいちばん好きな問題」と呼んで1,000ドルの賞金をかけている。出典は講演の論文。

参考文献

J. Kahn, G. Kalai, "Thresholds and expectation thresholds", Combin. Probab. Comput. 16(3) (2007), 495-502 (arXiv:math/0603218, 2006).
J. Park, H. T. Pham, "A proof of the Kahn-Kalai conjecture", J. Amer. Math. Soc. 37 (2024), 235-243 (arXiv:2203.17207, 2022).
K. Frankston, J. Kahn, B. Narayanan, J. Park, "Thresholds versus fractional expectation-thresholds", Ann. of Math. 194(2) (2021), 475-495 (arXiv:1910.13433, 2019); M. Talagrand, "Are many small sets explicitly small?", Proc. 42nd ACM Symposium on Theory of Computing (2010), 13-36.
P. Erdős, A. Rényi, "On random graphs I", Publ. Math. Debrecen 6 (1959), 290-297; P. Erdős, A. Rényi, "On the evolution of random graphs", Publ. Math. Inst. Hung. Acad. Sci. 5 (1960), 17-61; B. Bollobás, A. Thomason, "Threshold functions", Combinatorica 7 (1987), 35-38.
J. Park, "Thresholds", Proceedings of the International Congress of Mathematicians 2026, Vol. 6 (2026), 199-211; G. Kalai, "Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!", Combinatorics and more (2 April 2022); G. Kalai, "ICM 2026: A Magical Saturday Afternoon with Park, Braden and Proudfoot, and Meka", Combinatorics and more (1 August 2026); T. White, "Math Magic", Stanford Magazine (July 2022).
A.-M. Kermarrec, L. Massoulié, A. J. Ganesh, "Probabilistic reliable dissemination in large-scale systems", IEEE Trans. Parallel Distrib. Syst. 14(3) (2003), 248-258.
H. Kesten, "The critical probability of bond percolation on the square lattice equals 1/2", Commun. Math. Phys. 74 (1980), 41-59; V. Jain, H. T. Pham, "Optimal thresholds for Latin squares, Steiner Triple Systems, and edge colorings", arXiv:2212.06109 (2022); Q. Dubroff, J. Kahn, J. Park, "On the second Kahn-Kalai Conjecture", arXiv:2508.14269 (2025).

カーン＝カライ予想

提案した2人が疑った予想

1960年の「意外な結果」

安い被覆が見つからないとき

孤立点が生むlog

全員に届くゴシップの送り先

期待値と確率のずれを測る

例題 1基本線と三角形の期待値

例題 2入試確率を期待値で上から押さえる

例題 3難関孤立点の期待値と全域木の期待値

例題 4大学チェビシェフの不等式で押さえる

例題 5大学被覆を2つ作って費用を比べる

開き方は形で決まる

線を1本ずつ足す

臨界確率を見積もる学問

残った第2の予想

参考文献

タグ

同じタグを持つ公式

姉妹サイト