メシュラムのゲーム
数学ゲーム

グラフ理論において、メシュラムゲームとは、グラフの独立複体のホモロジー連結性に関するロイ・メシュラム[1]の定理を説明するために用いられるゲームである。ホモロジー連結性とは、 kを含むすべての被約ホモロジー群が自明となるような最小の指数kのことである。この定理をゲームとして定式化したのは、アハロニ、バーガー、ジヴである[2] [3] 。

説明

ゲームボードはグラフ Gです。これはCON と NON という2人のプレイヤーによるゼロサムゲームです。CON はGの独立複合体I( G ) に高い連結性があることを証明しようとします。一方、NON はその逆を証明しようとします。

CONは自分の番に、残りのグラフから 辺eを選択します。NONは次の2つの選択肢のいずれかを選択します。

  • 切断–グラフからエッジeを削除します。
  • 爆発– eの両端点と、そのすべての近傍点およびそれらに付随する辺を削除します。

CON のスコアは次のように定義されます。

  • ある時点で残りのグラフに孤立した頂点がある場合、スコアは無限大になります。
  • それ以外の場合、ある時点で残りのグラフに頂点が含まれなくなります。その場合、スコアは爆発の数になります。

与えられたグラフGごとに、G上のゲーム値（つまり、両側が最適にプレイした場合の CON のスコア）はΨ ( G ) で表されます。

ゲーム価値とホモロジー接続

メシュラム[1]は、あらゆるグラフGに対して、

η H （ 私 （ G ） ） ≥ Ψ （ G ） {\displaystyle \eta _{H}(I(G))\geq \Psi (G)}

ここで、プラス 2のホモロジー接続です。 η H （ 私 （ G ） ） {\displaystyle \eta _{H}(I(G))} 私 （ G ） {\displaystyle I(G)}

例

  1. Gが空のグラフの場合、爆発は必要ないのでΨ ( G ) = 0となります。
  2. Gにk個の連結成分がある場合、Ψ ( G ) ≥ kとなる。CON が辺を提供する順序に関わらず、NON による爆発はそれぞれ1つの成分の頂点を破壊するため、NON はすべての頂点を破壊するために少なくともk 回の爆発を必要とする。
  3. Gがk個の頂点分離クリークの和集合であり、各クリークに少なくとも 2 つの頂点が含まれている場合、爆発ごとに 1 つのクリークが完全に破壊されるため、 Ψ ( G ) = kとなります。
  4. G が少なくともkの独立支配数を持つ場合、 です。証明: A を支配数が少なくともkである独立セットとします。CON は、 a がAにあるすべてのエッジ ( a、b )を提供することから始めます。NON がそのようなエッジをすべて切断すると、 Aの頂点は孤立したままになり、CON のスコアは無限大になります。NON がそのようなエッジを爆発させると、爆発によってAからbによって隣接する頂点のみが削除されます ( A は独立セットであるため、aでの爆発ではAの頂点は破壊されません)。したがって、 Aの残りの頂点が支配するには少なくともk -1 個の頂点が必要なので、 Aの支配数は最大で 1 減少します。したがって、NON が A のすべての頂点を破壊するには少なくともk 回の爆発が必要です。これは を証明しています。 私 γ （ G ） ≥ け {\displaystyle i\gamma (G)\geq k} Ψ （ G ） ≥ け {\displaystyle \Psi (G)\geq k} Ψ （ G ） ≥ 私 γ （ G ） {\displaystyle \Psi (G)\geq i\gamma (G)}
    • 注：これはまた、 が成り立つことを意味します。ここではG の線グラフであり、はGにおける最大のマッチングのサイズです。これは、 GにおけるマッチングがL ( G )における独立集合であるためです。G の各辺はL( G )における頂点であり、マッチングにおいて最大で2つの辺（＝独立集合における頂点）を支配することになります。[3] Ψ （ L （ G ） ） ≥ ν （ G ） / 2 {\displaystyle \Psi (L(G))\geq \nu (G)/2} L （ G ） {\displaystyle L(G)} ν （ G ） {\displaystyle \nu (G)}
    • 同様に、Hがr部ハイパーグラフのとき、 . [4] Ψ （ L （ H ） ） ≥ ν （ H ） / r {\displaystyle \Psi (L(H))\geq \nu (H)/r}
  5. Gが完全な二部グラフ K n,nであり、L ( G ) がその線グラフである場合、となる。[5] [6]証明: L( G ) は n 行 n 列のセルの配列とみなすことができ、各行は一方の頂点、各列はもう一方の頂点、各セルは辺である。グラフL ( G ) において、各セルは頂点であり、各辺は同じ列または同じ行にある 2 つのセルのペアである。CON は、同じ行にある 2 つのセルを提供することから開始する。NON がそれらを爆発させると、CON は同じ列にある 2 つのセルを提供する。NON がそれらを再度爆発させると、2 回の爆発で 3 行 3 列が破壊される。したがって、すべての頂点を除去するには少なくとも 回の爆発が必要である。 Ψ （ L （ G ） ） ≥ ⌊ 2 n / 3 ⌋ {\displaystyle \Psi (L(G))\geq \lfloor 2n/3\rfloor } ⌊ 2 n / 3 ⌋ {\displaystyle \lfloor 2n/3\rfloor }
    • 注：この結果は後に一般化されました：FがKn ,nの任意のサブグラフである場合、. [3] ：Thm.3.10  Ψ （ L （ G ） ） ≥ | F | n − n 3 − 1 2 {\displaystyle \Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}}

