OpenAIのAIが証明した「完全グラフの交差数の公式」：トゥラーンのレンガ工場問題とハラリー・ヒル予想

この記事の要点

交差数: グラフ（点と、点どうしを結ぶ線）を平面に描いたとき、線どうしの交点の数の最小値です。どんなに曲がった線を使ってもよい、という条件で最小をとります。
問題の起源: 1944年、戦時下のレンガ工場で働いていたトゥラーンが、窯と置き場を結ぶ線路の交差を減らせないかと考えたのが始まりです。窯 $m$ 個と置き場 $n$ 個のすべての組を結ぶ図は完全2部グラフ $K_{m,n}$ と呼ばれます。
予想されていた公式: $K_{m,n}$ にはザランキエヴィッチの公式、 $n$ 個の点をすべて結んだ完全グラフ $K_n$ にはハラリーとヒルの公式がありました。どちらも、それだけの交点で描ける描き方はありましたが、それより少なくできないことは、片方の組が6個以下の場合、頂点の少ない場合、描き方を限った場合など、一部しか分かっていませんでした。
今回の結果: OpenAIのモデルが書いた2本の論文が、どちらの公式も正しいと証明しました。古典的な描き方が、すべての描き方の中で最適だったことになります。
確かさ: 2つの主定理はどちらもLeanで形式化され、リポジトリの照合の対象になっています。論文は査読前のプレプリントです。

この記事で読む論文（2本）

The crossing number of complete graphs

OpenAI　2026年9月23日付　プレプリント（査読前）　PDF 353KB　13ページ

The crossing number of complete bipartite graphs

OpenAI　2026年9月23日付　プレプリント（査読前）　PDF 397KB　16ページ

完全グラフの論文（PDF）完全2部グラフの論文（PDF） GitHubで見る（LaTeXソース・BibTeX） Leanの形式化の範囲を見る

PDFは2026年10月9日にGitHubから取得した版のコピーで、Apache License 2.0（全文）に従って掲載しています。完全2部グラフの論文のソースはこちらです。修正版が出た場合は、GitHubのほうが新しくなります。

定義・命題の下の「証明」は、開くとステップが並びます。もう少し詳しくは大学1〜2年程度の数学の補足、専門的な話は論文の中身に踏み込む補足です。どちらも開かずに読み進められます。図2〜4は、指やマウスで動かせます。

レンガ工場の線路から始まった問題が解けた

2026年10月6日、OpenAIは未公開の社内モデルが書いた数学の論文をGitHubのリポジトリ openai/math で公開しました^[1]。リポジトリの一覧で165番に分類されているのが、この記事で読む2本の論文です^[2,3]。

テーマは、点と線でできた図を平面に描いたとき、線どうしの交差をどこまで減らせるかという問題です。一覧の紹介文は、ハラリー・ヒル予想と、トゥラーンのレンガ工場問題（ザランキエヴィッチの定式化）を解決し、古典的な描き方が、辺を連続な曲線で描くすべての描き方の中で最適だと証明した、とまとめています。

問題そのものは、中学生でも意味が分かります。この記事では、まず交差数を正確に定義し、小さい場合を自分の手で確かめます。次に、予想されていた公式とそれを実現する描き方を、交点を数えながら動かせる図で見ます。最後に、今回の証明がどんな考え方で「これより減らせない」を示したかを紹介します。

2本の論文は、10月7日付の修正・取り下げには含まれていません。リポジトリの更新は修正と取り下げの記録にまとめています。

グラフを平面に描く

この記事の「グラフ」は関数のグラフではなく、点と、点どうしを結ぶ線でできた図のことです。点を頂点、線を辺と呼びます。

定義1 グラフ、完全グラフ、完全2部グラフ

有限集合 $V$ と、 $V$ の2元部分集合の集合 $E$ の組 $G=(V,E)$ をグラフという。 $V$ の元を頂点、 $E$ の元を辺と呼ぶ。

(1)　 $n$ 個の頂点のすべての2つ組を辺にしたグラフを完全グラフといい、 $K_n$ と書く。辺の数は $\binom n2$ である。
(2)　頂点を $m$ 個の組 $\{a_1,\dots,a_m\}$ と $n$ 個の組 $\{b_1,\dots,b_n\}$ に分け、 $a_i$ と $b_p$ を結ぶ $mn$ 本だけを辺にしたグラフを完全2部グラフといい、 $K_{m,n}$ と書く。

たとえば $K_4$ は4頂点と $\binom42=6$ 本の辺、 $K_{3,3}$ は6頂点と $3\times3=9$ 本の辺をもちます。 $K_{m,n}$ では、同じ組の頂点どうしは結びません。

グラフを平面に描くときは、頂点を点に、辺を2点を結ぶ曲線にします。曲線の通り道は自由に選べます。今回の論文は、描画を次のように定めています[2, §1; 3, §1]。

定義2 描画と交差数

グラフ $G$ の描画とは、頂点を平面の相異なる点に置き、各辺を、その両端を結ぶ連続な曲線（自分自身とは交わらない）で表したもので、次をみたすものをいう。

(a)　辺の内部（両端を除いた部分）は頂点を通らない。
(b)　2本の辺の内部は有限個の点でしか出会わず、どの出会う点でも2本はきちんと横切る（接するだけ、重なる、3本が1点で出会う、は許さない）。

辺の内部どうしが出会う点を交点と呼ぶ。描画 $D$ の交点の数を $c(D)$ と書く。同じ2本の辺が何回も交わるときは、交点をすべて数える。グラフ $G$ の交差数を次で定める。

\operatorname{cr}(G)=\min_{D}\,c(D)\qquad(D\text{ は }G\text{ の描画全体を動く})

\begin{gathered}\operatorname{cr}(G)=\min_{D}\,c(D)\\(D\text{ は }G\text{ の描画全体を動く})\end{gathered}

\begin{aligned}\operatorname{cr}(G) &= \min_{D}\,c(D)\\[4pt]&(D\text{ は }G\text{ の描画全体を動く})\end{aligned}

頂点をどこに置くか、辺をどう曲げるかに制限はありません。辺を直線に限る、辺どうしの交わり方に条件をつける、といった変種もありますが、この記事で「交差数」と言えばこの定義の $\operatorname{cr}(G)$ です。

交点 1 個

交点 0 個

図1具体例

K_4

の2つの描画です。左は正方形と2本の対角線で、対角線どうしが1回交わります（赤丸）。右は対角線の1本を外側に回したもので、交点がありません。よって

