メシュラムのゲーム

グラフ理論において、メシュラムのゲームは、グラフの独立複体のホモロジー接続性に関するロイ・メシュラムの定理^{[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に対して次のことを証明した。

${\displaystyle \eta _{H}(I(G))\geq \Psi (G)}$

ここで、プラス 2 のホモロジー接続です。${\displaystyle \eta _{H}(I(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 回の爆発が必要です。これは であることを証明します。 ${\displaystyle i\gamma (G)\geq k}$${\displaystyle \Psi (G)\geq k}$${\displaystyle \Psi (G)\geq i\gamma (G)}$
   • 注: これは も意味します。ここではG の線グラフ、 はGにおける最大のマッチングのサイズです。これは、 GにおけるマッチングがL ( G )における独立集合であるためです。Gにおける各辺は L( G )における頂点であり、マッチングにおいて最大で 2 つの辺 (= 独立集合における頂点) を支配します。^[3]${\displaystyle \Psi (L(G))\geq \nu (G)/2}$${\displaystyle L(G)}$${\displaystyle \nu (G)}$
   • 同様に、Hがr部ハイパーグラフのとき、 . ^[4]${\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 列が破壊されます。したがって、すべての頂点を除去するには少なくとも 1 回の爆発が必要である。 ${\displaystyle \Psi (L(G))\geq \lfloor 2n/3\rfloor }$ ${\displaystyle \lfloor 2n/3\rfloor }$
   • 注：この結果は後に一般化されました：FがKn _,nの任意のサブグラフである場合、. ^{[3] ：Thm.3.10}${\displaystyle \Psi (L(G))\geq {\frac {|F|}{n}}-{\frac {n}{3}}-{\frac {1}{2}}}$

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

${\displaystyle \eta _{H}(I(G))=1}$は接続されていないことを意味します。つまり、頂点のサブセットXとYが 2 つあり、 のどの辺もX のどの頂点も Y のどの頂点にも接続していません。しかし、 はGの独立複体 です。したがって、 Gでは、 Xのすべての頂点はYのすべての頂点に接続されています。 CON のプレイ方法に関係なく、ある段階でXの頂点とYの頂点の間の辺を選択する必要があります。 NON はこの辺を爆発させてグラフ全体を破壊できます。 ${\displaystyle I(G)}$${\displaystyle I(G)}$${\displaystyle I(G)}$

一般に、証明は一方向にしか機能しません。つまり、 となるグラフが存在する可能性があります。 ${\displaystyle \eta _{H}(I(G))>\Psi (G)}$

• ハイパーグラフのホール型定理