交差数不等式
Drawings of dense graphs have many crossings

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

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

声明と歴史

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

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

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

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

アプリケーション

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

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

証拠

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

cr ⁡ ( G ) ≥ e − 3 n . {\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の図が含まれる。予備的な交差数不等式より、

cr H ≥ e H − 3 n H . {\displaystyle \operatorname {cr} _{H}\geq e_{H}-3n_{H}.}

期待値を 得る

E [ cr H ] ≥ E [ e H ] − 3 E [ n 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 2です。これは、両方の端点がHに残る必要があるためです。したがって、 E [ e H ] = p 2 eが成り立ちます。最後に、 Gの図におけるすべての交差は、4 つの頂点を含むため、 Hに残る確率はp 4です。これを理解するために、 cr( G )回の交差を持つGの図を考えてみましょう。この図において、共通の頂点を持つ任意の 2 つの辺は互いに素であると仮定できます。そうでない場合は、2 つの辺の交差部分を交換し、交差数を 1 つ減らすことができます。したがって、この図のすべての交差は、Gの 4 つの異なる頂点を含みます。得られた図は、交差数の観点からは最適ではないかもしれませんが、少なくともcr H回の交差があることは明らかです。したがって、

p 4 cr ⁡ ( G ) ≥ E [ cr H ] {\displaystyle p^{4}\operatorname {cr} (G)\geq \mathbf {E} [\operatorname {cr} _{H}]}

そして私たちは

p 4 cr ⁡ ( G ) ≥ p 2 e − 3 p n . {\displaystyle p^{4}\operatorname {cr} (G)\geq p^{2}e-3pn.}

ここで、 p = 4 n / e < 1 （ e > 4 nと仮定したため）と設定すると、いくつかの代数処理を経て、

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

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

バリエーション

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

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

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

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

参考文献

  1. ^ Ajtai, M. ; Chvátal, V. ; Newborn, MM; Szemerédi, E. (1982)、「交差フリーサブグラフ」、組合せ論の理論と実践、North-Holland Mathematics Studies、第60巻、North-Holland、アムステルダム、pp.  9– 12、MR  0806962。
  2. ^ ab Leighton, T. (1983)、「VLSIにおける複雑性の問題」、コンピューティングの基礎シリーズ、ケンブリッジ、マサチューセッツ州：MITプレス。
  3. ^ ab Ackerman, Eyal (2019)、「辺あたり最大4つの交差を持つ位相グラフについて」、計算幾何学、85 101574: 101574, 31、arXiv : 1509.01932、doi :10.1016/j.comgeo.2019.101574、MR  4010251、S2CID  16847443。
  4. ^ Pach, János ; Tóth, Géza (1997)、「辺あたりの交差が少ないグラフ」、Combinatorica、17 (3): 427– 439、doi :10.1007/BF01215922、MR  1606052、S2CID  20480170。
  5. ^ Pach, János ; Radoičić, Radoš; Tardos, Gábor; Tóth, Géza (2006)、「疎グラフにおける交差の発見を増やすことで交差補題を改善する」、Discrete and Computational Geometry、36 (4): 527– 552、doi : 10.1007/s00454-006-1264-9、MR  2267545。
  6. ^ Pach, János; Tóth, Géza (2000)、「Which crossing number is it anyway?」、Journal of Combinatorial Theory、Series B、80 (2): 225– 246、doi : 10.1006/jctb.2000.1978。
  7. ^ Székely, LA (1997)、「離散幾何学における交差数と難解なエルデシュ問題」、組合せ論、確率、計算、6 (3): 353– 358、doi :10.1017/S0963548397002976、MR  1464571、S2CID  36602807。
  8. ^ Dey, TK (1998)、「平面k集合と関連問題に対する改良境界」、離散および計算幾何学、19 (3​​): 373– 382、doi : 10.1007/PL00009354、MR  1608878。
  9. ^ Pach, J. ; Spencer, J. ; Tóth, G. (2000)、「交差数の新しい境界」、離散および計算幾何学、24 (4): 623– 644、doi : 10.1007/s004540010011、MR  1799605。
  10. ^ Adiprasito, Karim (2018-12-26)、「正値性を超えた組み合わせ的レフシェッツ定理」、arXiv : 1812.10454v3 [math.CO]。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Crossing_number_inequality&oldid=1309471438"