\operatorname{cr}(K_4)=0

です。

図1のように、描き方を変えると交点の数は変わります。交差数は、いちばんうまく描いたときの交点の数です。交点が $0$ 個の描画をもつグラフは平面グラフと呼ばれます。

もう少し詳しく「交点を数える」と「交わる辺の組を数える」の違い

同じ2本の辺が3回交わっていれば、 $c(D)$ には $3$ が入ります。これとは別に、「交わる辺の組の数」や「奇数回交わる辺の組の数」の最小値を考える変種もあり、一般のグラフではどれが同じになるかが研究されています^[4]。

今回の2本の論文は、どちらも交点をすべて数える上の定義で証明しています[2, §1]。Leanの形式化でも、交点は平面上の点の集合として数えられ、同じ2本の辺の何回もの交わりは別々に数えられます^[5]。

小さいグラフの交差数

交差数を決めるには、2つのことを示す必要があります。ある描画で交点が $k$ 個になること（ $\operatorname{cr}(G)\le k$ ）と、どんな描画でも $k$ 個以上になること（ $\operatorname{cr}(G)\ge k$ ）です。前者は描いてみせれば済みますが、後者は「すべての描き方」について言う必要があり、こちらが難しい部分です。

小さいグラフなら、後者はオイラーの多面体公式から示せます。

おさらいオイラーの多面体公式

連結なグラフを交点なしで平面に描くと、平面は辺によっていくつかの領域（面）に分かれます。外側の無限に広い領域も1つの面に数えます。頂点・辺・面の数を $v,e,f$ とすると、次が成り立ちます。

v-e+f=2

\begin{aligned}v-e+f &= 2\end{aligned}

たとえば図1の右の $K_4$ では $v=4,\ e=6$ で、面は内側の3つと外側の1つなので $f=4$ 、 $4-6+4=2$ です。

命題3 平面グラフの辺の数

$G$ を頂点が3個以上の平面グラフとし、頂点の数を $v$ 、辺の数を $e$ とする。

(1)　 $e\le 3v-6$ である。
(2)　 $G$ が2部グラフ（頂点を2組に分けて、辺がいつも組をまたぐようにできるグラフ）なら、 $e\le 2v-4$ である。

証明

$G$ が連結な場合に示せば十分である。

連結でなければ、交点を作らずに2つの成分を結ぶ辺を足せる（同じ面に接している2つの成分の頂点を、その面の中で結べばよい）。2部グラフなら、足す辺が組をまたぐように選べる。辺を足すと $e$ は増え $v$ は変わらないので、足したあとのグラフで不等式を示せば元のグラフでも成り立つ。
交点なしの描画をとり、面の数を $f$ とする。各面の境界を一周すると、辺を3本以上通る（同じ辺を2回通るときは2回と数える）。

辺が1本だけ、または2本で囲まれた面は、ループや2重の辺がないグラフでは作れない。頂点が3個以上で連結なら、面の境界は3本以上の辺を通る。
各辺は、面の境界の周回に合わせて2回まで現れる。よって、面ごとに境界の辺を数えて足すと $3f\le 2e$ となる。
オイラーの公式 $f=2-v+e$ を代入すると $3(2-v+e)\le 2e$ 、つまり $e\le3v-6$ である。これで (1) が示せた。
(2) を示す。2部グラフには奇数本の辺で一周する道がないので、面の境界は4本以上の辺を通り、 $4f\le 2e$ となる。オイラーの公式を代入して $e\le 2v-4$ を得る。

命題4 オイラーの公式から出る下界

頂点が3個以上のグラフ $G$ の頂点の数を $v$ 、辺の数を $e$ とすると

\operatorname{cr}(G)\ge e-(3v-6)

\begin{aligned}\operatorname{cr}(G) &\ge e-(3v-6)\end{aligned}

$G$ が2部グラフなら $\operatorname{cr}(G)\ge e-(2v-4)$ である。

証明

交点が $c=\operatorname{cr}(G)$ 個の描画 $D$ をとる。
交点を1つ選び、そこを通る辺の1本を消す。これを交点がなくなるまでくり返すと、消す辺は $c$ 本以下で済む。

辺を1本消すと、その辺を通る交点はすべて消え、ほかの交点は残る。選んだ交点は必ず消えるので、1回ごとに交点は1つ以上減る。よって $c$ 回以内で交点がなくなる。
残ったグラフは平面グラフで、辺が $e-c$ 本以上ある。命題3(1) から $e-c\le 3v-6$ 、つまり $c\ge e-(3v-6)$ である。2部グラフなら、消したあとも2部グラフなので命題3(2) を使う。

これを小さい完全グラフ・完全2部グラフに当てはめると、次のようになります。

\begin{aligned} \operatorname{cr}(K_5)&\ge 10-(15-6)=1\\ \operatorname{cr}(K_6)&\ge 15-(18-6)=3\\ \operatorname{cr}(K_{3,3})&\ge 9-(12-4)=1\\ \operatorname{cr}(K_{3,4})&\ge 12-(14-4)=2\end{aligned}

どれも、この数ちょうどの交点で描けます（図2で試せます）。したがって、次の値が確定します。

例5 小さいグラフの交差数

$\operatorname{cr}(K_5)=1,\quad \operatorname{cr}(K_6)=3,\quad \operatorname{cr}(K_{3,3})=1,\quad \operatorname{cr}(K_{3,4})=2.$

交点：5 個（最小は 1 個）　まだ減らせます。頂点を動かしてみてください。

図2具体例頂点をドラッグして、交点（赤丸）を減らしてみる図です。辺はいつも直線で描かれ、交点の数はその場で数え直されます。

K_{3,3}

と

K_{3,4}

では、橙が窯、青が置き場です（次の節）。どのグラフも直線のままで最小の数まで減らせますが[6, p.55]、それより少なくはできません。曲線を使っても減らせないことは命題4が保証しています。

この方法には限界があります。 $K_7$ に当てはめると $21-(21-6)=6$ ですが、本当の交差数は $9$ です。頂点が増えるほど差は広がり、 $K_n$ では下界がおよそ $n^2/2$ なのに対し、予想される値はおよそ $n^4/64$ です。

オイラーの公式は「交点を消して平面グラフにする」ことしか見ていません。交点がどこに、どう入り組んで現れるかまで調べないと、大きなグラフの交差数は決まらないのです。

トゥラーンのレンガ工場

