交叉數

交叉數不等式說明了給定邊數目${\displaystyle e}$和頂點數目${\displaystyle v}$，${\displaystyle {\hbox{cr}}(G)}$的下界。

已知平面圖都符合${\displaystyle v-e+f=2}$（歐拉公式）。考慮邊面的對應數目，每條邊剛好屬於某兩個面，而每個面最小有三條邊，因此對於平面圖有${\displaystyle 3f\leq 2e}$。為了消去${\displaystyle f}$，代入${\displaystyle f=2+e-v}$，得${\displaystyle e\leq 3v-6}$。

再考慮一般圖${\displaystyle G}$，如何將它「變成」平面圖。如果我們在每個相交點，都去掉一條邊，則剩下的圖必是平面圖。這個新的平面圖的邊數目為${\displaystyle e-{\hbox{cr}}(G)}$，而頂點數目v不變。因此，對於所有的圖都有

${\displaystyle {\hbox{cr}}(G)\geq e-3v+6}$

接下來使用機率方法，從G中構作一個新的圖。考慮在G所有頂點中選取某些點作為新圖G'的頂點；若G中的某一條邊的兩個端點都在V(G')內，則E(G')亦有該條邊；因此，G中的一個交點仍然存在在G'中的條件，是該交點涉及的2條邊的4個不同端點都保留在G'中。現在隨機選取G中的pv個頂點（${\displaystyle 0<p\leq 1}$），則 ${\displaystyle |V(G')|=pv,|E(G')|=p^{2}e,|V(G')|=p^{4}{\hbox{cr}}(G)}$，代入上面的不等式：

${\displaystyle p^{4}{\hbox{cr}}(G)\geq p^{2}e-3pv+6}$

${\displaystyle {\hbox{cr}}(G)\geq p^{-2}e-3p^{-3}v+6p^{-4}}$

求${\displaystyle {\hbox{cr}}(G)}$的下界，希望能使上面的不等式右方儘可能大。

當${\displaystyle e}$相當大時，考慮${\displaystyle e\geq 4v}$，可以取${\displaystyle p=4v/e}$，整理後得：

${\displaystyle {\hbox{cr}}(G)\geq e^{3}/64v^{2}}$

• http://terrytao.wordpress.com/2007/09/18/the-crossing-number-inequality/ 页面存档备份，存于