ローテーションシステム

組合せ 数学において、回転システム(組合せ埋め込みまたは組合せマップとも呼ばれる)は、各頂点の周りのグラフの辺の循環的な順序を記述することによって、グラフの向き付け可能な表面への埋め込みをエンコードします。回転システムのより正式な定義には、順列のペアが含まれます。このようなペアは、マルチグラフ、表面、および表面へのマルチグラフの 2 セル埋め込みを決定するのに十分です。

すべての回転スキームは、有向閉面上の連結マルチグラフの一意の 2 セル埋め込みを定義します(方向保存位相同値まで)。逆に、有向閉面上の連結マルチグラフGの任意の埋め込みは、 G を基礎マルチグラフとする一意の回転システムを定義します。回転システムと 2 セル埋め込みのこの基本的な同値性は、1890 年代に Lothar Heffter によって双対形式で最初に解決され^[1] 、 1950 年代にRingelによって広く使用されました。 ^[2]独立して、Edmonds は定理の原型を与え^[3]、彼の研究の詳細は Youngs によって普及されました。^[4] マルチグラフへの一般化は Gross と Alpert によって提示されました。^[5]

回転システムは、グラフのジグザグ積を定義するために Reingold ら (2002) が使用した回転マップと関連していますが、同じではありません。回転システムは各頂点の周りのエッジの循環的な順序を指定しますが、回転マップは各頂点のエッジの (非循環的な) 順列を指定します。さらに、回転システムは任意のグラフに対して定義できますが、Reingold らが定義した回転マップは通常のグラフに制限されます。

正式には、回転システムは (σ, θ) のペアとして定義されます。ここで、 σ と θ は同じ基底集合B上で作用する順列であり、 θ は固定小数点のない反転であり、σ と θ によって生成される群<σ, θ>はB上で推移的に作用します。

有向面上の連結マルチグラフGの 2 セル埋め込みから回転システムを導出するには、 B をGのダーツ(またはフラグ、またはハーフエッジ)で構成します 。つまり、Gの各エッジに対して、エッジの各エンドポイントに 1 つずつ、 Bの 2 つの要素を形成します。エッジが両方のエンドポイントと同じ頂点を持つ場合でも、そのエッジに対して 2 つのダーツを作成します。 θ( b ) をbと同じエッジから形成されるもう 1 つのダーツとします。これは明らかに固定点のない反転です。 σ( b ) を、同じ頂点に入射するエッジの循環順序でbから時計回りの位置にあるダーツとします。ここで、「時計回り」は面の向きによって定義されます。

マルチグラフが向き付け可能だが向き付けされていない表面に埋め込まれている場合、それは通常、表面の 2 つの向きのそれぞれに 1 つずつ、合計 2 つの回転システムに対応します。これらの 2 つの回転システムは同じ反転 θ を持ちますが、一方の回転システムの順列 σ は、もう一方の回転システムの対応する順列の逆になります。

回転システムから多重グラフを復元するには、σ の各軌道に頂点を形成し、θ の各軌道に辺を形成します。これらの 2 つの軌道の交差が空でない場合、頂点は辺に接続されます。したがって、頂点あたりの発生数は軌道のサイズであり、辺あたりの発生数はちょうど 2 です。回転システムが連結多重グラフGの 2 セル埋め込みから派生する場合、回転システムから派生したグラフはGと同型です。

回転システムから導出されたグラフを表面に埋め込むには、σθ の各軌道に円板を形成し、eに対応する 2 つのダーツがこれらの円板に対応する 2 つの軌道に属する場合は常に、エッジeに沿って 2 つの円板を接着します。結果は、導出されたマルチグラフの 2 セル埋め込みであり、その 2 つのセルは σθ の軌道に対応する円板です。この埋め込みの表面は、各頂点の周りのエッジの時計回りの順序が σ によって与えられた時計回りの順序と同じになるように配置できます。

オイラーの公式によれば、回転系によって定義される閉曲面（つまり、基礎となる多重グラフが2セル埋め込まれている面）の種数 gを導くことができる。 ^[6]、およびであることに注意する。 ${\displaystyle (\sigma ,\theta )}$${\displaystyle V=|Z(\sigma )|}$${\displaystyle E=|Z(\theta )|}$${\displaystyle F=|Z(\sigma \theta )|}$

${\displaystyle g=1-{\frac {1}{2}}(V-E+F)=1-{\frac {1}{2}}(|Z(\sigma )|-|Z(\シータ )|+|Z(\sigma \シータ )|)}$

ここで、 は順列 の軌道の集合を表します。 ${\displaystyle Z(\phi )}$${\displaystyle \phi}$

• 組み合わせマップ

• コリ、R.マチ、A. (1992)。 「マップ、ハイパーマップ、およびそれらの自己同型性: 調査」。数学の解説。10 : 403–467。MR1190182  。
• Edmonds, J. (1960a). 「多面体表面の組み合わせ表現」.アメリカ数学会誌. 7 : 646.
• Edmonds, John Robert (1960b)。有向多面体表面の組合せ表現(PDF) (修士)。メリーランド大学。hdl :1903/24820。
• Gross, JL; Alpert, SR (1974). 「電流グラフの位相理論」. Journal of Combinatorial Theory, Series B. 17 ( 3): 218–233. doi : 10.1016/0095-8956(74)90028-8 . MR  0363971.
• ヘフター、L. (1891)。 「Uber das 問題 der Nachbargebiete」。数学アンナレン。38 (4): 477–508。土井：10.1007/BF01203357。S2CID  121206491。
• ヘフター、L. (1898)。 「ユーバーメタシークリッシェグルッペンとナッハバルコンティギュレーション」。数学アンナレン。50 (2-3): 261-268。土井：10.1007/BF01448067。S2CID  120691296。
• Lando, Sergei K.; Zvonkin, Alexander K. (2004).表面上のグラフとその応用. 数学科学百科事典: 低次元トポロジー II. 第 141 巻. Springer-Verlag . ISBN 978-3-540-00203-1。。
• モハール、ボヤン、トーマスセン、カーステン(2001)。表面上のグラフ。ジョンズ・ホプキンス大学出版局。ISBN 0-8018-6689-8。
• Reingold, O.; Vadhan, S.; Wigderson, A. (2002). 「エントロピー波、ジグザググラフ積、および新しい定数次数エクスパンダー」Annals of Mathematics . 155 (1): 157–187. arXiv : math/0406038 . doi :10.2307/3062153. JSTOR  3062153. MR  1888797. S2CID  120739405.
• リンゲル、G. (1965)。 「Das Geschlecht des vollständigen paaren Graphen」。ハンブルク大学アブハンドルゲン数学セミナー。28 (3-4): 139-150。土井：10.1007/BF02993245。MR  0189012。S2CID 120414651  。
• Youngs, JWT (1963). 「最小埋め込みとグラフの種数」.数学と力学ジャーナル. 12 (2): 303–315. doi : 10.1512/iumj.1963.12.12021 . MR  0145512.