この問題の始まりは、ハンガリーの数学者トゥラーンの短い文章に記されています。トゥラーンは1976年9月26日に亡くなり、この文章は1977年に掲載されました[7, pp.7–9]。トゥラーンは1940年9月に初めて労働奉仕の部隊に召集されました。この文章では、戦争中を人生でいちばん苦しい時期だったと振り返っています。1944年7月には、ブダペスト近くのレンガ工場で働いていました。

工場にはレンガを焼く窯がいくつかと、レンガを置く置き場がいくつかあり、すべての窯がすべての置き場と線路で結ばれていました。レンガを積んだ小さな台車を押して運ぶのですが、線路が交差する場所で台車が脱線し、レンガが落ちて時間を失いました。トゥラーンは、線路の交差の数を最小にすればこの損失を減らせたはずだと考え、では最小はいくつか、と問いました[7, p.8]。

窯を $a_1,\dots,a_m$ 、置き場を $b_1,\dots,b_n$ とすると、線路の図はちょうど完全2部グラフ $K_{m,n}$ です。トゥラーンの問いは、 $\operatorname{cr}(K_{m,n})$ を求めることになります。

ザランキエヴィッチの描き方

トゥラーンは1952年にポーランドを訪れた際、この問題をザランキエヴィッチに話しました[7, p.8]。ザランキエヴィッチは、次の描き方を示しました[8; 6, p.55]。窯を縦の軸の上下に、置き場を横の軸の左右に、それぞれできるだけ半分ずつ並べ、すべての組を線分で結びます。

窯

m

4 置き場

n

$K_{m,n}$ （ $m=$ 4、 $n=$ 5）の交点を数えると 8 個。公式では $\lfloor\tfrac m2\rfloor\lfloor\tfrac{m-1}2\rfloor\lfloor\tfrac n2\rfloor\lfloor\tfrac{n-1}2\rfloor=$ 2 $\times$ 1 $\times$ 2 $\times$ 2 $=$ 8 です。

図3具体例ザランキエヴィッチの描画です。橙の四角が窯、青の丸が置き場、赤丸が交点です。スライダーで

m,n

を

1

から

8

まで変えられます。交点は描いた線分どうしの交わりを実際に計算して求めたもので、64通りすべてで公式の値と一致することを、記事の生成時に確かめています。3本の線分が1点で交わらないように、頂点の間隔を少し不ぞろいにしています。

交点を数えると、次の公式が出てきます。以下、 $\lfloor x\rfloor$ は $x$ 以下の最大の整数です。

命題6 ザランキエヴィッチの描画の交点の数 [3, §5.1]

$d_r=\lfloor r/2\rfloor\lfloor (r-1)/2\rfloor$ とおく。ザランキエヴィッチの描画の交点の数は $d_md_n$ である。とくに

\begin{aligned} \operatorname{cr}(K_{m,n})&\le Z(m,n)\\ &:=\left\lfloor\frac m2\right\rfloor\left\lfloor\frac{m-1}2\right\rfloor\\ &\phantom{{}:={}}\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}2\right\rfloor\end{aligned}

証明

どの辺も、軸で区切られた4つの象限のどれか1つの中を通る。異なる象限の辺は交わらないので、象限ごとに数えればよい。
ある象限を囲む縦の半直線に窯が $u$ 個、横の半直線に置き場が $v$ 個あるとする。この象限の交点の数は $\binom u2\binom v2$ である。

窯を2つ $a,a'$ （ $a$ が中心に近い）、置き場を2つ $b,b'$ （ $b$ が中心に近い）選ぶと、4点は凸な四角形を作り、その2本の対角線 $ab'$ と $a'b$ だけが交わる。逆に、交わる2本の線分は端点が4つとも異なり、こうして選んだ4点の対角線になっている。

3本の線分が1点で交わらないように頂点の位置を選んでおけば、選び方1つにつき交点がちょうど1つになる。
窯は上に $\lceil m/2\rceil$ 個、下に $\lfloor m/2\rfloor$ 個、置き場は右に $\lceil n/2\rceil$ 個、左に $\lfloor n/2\rfloor$ 個ある。4つの象限を足すと次のようになる。 $\begin{aligned} &\left(\binom{\lceil m/2\rceil}2+\binom{\lfloor m/2\rfloor}2\right)\\ &\quad\times\left(\binom{\lceil n/2\rceil}2+\binom{\lfloor n/2\rfloor}2\right)\\ &=d_md_n\end{aligned}$

最後の等式は $\binom{\lfloor r/2\rfloor}2+\binom{\lceil r/2\rceil}2=d_r$ による。 $r=2t$ なら左辺は $2\binom t2=t(t-1)=\lfloor r/2\rfloor\lfloor(r-1)/2\rfloor$ 、 $r=2t+1$ なら $\binom t2+\binom{t+1}2=t^2$ で、これも $d_{2t+1}=t\cdot t$ に等しい。

たとえば $K_{4,5}$ では、窯が上下に $2$ 個ずつ、置き場が右に $3$ 個・左に $2$ 個です。象限ごとの交点は $\binom22\binom32=3$ が2つと $\binom22\binom22=1$ が2つで、合計 $8=d_4d_5=2\times4$ です。図3の初期状態がこれです。

証明の穴

ザランキエヴィッチは、この描画が最適である、つまり $\operatorname{cr}(K_{m,n})=Z(m,n)$ だと証明したと考え、Fundamenta Mathematicae の第41巻に発表しました^[8]。同じころウルバニクも同じ主張を発表しています^[9]。しかし、のちにリンゲルとケイネンがそれぞれ独立に証明の穴を見つけました[6, p.55]。

トゥラーンも上の文章で、リンゲルが穴を見つけ、それ以来だれも埋められていない、と書いています[7, pp.8–9]。こうして次の主張は、ザランキエヴィッチ予想と呼ばれる未解決問題になりました。

予想7 ザランキエヴィッチ [6, p.55; 3, §1]

すべての正の整数 $m,n$ について $\operatorname{cr}(K_{m,n})=Z(m,n)$ 。

その後に分かっていたことは、主に次のとおりです。

$\min(m,n)\le 2$ なら $Z(m,n)=0$ で、自明に成り立ちます。 $\min(m,n)=3$ の場合は、ザランキエヴィッチが示していました[6, p.55]。
1970年にクライトマンが、 $\min(m,n)\le 6$ のすべての場合を証明しました[10; 6, p.55]。
1993年にウッドオールが、計算機を使って $K_{7,7}$ と $K_{7,9}$ の場合を確かめました[11; 3, §1]。
漸近的には、 $\operatorname{cr}(K_{n,n})\ge 0.9118\,d_n^2+o(n^4)$ まで分かっていました[12; 3, §1]。予想の値 $d_n^2$ の約91%です。

