交差数不等式

グラフ描画の数学において、交差数不等式または交差補題は、与えられたグラフの平面描画における辺の交差の最小数の下限を、グラフの辺と頂点の数の関数として与える。これは、辺の数e が頂点の数nよりも十分に大きいグラフの場合、交差数は少なくともe ³ / n ²に比例することを述べている。

これはVLSI設計や組合せ幾何学に応用されており、Ajtai、Chvátal、Newborn、Szemerédi ^[1] とLeighton ^[2]によって独立に発見されました。

交差数不等式は、n個の頂点とe個の辺（e > 7 n）を持つ無向単純グラフ Gに対して、交差数cr( G )が不等式に従うことを述べている。

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{29n^{2}}}.}$

定数29は現在までに最もよく知られている定数であり、アッカーマンによるものです。^[3] より弱い定数を使用した以前の結果については、Pach & Tóth (1997)およびPach et al. (2006)を参照してください。^{[4] [5]} 定数7は4まで下げることができますが、 29をより悪い定数64に置き換えるという犠牲を払います。

交差数cr( G )とペアワイズ交差数pair-cr( G )を区別することは重要である。Pach & Tóth (2000)が指摘しているように、ペアワイズ交差数は、それぞれが1つの交差を決定するエッジのペアの最小数を指すのに対し、交差数は単に交差の最小数を指す。(一部の著者は、適切な描画では2つのエッジが複数回交差することはないと考えているため、この区別が必要である。) ^[6]${\displaystyle {\text{pair-cr}}(G)\leq {\text{cr}}(G)}$

レイトンが交差数を研究した動機は、理論計算機科学におけるVLSI設計への応用のためであった。^[2]

その後、Székely (1997) は、この不等式が接続幾何学におけるいくつかの重要な定理の非常に簡単な証明をもたらすことに気付きました。たとえば、平面上の与えられた数の点と直線の間で可能な接続の数の上限であるSzemerédi–Trotter の定理は、頂点が点であり、接続点間の線分が辺であるグラフを構築することによって得られます。接続が Szemerédi–Trotter の境界よりも多い場合、このグラフは必然的に直線のペアの総数よりも多くの交差を持つことになりますが、これは不可能です。この不等式は、有限点集合が共線上の点の線形数を持たなければ、異なる直線の二乗数が決まるというBeck の定理を証明するためにも使用できます。 ^[7] 同様に、Tamal Dey はこれを使用して幾何学的k集合の上限を証明しました。^[8]

まず予備的な推定値を与える。n個の頂点とe個の辺を持つ任意のグラフGに対して、

${\displaystyle \operatorname {cr} (G)\geq e-3n.}$

これを証明するには、ちょうどcr( G )個の交差を持つGの図式を考えます。これらの交差はそれぞれ、Gから辺を 1 つ削除することで削除できます。したがって、少なくともe − cr( G )個の辺と交差のないn 個の頂点を持つグラフを見つけることができ、これは平面グラフです。しかし、オイラーの公式から、e − cr( G ) ≤ 3 nとなるはずであり、主張は成り立ちます。(実際、n ≥ 3の場合、e − cr( G ) ≤ 3 n − 6となります)。

実際の交差数不等式を得るために、確率論的議論を用いる。0 < p < 1 を後で選択される確率パラメータとし、 Gの各頂点が確率 p で独立に H に存在することを許容し、 Gの辺がH に存在するのは、その 2 つの頂点が H に存在するように選択された場合のみとすることで、 G のランダムなサブグラフ H を構築する。e H 、n H 、cr _Hは_、それぞれH_の辺、頂点、交差の数を表すものとする。 H はGのサブグラフであるため、 Gの図にはHの図が含まれる。予備的な交差数不等式により、

${\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}$

期待に 応える

${\displaystyle \mathbf {E} [\operatorname {cr} _{H}]\geq \mathbf {E} [e_{H}]-3\mathbf {E} [n_{H}].}$

Gのn個の頂点のそれぞれがHにある確率はpなので、E [ n _H ] = pnとなります。同様に、 Gのそれぞれの辺がHに残る確率はp ²です。これは、両方の端点がHに残る必要があるためです。したがって、 E [ e _H ] = p ² eとなります。最後に、 Gの図のすべての交差がHに残る確率はp ⁴です。これは、すべての交差に 4 つの頂点が含まれるためです。これを確認するには、 cr( G )回の交差があるGの図を考えてみましょう。この図で、共通の頂点を持つ 2 つの辺は互いに素であると仮定できます。そうでない場合は、2 つの辺の交差部分を交換し、交差数を 1 つ減らすことができます。したがって、この図のすべての交差には、Gの 4 つの異なる頂点が含まれます。取得した図は、交差の数の点では最適ではないかもしれませんが、少なくともcr _H回の交差があることは明らかです。したがって、

${\displaystyle p^{4}\演算子名 {cr} (G)\geq \mathbf {E} [\演算子名 {cr} _{H}]}$

そして私たちは

${\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}$

ここで、p = 4 n / e < 1 （ e > 4 nと仮定したため）と設定すると、代数演算により次式が得られます。

${\displaystyle \operatorname {cr} (G)\geq {\frac {e^{3}}{64n^{2}}}.}$

この議論を少し改良すると、 e > 7.5 nの場合、64を33.75に置き換えることができます。^[3]

内周が2rより大きくe≥4nのグラフについては、Pach、Spencer、Tóth（2000）はこの不等式を次のように改善した^[9] 。

${\displaystyle \operatorname {cr} (G)\geq c_{r}{\frac {e^{r+2}}{n^{r+1}}}.}$

アディプラシトは高次元への一般化を示した：^[10]が に区分線形に写像される単体複体であり、となる-次元面と-次元面を持つ場合、 対で交差する-次元面の数は少なくとも ${\displaystyle \Delta }$${\displaystyle \mathbf {R} ^{2d}}$${\displaystyle f_{d}(\Delta )\ \ d}$${\displaystyle f_{d-1}(\Delta )\ \ (d-1)}$${\displaystyle f_{d}(\Delta )>(d+3)f_{d-1}(\Delta )}$${\displaystyle d}$

${\displaystyle {\frac {f_{d}^{d+2}(\Delta )}{(d+3)^{d+2}f_{d-1}^{d+1}(\Delta ) }}.}$