ケース1の証明

メシュラムのゲームと連結性の関係を説明するために、（ の最小値）となる特殊なケースで証明します。この場合、、つまり、NONは常に最大1回の爆発でグラフ全体を破壊できることを証明します。 η H （ 私 （ G ） ） ＝ 1 {\displaystyle \eta _{H}(I(G))=1} η H （ 私 （ G ） ） {\displaystyle \eta _{H}(I(G))} Ψ （ G ） ≤ 1 {\displaystyle \Psi (G)\leq 1}

η H （ 私 （ G ） ） ＝ 1 {\displaystyle \eta _{H}(I(G))=1} は連結されていないことを意味します。これは、頂点の2つの部分集合XとYが存在し、X のどの頂点も Y のどの頂点にも連結されていないことを意味します。しかし、はGの独立複体 であるため、 GではXのすべての頂点はYのすべての頂点に連結されています。CON がどのようにプレイするかに関わらず、彼はある段階でXの頂点とYの頂点の間の辺を選択する必要があります。NON はこの辺を爆発させてグラフ全体を破壊することができます。 私 （ G ） {\displaystyle I(G)} 私 （ G ） {\displaystyle I(G)} 私 （ G ） {\displaystyle I(G)}

一般に、証明は一方向にのみ機能します。つまり、 となるグラフが存在する可能性があります。 η H （ 私 （ G ） ） > Ψ （ G ） {\displaystyle \eta_{H}(I(G))>\Psi(G)}

参照

参考文献

  1. ^ ab Meshulam, Roy (2003-05-01). 「支配数とホモロジー」. Journal of Combinatorial Theory, Series A. 102 ( 2): 321– 330. doi : 10.1016/S0097-3165(03)00045-1 . ISSN  0097-3165.
  2. ^ ロン、アハロニ;バーガー、イーライ。ジヴ、ラン (2007-05-01)。 「加重グラフにおける代表者の独立したシステム」。コンビナトリカ。27 (3): 253–267。土井:10.1007/s00493-007-2086-y。ISSN  0209-9683。S2CID  43510417。
  3. ^ abc アハロニ、ロン;バーガー、イーライ。コトラー、ダニ。ジヴ、ラン(2017-01-04)。 「スタインの推測について」。ハンブルク大学アブハンドルゲン数学セミナー。87 (2 ) : 203–211。arXiv : 1605.01982 。土井：10.1007/s12188-016-0160-3。ISSN  0025-5858。S2CID  119139740。
  4. ^ Haxell, Penny; Narins, Lothar; Szabó, Tibor (2018-08-01). 「Ryser予想に対する極値ハイパーグラフ」. Journal of Combinatorial Theory, Series A. 158 : 492–547 . doi : 10.1016/j.jcta.2018.04.004. ISSN  0097-3165.
  5. ^ Björner, A.; Lovász, L.; Vrećica, ST; Živaljević, RT (1994). 「チェスボード複体とマッチング複体」.ロンドン数学会誌. 49 (1): 25– 39. doi :10.1112/jlms/49.1.25. ISSN  1469-7750.
  6. ^ Shareshian, John; Wachs, Michelle L. (2009-10-01). 「対称群のハイパーグラフマッチング複体、pサイクル複体、およびQuillen複体のトップホモロジー」. Journal of Algebra . 322 (7): 2253– 2271. arXiv : 0808.3114 . doi :10.1016/j.jalgebra.2008.11.042. ISSN  0021-8693. S2CID  5259429.
「https://en.wikipedia.org/w/index.php?title=Meshulam%27s_game&oldid=1315648449」から取得