完全グラフとハラリー・ヒル予想

完全グラフ $K_n$ の交差数の問題は、1950年代の終わりにイギリスの芸術家アンソニー・ヒルが考えたのが最初とされています[13, arXiv版 p.1]。ヒルは、次の公式の数だけ交点をもつ $K_n$ の描き方を見つけました。

\begin{aligned} Z(n)&:=\frac14\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}2\right\rfloor\\ &\phantom{{}:={}\frac14}\left\lfloor\frac{n-2}2\right\rfloor\left\lfloor\frac{n-3}2\right\rfloor\end{aligned}

ハラリーとヒルは1963年の論文でヒルの構成を説明し、次を予想しました[14; 2, §1]。

予想8 ハラリー・ヒル [14; 2, §1]

すべての $n\ge3$ について $\operatorname{cr}(K_n)=Z(n)$ 。

これがハラリー・ヒル予想（ヒル予想とも呼ばれます）です。ハラリーとヒルは、上界を最初に発表したのは1960年のガイだとしています[2, §1]。

$n$ を奇数と偶数に分けると、次の形になります[2, (1.1)]。

Z(2s+1)=\binom s2^{\!2}\qquad Z(2s)=\frac{s(s-1)^2(s-2)}4

\begin{gathered}Z(2s+1)=\binom s2^{\!2}\\Z(2s)=\frac{s(s-1)^2(s-2)}4\end{gathered}

\begin{aligned}Z(2s+1) &= \binom s2^{\!2}\\[4pt]Z(2s) &= \frac{s(s-1)^2(s-2)}4\end{aligned}

たとえば $Z(7)=\binom32^2=9$ 、 $Z(8)=4\cdot3^2\cdot2/4=18$ です。

$Z(n)$ 個の交点をもつ描き方は、少なくとも3通り知られています[13, arXiv版 p.2]。ヒルの描き方は円筒の描画の一種です。円筒の描画とは、頂点を2つの同心円の上に置き、どの辺も円を横切らないように描いたものです。円筒の描画なら必ず交点が $Z(n)$ 個になる、というわけではありません。ヒルの描き方では、頂点を2つの円に半分ずつ置きます。円筒の上下のふたの縁に頂点を並べ、ふたの上と側面に辺を引いたものを、平面に広げた形です。

ブラジェクとコマンの描き方は2ページの描画です[15; 13, arXiv版 p.2]。頂点をすべて1本の直線の上に並べ、各辺を直線の上側か下側のどちらかに描きます。今回の論文は、この2ページの描画の一種を使って上界を示しています[2, §5]。

n

$K_n$ （ $n=$ 7）の交点を数えると 9 個。公式では $Z(n)=\tfrac14\times$ 3 $\times$ 3 $\times$ 2 $\times$ 2 $=$ 9 です。

2ページの描画：頂点に左から $0,1,\dots,n-1$ と番号をつけ、辺 $ij$ は $i+j$ を $n$ で割った余りが $\lfloor n/2\rfloor$ 未満なら上（青）、それ以外なら下（橙）に、半円で描きます。

図4具体例

K_n

を

Z(n)

個の交点で描く2つの方法です。スライダーで

n

を

3

から

12

まで変え、ボタンで描き方を切り替えられます。どちらの描き方でも、描いた曲線どうしの交わりを細かい折れ線で計算して数え、

Z(n)

と一致することを記事の生成時に確かめています。2ページの描画では、頂点の近くで交点が重なって見えるところがあります。

2ページの描画の交点の数は、次のように数えられます。

命題9 2ページの描画の交点の数 [2, Proposition 5.1]

$n\ge3$ とし、頂点 $0,1,\dots,n-1$ を直線上にこの順に並べる。辺 $ij$ を、 $i+j$ を $n$ で割った余りが $\lfloor n/2\rfloor$ 未満なら上側に、そうでなければ下側に、両端を直径とする半円で描く。頂点の位置をうまく選べば、この描画の交点の数はちょうど $Z(n)$ である。とくに $\operatorname{cr}(K_n)\le Z(n)$ である。

証明

同じ側の2つの半円は、端点が直線上で交互に並ぶとき（ $a\lt p\lt b\lt q$ のように）だけ交わり、そのとき1回だけ交わる。反対側の半円どうしは交わらない。

端点が $a\lt b$ の半円は $y^2=(x-a)(b-x)$ をみたす。2つの半円の右辺の差は $x$ の1次式なので、交わる $x$ は高々1つである。直径の区間が交互に重なるときは、重なりの両端でこの1次式の符号が逆になり、ちょうど1回交わる。入れ子のときは符号が同じで、交わらない。

3本が1点で交わらないことは、頂点を左から順に、それぞれ少しずつ位置をずらして置けば保証できる[2, §5]。
直線上の4頂点 $a\lt b\lt c\lt d$ のうち、端点が交互に並ぶ辺の組は $ac$ と $bd$ （対角線と呼ぶ）だけである。よって交点の数は、「対角線の2本が同じ側にある4頂点の組」の数に等しい。
4頂点を、円周上の番号 $0,\dots,n-1$ で $a$ から始めて間隔 $g_1,g_2,g_3,g_4$ （正の整数、合計 $n$ ）で並べる。対角線の両端の和は $r=2a+g_1+g_2$ と $r+k$ （ $k=g_1+g_3$ ）である。

4頂点は $a,\ a+g_1,\ a+g_1+g_2,\ a+g_1+g_2+g_3$ （ $n$ で割った余り）で、対角線は $\{a,\,a+g_1+g_2\}$ と $\{a+g_1,\,a+g_1+g_2+g_3\}$ である。端点の和はそれぞれ $2a+g_1+g_2$ と $2a+2g_1+g_2+g_3$ で、差は $g_1+g_3$ である。

直線上で交互に並ぶことは、番号を円周上に並べて交互であることと同じなので、4頂点の組は始点 $a$ の選び方の分だけ、ちょうど4回ずつ数えられる。
余り $r$ と $r+k$ が同じ側に入る $r$ は $n-2\min(k,n-k)$ 個ある。 $k$ を決めたときの間隔の選び方は $(k-1)(n-k-1)$ 通りである。
$n$ が奇数のときは、 $a$ を動かすと $r$ はすべての余りを1回ずつとるので、4回ずつの重複を割って次を得る。 $n$ が偶数のときは $r$ の偶奇に偏りが出るが、論文は場合分けで同じ式になることを示している[2, Proposition 5.1]。
$\begin{aligned} c(D)&=\frac14\sum_{k=2}^{n-2}(k-1)(n-k-1)\\ &\qquad\bigl(n-2\min(k,n-k)\bigr)\end{aligned}$
この和は $Z(n)$ に等しい。

