Meshulam's game
Meshulam's game
In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam
Description The game-board is a graph G. It is a zero-sum-game for two players, CON and NON. CON wants to show that I(G), the independence complex of G, has a high connectivity; NON wants to prove the opposite.
At his turn, CON chooses an edge e from the remaining graph. NON then chooses one of two options:
- Disconnection – remove the edge e from the graph.
- Explosion – remove both endpoints of e, together with all their neighbors and the edges incident to them.
The score of CON is defined as follows:
- If at some point the remaining graph has an isolated vertex, the score is infinity;
- Otherwise, at some point the remaining graph contains no vertex; in that case the score is the number of explosions.
For every given graph G, the game value on G (i.e., the score of CON when both sides play optimally) is denoted by Ψ(G).
Game value and homological connectivity Meshulam proved that, for every graph G:<blockquote><math>\eta_H(I(G))\geq \Psi(G)</math></blockquote>where <math>\eta_H(I(G))</math> is the homological connectivity of <math>I(G)</math> plus 2.
Examples # If G is the empty graph, then Ψ(G) = 0, since no explosions are needed. #If G has k connected components, then Ψ(G) ≥ k. Regardless of the order in which CON offers edges, each explosion made by NON destroys vertices in a single component, so NON needs at least k explosions to destroy all vertices. # If G is a union of k vertex-disjoint cliques, each of which contains at least two vertices, then Ψ(G) = k, since each explosion completely destroys a single clique. # If G has an independence domination number of at least k, <math>i \gamma(G) \geq k</math>, then <math> \Psi(G)\geq k</math>. Proof: Let A be an independent set with domination number at least k. CON starts by offering all edges (a,b) where a is in A. If NON disconnects all such edges, then the vertices of A remain isolated so CON's score is infinity. If NON explodes such an edge, then the explosion removes from A only the vertices that are adjacent by b (the explosion at a does not destroy vertices of A, since A is an independent set). Therefore, the remaining vertices of A require at least k-1 vertices to dominate, so the domination number of A decreased by at most 1. Therefore, NON needs at least k explosions to destroy all vertices of A. This proves that <math> \Psi(G)\geq i\gamma(G)</math>. # Note: this also implies that <math> \Psi(L(G))\geq \nu(G)/2</math>, where <math> L(G)</math> is the line graph of G, and <math> \nu(G)</math> is the size of the largest matching in G. This is because the matchings in G are the independent sets in L(G). Each edge in G is a vertex in L(G*), and it dominates at most two edges in the matching (= vertices in the independent set). # If G is the complete bipartite graph Kn,n, and L(G) is its line graph, then <math> \Psi(L(G))\geq \lfloor 2n/3\rfloor</math>. Proof: L(G) can be seen as an n-by-n array of cells, where each row is a vertex on one side, each column is a vertex on the other side, and each cell is an edge. In the graph L(G), each cell is a vertex, and each edge is a pair of two cells in the same column or the same row. CON starts by offering two cells in the same row; if NON explodes them, then CON offers two cells in the same column; if NON explodes them again, then the two explosions together destroy 3 rows and 3 columns. Therefore, at least <math> \lfloor 2n/3\rfloor</math> explosions are required to remove all vertices. # Note: this result was generalized later: if F is any subgraph of Kn,n*, then <math> \Psi(L(G))\geq \frac{n} - \frac{n}{3} - \frac{1}{2}</math>.
Proof for the case 1 To illustrate the connection between Meshulam's game and connectivity, we prove it in the special case in which <math>\eta_H(I(G))=1</math>, which is the smallest possible value of <math>\eta_H(I(G))</math>. We prove that, in this case, <math>\Psi(G)\leq 1</math>, i.e., NON can always destroy the entire graph using at most one explosion.
<math>\eta_H(I(G))=1</math> means that <math>I(G)</math> is not connected. This means that there are two subsets of vertices, X and Y, where no edge in <math>I(G)</math> connects any vertex of X to any vertex of Y. But <math>I(G)</math> is the independence complex of G; so in G, every vertex of X is connected to every vertex of Y. Regardless of how CON plays, he must at some step select an edge between a vertex of X and a vertex of Y. NON can explode this edge and destroy the entire graph.
In general, the proof works only one way, that is, there may be graphs for which <math>\eta_H(I(G))> \Psi(G)</math>.