交差数(グラフ)

1：頂点を円周上の相異なる点に置き、各辺を両端を結ぶ線分で描く。円周上の 3 点は一直線上にないので、線分の内部は円周上の点を通らず (D1)、端点を共有する 2 本の線分は共有する端点でだけ交わり (D2)、端点を共有しない 2 本の線分の共有点は高々 1 個である (D3)。よって良い描画であり、交差の個数は端点を共有しない辺の組の個数以下である。
2：$G$ の良い描画から $H$ の頂点と辺だけを残すと $H$ の良い描画になり、交差の個数は増えない。$\operatorname{cr}(D)=\operatorname{cr}(G)$ となる $D$ に当てればよい。
3：交差の個数が $0$ の良い描画では、(D1)・(D2) と交差がないことから、相異なる辺の弧は共有する端点のほかに共有点をもたず、弧の内部は頂点を通らない。これは 平面グラフ の定義「平面グラフ・平面埋め込み」の平面埋め込みである。逆に、平面埋め込みは (D1)〜(D3) を満たし、交差の個数が $0$ の良い描画である。$\square$

$\operatorname{cr}(D)=\operatorname{cr}(G)=:c$ となる良い描画 $D$ をとる。交差の個数が正である限り、交差に関わる辺（内部がほかの辺の内部と共有点をもつ辺）を 1 本選び、描画から除く。残りは、除いた辺をもたないグラフの良い描画であり、除いた辺が関わっていた交差がなくなるので、交差の個数は $1$ 以上減る。したがって、高々 $c$ 本の辺を除けば交差の個数は $0$ になる。
除いた辺の本数を $k\le c$ とすると、残りは頂点 $n$ 個、辺 $m-k$ 本の単純グラフ $G'$ の、交差の個数が $0$ の良い描画である。prop-cr-basic の 3 により $G'$ は平面グラフであり、平面グラフ の系「単純平面グラフの辺数の上界」により $m-k\le3n-6$ である。$G$ が二部グラフなら $G'$ も二部グラフなので、同じ系により $m-k\le2n-4$ である。$c\ge k$ と合わせて結論を得る。$\square$