$k$ と $n-k$ を組にすると $c(D)=\frac12\sum_{k=1}^{m}(k-1)(n-k-1)(n-2k)$ （ $m=\lfloor n/2\rfloor$ ）となる。 $B_k=k(k-1)(n-k-1)(n-k-2)$ とおくと $B_k-B_{k-1}=2(k-1)(n-k-1)(n-2k)$ なので、和は $B_m/4$ になる。 $n=2m+1$ なら $m^2(m-1)^2/4=\binom m2^2$ 、 $n=2m$ なら $m(m-1)^2(m-2)/4$ で、どちらも $Z(n)$ である。

$n=7$ （ $\lfloor7/2\rfloor=3$ ）で確かめます。余り $0,1,2$ が上側、 $3,4,5,6$ が下側です。 $k=2,5$ のとき $r$ と $r+k$ が同じ側に入る $r$ は $3$ 個、 $k=3,4$ のときは $1$ 個です。間隔の選び方は $k=2,5$ で $4$ 通り、 $k=3,4$ で $6$ 通りなので、

c(D)=\frac14\bigl(4\cdot3+6\cdot1+6\cdot1+4\cdot3\bigr)=\frac{36}4=9=Z(7)

\begin{aligned}c(D) &= \frac14\bigl(4\cdot3+6\cdot1+6\cdot1+4\cdot3\bigr)\\&= \frac{36}4\\&= 9\\&= Z(7)\end{aligned}

今回より前に分かっていたこと

下界のほうは、小さい $n$ と、描き方を制限した場合に限られていました。

$n$	$Z(n)$	$\operatorname{cr}(K_n)=Z(n)$ を示したもの
$5,6$	$1,\ 3$	オイラーの公式（例5）
$7$ 〜 $10$	$9,\ 18,\ 36,\ 60$	ガイ（1971年までに）[6, p.53]
$11,12$	$100,\ 150$	パンとリクター、計算機を使った証明（2007年）^[16]
$13,14$	$225,\ 315$	アイヒホルツァー、計算機を使った証明の報告（2021年）^[17]
$15$ 以上	$441,\ 588,\dots$	今回まで未解決

漸近的には、バログ、リディツキー、サラザールが2019年に $\lim\operatorname{cr}(K_n)/Z(n)>0.98559895$ を示していました[13, Theorem 1]。フラグ代数を使った結果です。
2ページの描画、円筒の描画など、描き方を制限したクラスの中では $Z(n)$ 個以上必要なことが示されていました^[18,19]。

表の $n=15$ の値は $Z(15)=\binom72^2=441$ 、 $Z(16)=8\cdot7^2\cdot6/4=588$ です。

今回の2つの定理

定理10 ハラリー・ヒル予想、OpenAI 2026 [2, Theorem 1.1]

$n\ge3$ のすべての整数について

\begin{aligned} \operatorname{cr}(K_n)&=Z(n)\\ &=\frac14\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}2\right\rfloor\\ &\phantom{{}={}\frac14}\left\lfloor\frac{n-2}2\right\rfloor\left\lfloor\frac{n-3}2\right\rfloor\end{aligned}

定理11 ザランキエヴィッチ予想、OpenAI 2026 [3, Theorem 1.1]

すべての正の整数 $m,n$ について

\begin{aligned} \operatorname{cr}(K_{m,n})&=\left\lfloor\frac m2\right\rfloor\left\lfloor\frac{m-1}2\right\rfloor\\ &\phantom{{}={}}\left\lfloor\frac n2\right\rfloor\left\lfloor\frac{n-1}2\right\rfloor\end{aligned}

2つの定理から、予想8と予想7はどちらも正しいことになります。

上界（その数の交点で描けること）は、命題6と命題9で示したとおりです。新しいのは下界、つまりどんな描画でもこの数以上の交点ができることです。辺は直線である必要も、なめらかである必要もなく、連続な曲線なら何でも構いません。

定理を読むときに気をつけたい点が2つあります。

辺を直線に限る問題とは別です。辺を直線で描く場合の最小値（直線交差数）は、ふつうの交差数以上になります。 $K_8$ では、ふつうの交差数が $18$ なのに、直線では $19$ 個必要です[6, p.55]。直線交差数はふつうの交差数以上なので、今回の定理から $K_n$ の直線交差数が $Z(n)$ 以上であることは従います。ただし、直線の場合の値を決めるものではありません。
交点はすべて数えます。定義2のとおり、同じ2本の辺が何回交わってもすべて数えます。交わる辺の組を数える変種などは、今回の定理の対象ではありません[2, §1]。

偶数の場合は奇数の場合から従う

下界の証明で、論文が新しい方法で示すのは $n$ が奇数の場合だけです。偶数の場合は、古くから知られている数え上げで奇数の場合から従います[2, Corollary 4.4; 3, §5.3; 6, p.53]。この部分は初等的なので、証明をつけて紹介します。

使うのは、最小の描画は「辺を共有する2本の辺が交わらない」ように選べる、という事実です[2, Lemma A.1]。このとき、交点を作る2本の辺の端点は4つとも異なります。

命題12 頂点を1つずつ消す数え上げ

(1)　 $n\ge5$ なら $(n-4)\operatorname{cr}(K_n)\ge n\operatorname{cr}(K_{n-1})$ 。
(2)　 $n\ge3$ なら $(n-2)\operatorname{cr}(K_{m,n})\ge n\operatorname{cr}(K_{m,n-1})$ 。

証明

(1) を示す。 $K_n$ の最小の描画 $D$ を、辺を共有する辺どうしが交わらないようにとる。
頂点 $v$ を1つ選び、 $v$ と $v$ から出る辺を消すと、 $K_{n-1}$ の描画が残る。その交点の数は $\operatorname{cr}(K_{n-1})$ 以上である。
$n$ 個の頂点それぞれについて消してみて、残る交点の数を足す。合計は $n\operatorname{cr}(K_{n-1})$ 以上である。
一方、 $D$ の各交点は4つの異なる頂点を端点にもつ2本の辺の交わりなので、それ以外の $n-4$ 個の頂点を消したときにだけ残る。よって合計はちょうど $(n-4)c(D)=(n-4)\operatorname{cr}(K_n)$ である。2つを比べて (1) を得る。
(2) も同じである。置き場の側の頂点 $b_p$ を1つずつ消す。交点を作る2本の辺は置き場の側の端点が異なるので、各交点は残りの $n-2$ 回で残る。

