In graph theory, Meshulam's game is a game used to explain a theorem of Roy Meshulam[1] 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.
[2][3] 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: The score of CON is defined as follows: 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).
Meshulam[1] proved that, for every graph G:
To illustrate the connection between Meshulam's game and connectivity, we prove it in the special case in which
, i.e., NON can always destroy the entire graph using at most one explosion.
This means that there are two subsets of vertices, X and Y, where no edge in
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