Meshulams hra - Meshulams game - Wikipedia

v teorie grafů, Meshulamova hra je hra používaná k vysvětlení věty o Roy Meshulam^[1] související s homologická konektivita z komplex nezávislosti grafu, což je nejmenší index k tak, že všechny redukované homologické skupiny až do k jsou triviální. Formulování této věty jako hry je zásluhou Aharoniho, Bergera a Ziva.^[2][3]

Popis

Herní plán je a graf G. Je to hra s nulovým součtem pro dva hráče, CON a NON. CON chce ukázat, že já (G), komplex nezávislosti z G, má vysokou připojení; NON chce dokázat opak.

V jeho tahu si CON vybere výhodu E ze zbývajícího grafu. NON poté zvolí jednu ze dvou možností:

• Odpojení - odstraňte okraj E z grafu.
• Exploze - odstranit oba koncové body E, společně se všemi svými sousedy a hranami, které s nimi souvisejí.

Skóre CON je definováno takto:

• Pokud má v určitém okamžiku zbývající graf izolovaný vrchol, je skóre nekonečno;
• Jinak zbývající graf v určitém okamžiku neobsahuje žádný vrchol; v takovém případě je skóre počet výbuchů.

Pro každý daný graf G, hodnota hry na G (tj. skóre CON, když obě strany hrají optimálně) je označeno Ψ(G).

Hodnota hry a homologická konektivita

Meshulam^[1] dokázal, že pro každý graf G:

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

kde ${ displaystyle eta _ {H} (I (G))}$ je homologická konektivita ${ displaystyle I (G)}$ plus 2.

Příklady

1. jáF G má k připojené komponenty Ψ(G) ≥ k. Bez ohledu na pořadí, ve kterém CON nabízí hrany, každá exploze způsobená NON ničí vrcholy v jedné složce, takže NON potřebuje alespoň k výbuchy zničit všechny vrcholy.

2. Li G je svazek k vertex-disjunktní kliky, z nichž každá obsahuje alespoň dva vrcholy Ψ(G) = k, protože každá exploze úplně zničí jednu kliku.

3. Li G má nezávislost dominantní číslo nejméně k, ${ displaystyle i gamma (G) geq k}$, pak ${ displaystyle Psi (G) geq k}$. Důkaz: Nechte A být nezávislou sadou s alespoň počtem dominancí k. CON začíná nabídkou všech hran (A,b) kde A je v A. Pokud NON odpojí všechny takové hrany, pak vrcholy A zůstaňte izolovaní, takže skóre CON je nekonečno. Pokud NON vybuchne takovou hranu, pak se výbuch odstraní A pouze vrcholy, které sousedí s b (výbuch v A nezničí vrcholy A, protože A je nezávislá množina). Proto zbývající vrcholy A vyžadovat alespoň k-1 vrcholy k dominování, takže počet dominancí A snížena o maximálně 1. Proto NON potřebuje minimálně k výbuchy zničit všechny vrcholy A. To dokazuje ${ displaystyle Psi (G) geq i gama (G)}$.

• Poznámka: to také naznačuje ${ displaystyle Psi (L (G)) geq nu (G) / 2}$, kde ${ displaystyle L (G)}$ je hranový graf G a ${ displaystyle nu (G)}$ je velikost největší shody v G. Důvodem je, že shody v G jsou nezávislé soubory L(G). Každá hrana dovnitř G je vrchol v L (G), a dominuje maximálně dvěma hranami ve shodě (= vrcholy v nezávislé sadě). ^[3]
• Podobně, když H je r- částečný hypergraf, ${ displaystyle Psi (L (H)) geq nu (H) / r}$.^[4]

4. Li G je kompletní bipartitní graf K._{n, n}, pak ${ displaystyle Psi (L (G)) geq lfloor 2n / 3 rfloor}$.^[5][6] Důkaz: L (G) lze chápat jako pole buněk n-by-n, kde každý řádek je vrchol na jedné straně, každý sloupec je vrchol na druhé straně a každá buňka je hrana. V grafu L(G), každá buňka je vrchol a každá hrana je dvojice dvou buněk ve stejném sloupci nebo ve stejném řádku. CON začíná nabídnutím dvou buněk ve stejné řadě; pokud je NON nevybuchne, pak CON nabídne dvě buňky ve stejném sloupci; pokud je NON znovu nevybuchne, pak obě exploze společně zničí 3 řady a 3 sloupce. Proto alespoň ${ displaystyle lfloor 2n / 3 rfloor}$ k odstranění všech vrcholů jsou nutné výbuchy.

• Poznámka: tento výsledek byl zobecněn později: pokud F je jakýkoli podgraf K._{n, n}, pak ${ displaystyle Psi (L (G)) geq { frac {| F |} {n}} - { frac {n} {3}} - { frac {1} {2}}}$.^{[3]:Thm. 3.10}

Důkaz pro případ 1

Abychom ilustrovali souvislost mezi Meshulamovou hrou a konektivitou, dokazujeme to ve zvláštním případě ${ displaystyle eta _ {H} (I (G)) = 1}$, což je nejmenší možná hodnota ${ displaystyle eta _ {H} (I (G))}$. Dokazujeme, že v tomto případě ${ displaystyle Psi (G) leq 1}$, tj. NON může vždy zničit celý graf pomocí maximálně jedné exploze.

${ displaystyle eta _ {H} (I (G)) = 1}$ znamená, že ${ displaystyle I (G)}$ není připojen. To znamená, že existují dvě podmnožiny vrcholů, X a Y, kde není hrana dovnitř ${ displaystyle I (G)}$ spojuje jakýkoli vrchol X s jakýmkoli vrcholem Y. Ale ${ displaystyle I (G)}$ je komplex nezávislosti z G; tak dovnitř G, každý vrchol X je spojen s každým vrcholem Y. Bez ohledu na to, jak CON hraje, musí v určitém kroku vybrat hranu mezi vrcholem X a vrchol Y. NON nemůže tento okraj explodovat a zničit celý graf.

Obecně platí, že důkaz funguje pouze jedním způsobem, to znamená, že mohou existovat grafy, pro které ${ displaystyle eta _ {H} (I (G))> Psi (G)}$.

Viz také

• Hallovy věty pro hypergrafy

Reference