段 1（すべてのグラフでの弱い下界）。 すべての単純グラフ $H$（頂点 $n_H$ 個、辺 $m_H$ 本）について $\operatorname{cr}(H)\ge m_H-3n_H$ である。$n_H\ge3$ なら thm-cr-edge-bound による。$n_H\le2$ なら $m_H\le1$ であり、$n_H\ge1$ なら $m_H-3n_H\le1-3<0$、$n_H=0$ なら $m_H-3n_H=0$ なので、右辺は $0$ 以下である。
段 2（無作為な部分グラフ）。 $\operatorname{cr}(D)=\operatorname{cr}(G)=:c$ となる良い描画 $D$ をとり、$p:=4n/m$ とおく。仮定から $0< p\le1$ である。各頂点を独立に確率 $p$ で残し（$2^n$ 通りの残し方からなる有限確率空間）、残った頂点の集合を $V'$、両端が $V'$ に属する $G$ の辺の全体からなるグラフを $H$ とする。$D$ から $H$ の頂点と辺だけを残した描画 $D_H$ は $H$ の良い描画である。$n_H$、$m_H$ と $X:=\operatorname{cr}(D_H)$ はこの確率空間の上の確率変数で、段 1 により、どの場合にも
$$ X\ge\operatorname{cr}(H)\ge m_H-3n_H $$
である。
段 3（期待値の計算）。 各頂点は確率 $p$ で残るので $\mathbb E[n_H]=pn$ であり、各辺は両端が残るとき残るので $\mathbb E[m_H]=p^2m$ である。$X$ は、$D$ の 2 辺 $\{e,e'\}$ と共有点 $x\in e^\circ\cap e'^\circ$ の組のうち、$e,e'$ がともに $H$ に残るものの個数である。(D2) により $e$ と $e'$ は端点を共有しないので、両方が残るのは相異なる 4 頂点がすべて残るときで、その確率は $p^4$ である。期待値の線形性と数え上げ の定理「期待値の線形性」により $\mathbb E[X]=p^4c$ である。段 2 の不等式の期待値をとって
$$ p^4c\ge p^2m-3pn,\qquad\text{すなわち}\qquad c\ge\frac{m}{p^2}-\frac{3n}{p^3} $$
を得る。$p=4n/m$ を代入すると
$$ c\ge\frac{m^3}{16n^2}-\frac{3m^3}{64n^2}=\frac{m^3}{64n^2} $$
である。$\square$

$m=\frac{n(n-1)}2$ であり、$m\ge4n$ は $n\ge9$ と同値である。thm-cr-crossing-lemma により $\operatorname{cr}(K_n)\ge\frac{n^3(n-1)^3}{8\cdot64n^2}=\frac{n(n-1)^3}{512}$ である。$\square$

円の 2 本の弦は、端点が円周上で交互に並ぶとき 1 点で交わり、そうでなければ交わらない。円周上の相異なる 4 点を 2 組に分ける 3 通りのうち、端点が交互に並ぶのはちょうど 1 通り（四角形の 2 本の対角線）である。よって交差する辺の組は 4 頂点の集合と 1 対 1 に対応し、各組は 1 点で交わる。prop-cr-basic の 1 の証明により、これは良い描画である。$\square$

一方の側の $a$ 頂点を $x$ 軸上の $0$ でない相異なる点に、正の側に $\lceil a/2\rceil$ 個、負の側に $\lfloor a/2\rfloor$ 個置く。もう一方の側の $b$ 頂点を $y$ 軸上に同様に置き、辺を線分で描く。線分の内部は開いた象限の中にあるので頂点を通らない (D1)。端点を共有する 2 本の線分は、共有する端点と残りの 2 つの端点が、一方の軸の上の 2 点と他方の軸の上の原点でない 1 点なので一直線上になく、共有する端点でだけ交わる (D2)。端点を共有しない 2 本の線分の共有点は高々 1 個である (D3)。よって良い描画である。
端点を共有しない 2 辺 $(s,0)$–$(0,u)$ と $(t,0)$–$(0,w)$ を考える。2 本の線分の内部はそれぞれ 1 つの開いた象限にあるので、交わるのは $s,t$ が同符号かつ $u,w$ が同符号のときに限る。座標の符号を変えて第 1 象限で考え、$0< s< t$ とする。直線 $\frac xs+\frac yu=1$ に対して、点 $(t,0)$ は原点と反対側にあり、点 $(0,w)$ は $w< u$ なら原点の側、$w>u$ なら反対側にある。直線 $\frac xt+\frac yw=1$ に対して、点 $(s,0)$ は原点の側にあり、点 $(0,u)$ は $u>w$ なら反対側、$u< w$ なら原点の側にある。2 本の線分が交わるのは、どちらの線分の両端も他方の直線の両側にあるときに限るので、交わるのは $u>w$ のときで、そのとき交点は 1 個である。よって、ある象限に $x$ 軸側の頂点が $\alpha$ 個、$y$ 軸側の頂点が $\beta$ 個あれば、その象限の交差は $\binom\alpha2\binom\beta2$ 個である。4 つの象限で足すと、交差の個数は
$$ \Bigl(\binom{\lceil a/2\rceil}2+\binom{\lfloor a/2\rfloor}2\Bigr)\Bigl(\binom{\lceil b/2\rceil}2+\binom{\lfloor b/2\rfloor}2\Bigr) $$
である。$a=2r$ なら第 1 因子は $2\binom r2=r(r-1)$、$a=2r+1$ なら $\binom{r+1}2+\binom r2=r^2$ で、どちらも $\lfloor\frac a2\rfloor\lfloor\frac{a-1}2\rfloor$ に等しい。$b$ についても同様である。$\square$