奇数 $2s-1$ で $\operatorname{cr}(K_{2s-1})=Z(2s-1)$ が分かれば、(1) から

\operatorname{cr}(K_{2s})\ge\frac{2s}{2s-4}\binom{s-1}2^{\!2}=\frac{2s}{2(s-2)}\cdot\frac{(s-1)^2(s-2)^2}{4}=\frac{s(s-1)^2(s-2)}4=Z(2s)

\begin{aligned}\operatorname{cr}(K_{2s}) &\ge \frac{2s}{2s-4}\binom{s-1}2^{\!2}\\&= \frac{2s}{2(s-2)}\cdot\frac{(s-1)^2(s-2)^2}{4}\\&= \frac{s(s-1)^2(s-2)}4\\&= Z(2s)\end{aligned}

たとえば $\operatorname{cr}(K_5)=1$ から $\operatorname{cr}(K_6)\ge\frac62\cdot1=3=Z(6)$ 、 $\operatorname{cr}(K_7)=9$ から $\operatorname{cr}(K_8)\ge\frac84\cdot9=18=Z(8)$ です。完全2部グラフでも、 $n$ が偶数なら $n\,d_{n-1}=(n-2)\,d_n$ が成り立つので、同じように奇数の場合から偶数の場合が従います[3, §5.3]。

逆向き、つまり偶数から次の奇数へは、この数え上げでは届きません。たとえば $\operatorname{cr}(K_6)=3$ から言えるのは $\operatorname{cr}(K_7)\ge\frac73\cdot3=7$ で、本当の値 $9$ には足りません。難しいのは奇数の場合です。

下界の証明の考え方

論文の下界の証明は、描画の幾何学的な情報を線形代数の問題に移すものです。次の4段階に分かれ、第1・第2段階は2本の論文で共通、第3・第4段階は論文ごとに異なります。

1
描画を整える
最小の描画を、辺が折れ線で、辺を共有する辺どうしは交わらない形に取り直す[2, Lemma A.1]。
2
交点に符号をつける
辺に向きをつけ、交点に「どちら向きに横切ったか」で $\pm1$ をつける。閉じた曲線どうしでは符号の和が $0$ になることを使い、辺の組の行列 $J$ が閉路の組の上で $0$ になる、という恒等式を作る。
3
恒等式を線形代数に移す
完全グラフでは、頂点に相異なる実数を割り当て、多項式で重みをつけた閉路を恒等式に入れる[2, §4]。完全2部グラフでは、4本の辺でできる閉路を恒等式に入れ（Lemma 3.2）、ラグランジュ補間の重みで作った線形写像 $\Phi$ で行列に移す（Lemma 4.2）[3, §3, §4]。どちらも、頂点のまわりの辺の並び方（回転系）を読み取るのにラグランジュ補間の性質を使う。
4
次元や階数を数える
完全グラフでは、交点のある辺の組を座標とする空間の中に次元 $Z(n)$ の部分空間を作り、その次元が交点の数で抑えられることを示す（Proposition 4.3）。完全2部グラフでは、行列の階数の和の不等式（Corollary 2.3）で、階数の和が $2d_md_n$ 以上で交点の数の2倍以下であることを示す[3, §5.2]。

第2段階の出発点は、平面の閉曲線についての次の事実です。ここだけは図で確かめられます。

命題13 閉曲線の交点の符号の和 [2, §2; 3, Lemma 3.1]

向きのついた2本の閉じた折れ線 $\gamma,\eta$ が、角を避けて有限個の点で横切りあっているとする。各交点に、 $\gamma$ の向きから $\eta$ の向きへ反時計回りに回るなら $+1$ 、時計回りなら $-1$ の符号をつける。このとき符号の和は $0$ である。

証明

平面の点 $o$ を、 $\gamma$ の各線分 $[u,w]$ と三角形 $[o,u,w]$ を作ったときに具合の悪いことが起きないように選ぶ。

三角形がつぶれる、三角形の辺が $\eta$ の角を通る、 $\eta$ と接する、といった場合は、 $o$ が有限本の直線の上にあるときだけ起きる。それらを避ければよい。
各三角形の周（向きつき）と $\eta$ の交点の符号の和は $0$ である。

$\eta$ は閉じているので、三角形の中に入った回数と出た回数は等しい。入るときと出るときで横切る向きが逆なので、符号は打ち消しあう。
三角形の周を全部足すと、 $o$ から出る辺は隣どうしで逆向きに2回ずつ現れて打ち消しあい、 $\gamma$ だけが残る。よって $\gamma$ と $\eta$ の符号の和も $0$ である。

+

-

+

-

交点の符号の和：

+1-1+1-1=0

図5具体例命題13の例です。青と橙の閉曲線は4回交わり、交点の符号は

+1

と

-1

が交互に現れて、和は

0

です。符号は交点ごとに2本の線分の向きから計算しています。

グラフの閉路（頂点をたどって元に戻る道）は、描画の中では閉曲線になります。ただし2つの閉路が頂点を共有すると、そこで「交わっているのか、触れているだけなのか」があいまいになります。論文は、頂点のまわりの辺の並び方から決まる $\pm\tfrac12$ の補正を足した行列 $J$ を作り、どんな2つの閉路 $z,z'$ についても $J(z,z')=0$ となることを示しています[2, Lemma 2.1; 3, Lemma 3.1]。

専門的な話完全グラフの場合：等方的な部分空間の次元

$n=2s+1$ とします。第4段階の線形代数の核は、次の事実です。

命題14 全等方部分空間の次元 [2, Proposition 4.3 の証明中]

$\mathbb{R}^N$ の対称双線形形式 $\langle x,y\rangle=\sum_\alpha a_\alpha x_\alpha y_\alpha$ （すべての $a_\alpha\ne0$ ）について、部分空間 $W$ のどの2つのベクトルも $\langle w,w'\rangle=0$ をみたすなら、 $2\dim W\le N$ である。

証明

