Meshulam's Game

In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam related to the homological connectivity of the independence complex of a graph, which is the smallest index ''k'' such that all reduced homological groups up to and including ''k'' are trivial. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.

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'':

$\eta_H(I(G))\geq \Psi(G)$

where $\eta_H(I(G))$ is the homological connectivity of $I(G)$ 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'', $i \gamma(G) \geq k$, then $\Psi(G)\geq k$. ''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 $\Psi(G)\geq i\gamma(G)$.
#* Note: this also implies that $\Psi(L(G))\geq \nu(G)/2$, where $L(G)$ is the line graph of G, and $\nu(G)$ 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).
#* Similarly, when ''H'' is an ''r''-partite hypergraph, $\Psi(L(H))\geq \nu(H)/r$.
# If ''G'' is the complete bipartite graph ''K_n,n'', and ''L''(''G'') is its line graph, then $\Psi(L(G))\geq \lfloor 2n/3\rfloor$. ''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 $\lfloor 2n/3\rfloor$ explosions are required to remove all vertices.
#* Note: this result was generalized later: if ''F'' is any subgraph of ''K_n,n'', then $\Psi(L(G))\geq \frac - \frac - \frac$.

Proof for the case 1

To illustrate the connection between Meshulam's game and connectivity, we prove it in the special case in which $\eta_H(I(G))=1$, which is the smallest possible value of $\eta_H(I(G))$. We prove that, in this case, $\Psi(G)\leq 1$, i.e., NON can always destroy the entire graph using at most one explosion.

$\eta_H(I(G))=1$ means that $I(G)$ is not connected. This means that there are two subsets of vertices, ''X'' and ''Y'', where no edge in $I(G)$ connects any vertex of X to any vertex of Y. But $I(G)$ 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 $\eta_H(I(G))> \Psi(G)$.

See also

* Hall-type theorems for hypergraphs

References

{{Reflist
Combinatorial game theory
Homology theory
Graph theory