仮定は $W\subseteq W^{\perp}$ と言い換えられる。ここで $W^\perp=\{x:\langle x,w\rangle=0\ (w\in W)\}$ である。
すべての $a_\alpha$ が $0$ でないので、形式は退化していない。このとき $\dim W^\perp=N-\dim W$ である。

写像 $x\mapsto\langle x,\cdot\rangle|_W$ は $\mathbb{R}^N$ から $W$ の双対空間への全射で、核が $W^\perp$ である。全射なのは、形式が退化していないので $\mathbb{R}^N$ の線形汎関数がすべて $\langle x,\cdot\rangle$ の形で書け、 $W$ 上の線形汎関数は $\mathbb{R}^N$ 全体に延ばせるからである。
$\dim W\le\dim W^\perp=N-\dim W$ より $2\dim W\le N$ である。

たとえば $\mathbb{R}^2$ で $\langle x,y\rangle=x_1y_1-x_2y_2$ とすると、 $(1,1)$ の張る直線は全等方ですが、2次元の全等方部分空間はありません。

論文は、 $x,u,y,v$ の4変数の多項式で、各変数について次数 $s-2$ 以下、 $(x,u)$ の入れ替えと $(y,v)$ の入れ替えで不変なものの空間 $\mathcal S$ を考えます[2, §4]。 $(x,u)$ について対称な多項式の基底は $0\le a\le b\le s-2$ で番号づけられ、その数は $\binom s2$ なので、次のようになります。

\dim\mathcal S=\binom s2^{\!2}=Z(2s+1)

\begin{aligned}\dim\mathcal S &= \binom s2^{\!2}\\&= Z(2s+1)\end{aligned}

$s=3$ （ $K_7$ ）なら、各変数について1次以下の多項式で、 $(x,u)$ について対称なものは $1,\ x+u,\ xu$ の3つで張られます。 $(y,v)$ についても同じなので、 $\mathcal S$ は $3\times3=9$ 次元で、 $Z(7)=9$ と一致します。

頂点 $i$ に相異なる実数 $t_i$ を割り当てます。共通の端点をもたず、 $J$ の値が $0$ でない辺の順序対 $(\{i,p\},\{k,q\})$ の集合を $\mathcal T$ とします。辺の組が $\mathcal T$ に入るには少なくとも1回交わる必要があります。順序対で数えると1組が2回入るので、 $|\mathcal T|\le 2c(D)$ です。

評価写像 $E:\mathcal S\to\mathbb{R}^{\mathcal T}$ を、 $P$ を各座標 $(\{i,p\},\{k,q\})$ での値 $P(t_i,t_p,t_k,t_q)$ に送るものとします。証明は次の2つから成ります。

$E$ は単射（Lemma 4.2）。 $E(P)=0$ とすると、閉路の恒等式から $P(x,u,x,v)=0$ が従い、 $P$ は $(x-y)(x-v)(u-y)(u-v)$ で割り切れます。割った商も同じ条件をみたすので、次数が下がり続けて $P=0$ になります。ここで頂点のまわりの辺の並び方を読み取るのに、ラグランジュ補間の重み $1/G'(u_p)$ を使った「順序の検出器」（Lemma 3.3）を使います。
像は全等方（Proposition 4.3）。閉路の恒等式に $PQ\cdot(x-u)(y-v)(x-y)(x-v)(u-y)(u-v)$ を入れると、 $\sum_{\alpha\in\mathcal T}a_\alpha E(P)_\alpha E(Q)_\alpha=0$ （すべての $a_\alpha\ne0$ ）が得られます。

上の命題と合わせると、次のように下界が出ます。

c(D)\ge\frac{|\mathcal T|}2\ge\dim E(\mathcal S)=\dim\mathcal S=\binom s2^{\!2}=Z(2s+1)

\begin{aligned}c(D) &\ge \frac{|\mathcal T|}2\\&\ge \dim E(\mathcal S)\\&= \dim\mathcal S\\&= \binom s2^{\!2}\\&= Z(2s+1)\end{aligned}

ラグランジュ補間の重みを使うのは、次の恒等式が成り立つからです。相異なる $u_1,\dots,u_N$ と $G(t)=\prod_p(t-u_p)$ について、次数 $N-2$ 以下の多項式 $A$ は次をみたします（Lemma 3.1）。

\sum_{p=1}^{N}\frac{A(u_p)}{G'(u_p)}=0

\begin{aligned}\sum_{p=1}^{N}\frac{A(u_p)}{G'(u_p)} &= 0\end{aligned}

$u=0,1,2$ なら $G'(0)=2,\ G'(1)=-1,\ G'(2)=2$ で、 $A=1$ では $\tfrac12-1+\tfrac12=0$ 、 $A=t$ では $0-1+1=0$ です。 $A=t^2$ （次数 $2=N-1$ ）では $0-1+2=1$ となり、 $0$ になりません。この重みを頂点ごとにつけた辺の和は境界が $0$ になり、閉路として恒等式に入れられます（Lemma 4.1）。

専門的な話完全2部グラフの場合：行列の階数の和

完全2部グラフの論文では、 $n=2s+1$ のとき、窯 $a_i$ から出る辺と窯 $a_k$ から出る辺の $J$ の値を並べた $n\times n$ 行列 $J^{ik}$ を考えます[3, §3, §5.2]。4本の辺でできる閉路を恒等式に入れると、 $J^{ik}-J^{i1}-J^{1k}+J^{11}$ が「行ごとの定数＋列ごとの定数」の形になることが分かります（Lemma 3.2）。

次に、 $n\times n$ 行列を $s^2\times s^2$ 行列に送る線形写像 $\Phi$ を、ラグランジュ補間の重みを使って作ります（Lemma 4.2）。 $\Phi$ は「行ごとの定数＋列ごとの定数」と対角成分を消し、各成分を階数1以下の行列に送り、頂点のまわりの辺の並び方を表す行列を可逆な行列に送ります。

$R_{ik}=\Phi(J^{ik})$ とおくと、 $X_i-Y_k$ の形に書け、 $R_{ii}$ は可逆（階数 $s^2=d_n$ ）、 $i\ne k$ では階数が窯 $a_i,a_k$ の辺どうしの交点の数 $c_{ik}$ 以下になります。ここに次の不等式を使います（Corollary 2.3）。

\begin{aligned} &X_i-Y_i\ \text{がすべて可逆}\\ &\Longrightarrow\ \sum_{i\ne j}\operatorname{rank}(X_i-Y_j)\ge 2d_m\,d\end{aligned}

この不等式自体は、多項式の行列式の零点の重複度を数える議論で、部分空間の交わりの次元の和を抑える補題（Lemma 2.1）から導かれます。まとめると

2d_md_n\le\sum_{i\ne k}\operatorname{rank}R_{ik}\le\sum_{i\ne k}c_{ik}=2c(D)

\begin{aligned}2d_md_n &\le \sum_{i\ne k}\operatorname{rank}R_{ik}\\&\le \sum_{i\ne k}c_{ik}\\&= 2c(D)\end{aligned}

となり、 $c(D)\ge d_md_n$ が出ます。各交点は2つの窯の組に、順序を入れて2回数えられるので、最後の等号が成り立ちます。

2本の論文は関係していますが、完全グラフの論文は、下界の証明が完全2部グラフの公式に依存しないと明記しています[2, §1]。閉路の恒等式の証明は共通で、順序の検出器は完全グラフの側で偶数個の点用に作り直されています。

どこまで確かなのか

2本の論文は2026年9月23日付のプレプリントで、査読はまだです^[2,3]。
リポジトリの照合（Comparator）の設定で、2つの主定理が検査の対象になっています^[20]。完全グラフは OAI.Paper170.complete_graph_crossing_number（ $n\ge3$ で $\operatorname{cr}(K_n)$ が $Z(n)$ に等しい）、完全2部グラフは OAI.Zarankiewicz.mainTarget_proof（すべての $m,n\ge1$ で、公式の数の交点をもつ描画があり、どの描画の交点もその数以上）です。許可された公理は、Leanで標準的な propext、Quot.sound、Classical.choice の3つです。名前空間の「Paper170」の170は、リポジトリの一覧の165番とは別の番号です。
形式化の範囲の説明によると、完全グラフでは下界と、上界を与える2ページの描画の構成の両方が形式化されています^[5]。どちらの形式化でも、辺は連続な曲線で、交点は平面上の点として数えられます。
2026年10月7日付の更新では、この2本は修正も取り下げもされていません^[21]。

照合の対象になっている主張では、描画は「頂点の位置が相異なり、辺が単射な連続曲線で、辺の内部は頂点を通らず、交点は有限個で、どれもきちんと横切り、3本の辺が1点で交わらない」ものとして定義されています。定義2をそのまま書いたものだと読めます。なお、筆者はこの記事を書いた時点で、Leanの検査を手元で再実行していません。

論文の序文によると、2018年にも両方の公式を主張する論文（Hebbar と Mangam）が出ています。論文は、決まった描画の交点を数えるだけでは上界しか得られず、すべての描画についての最小値を決めるには下界の議論が必要だと述べています[2, §1]。

残された問題

直線で描く場合：辺を直線に限った交差数は、定理10とは別の問題です。 $K_8$ のように、ふつうの交差数より大きくなる場合があります[6, p.55]。
交差数の変種：交わる辺の組を数える交差数などは、一般のグラフでふつうの交差数と同じになるかが研究されています^[4]。今回の証明はふつうの交差数についてのものです。
ほかのグラフ：描画を線形代数の問題に移す今回の方法が、完全グラフと完全2部グラフ以外のグラフにも使えるかは、これからの研究を待つことになります。

OpenAIの数学論文には、ほかに平面の彩色数の記事で読んだ「平面は5色では塗れない」や、πの無理数度の記事で読んだ「πの無理数度は2」もあります。

参考文献

OpenAI, openai/math: mathematical manuscripts and supporting proof artifacts, GitHub, 2026.
OpenAI, The crossing number of complete graphs, OpenAI Math Release preprint, September 23, 2026.
OpenAI, The crossing number of complete bipartite graphs, OpenAI Math Release preprint, September 23, 2026.
J. Pach, G. Tóth, Which crossing number is it anyway?, Journal of Combinatorial Theory, Series B 80 (2000), 225–246.
OpenAI, Lean formalization scope: The Harary–Hill and Zarankiewicz crossing-number formulas, openai/math, lean/docs/165.md, 2026.
P. Erdős, R. K. Guy, Crossing number problems, The American Mathematical Monthly 80 (1973), 52–58.
P. Turán, A note of welcome, Journal of Graph Theory 1 (1977), 7–9.
K. Zarankiewicz, On a problem of P. Turán concerning graphs, Fundamenta Mathematicae 41 (1954), 137–145（出版社の記録では1955年）.
K. Urbaník, Solution du problème posé par P. Turán, Colloquium Mathematicum 3 (1955), 200–201.
D. J. Kleitman, The crossing number of K_{5,n}, Journal of Combinatorial Theory 9 (1970), 315–323.
D. R. Woodall, Cyclic-order graphs and Zarankiewicz's crossing-number conjecture, Journal of Graph Theory 17 (1993), 657–671.
J. Balogh, B. Lidický, S. Norin, F. Pfender, G. Salazar, S. Spiro, Crossing numbers of complete bipartite graphs, Procedia Computer Science 223 (2023), 78–87.
J. Balogh, B. Lidický, G. Salazar, Closing in on Hill's conjecture, arXiv:1711.08958v2, 2018（頁はarXiv版。SIAM Journal on Discrete Mathematics 33 (2019), 1261–1276 に掲載）.
F. Harary, A. Hill, On the number of crossings in a complete graph, Proceedings of the Edinburgh Mathematical Society 13 (1963), 333–338.
J. Blažek, M. Koman, A minimal problem concerning complete plane graphs, Theory of Graphs and Its Applications (Proc. Symp. Smolenice, 1963), 1964, 113–117.
S. Pan, R. B. Richter, The crossing number of K_11 is 100, Journal of Graph Theory 56 (2007), 128–134.
O. Aichholzer, Another small but long step for crossing numbers: cr(13) = 225 and cr(14) = 315, Proceedings of the 33rd Canadian Conference on Computational Geometry (2021), 72–77.
B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, G. Salazar, The 2-page crossing number of K_n, Discrete & Computational Geometry 49 (2013), 747–777.
B. M. Ábrego, O. Aichholzer, S. Fernández-Merchant, P. Ramos, G. Salazar, Shellable drawings and the cylindrical crossing number of K_n, Discrete & Computational Geometry 52 (2014), 743–753.
OpenAI, Lean formalization: OAI/Combinatorics/CompleteCrossing/Main.lean, OAI/Combinatorics/Crossing/Main.lean and ComparatorChallenges/CompleteCrossing.lean, BipartiteCrossing.lean, openai/math, 2026.
OpenAI, openai/math: History, GitHub, 2026.