Meshulam's game

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).

Meshulam{{Cite journal|last=Meshulam|first=Roy|date=2003-05-01|title=Domination numbers and homology|journal=Journal of Combinatorial Theory, Series A|language=en|volume=102|issue=2|pages=321–330|doi=10.1016/S0097-3165(03)00045-1|issn=0097-3165|doi-access=free}} proved that, for every graph G:

$\backslash eta\_H(I(G))\backslash geq\; \backslash Psi(G)$

1. If G is the empty graph, then Ψ(G) = 0, since no explosions are needed.
2. 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.
3. 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.
4. If G has an independence domination number of at least k, $i\; \backslash gamma(G)\; \backslash geq\; k$, then $\backslash Psi(G)\backslash 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 $\backslash Psi(G)\backslash geq\; i\backslash gamma(G)$.
5. * Note: this also implies that $\backslash Psi(L(G))\backslash geq\; \backslash nu(G)/2$, where $L(G)$ is the line graph of G, and $\backslash 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).
6. * Similarly, when H is an r-partite hypergraph, $\backslash Psi(L(H))\backslash geq\; \backslash nu(H)/r$.{{Cite journal|last1=Haxell|first1=Penny|last2=Narins|first2=Lothar|last3=Szabó|first3=Tibor|date=2018-08-01|title=Extremal hypergraphs for Ryser's Conjecture|journal=Journal of Combinatorial Theory, Series A|language=en|volume=158|pages=492–547|doi=10.1016/j.jcta.2018.04.004|issn=0097-3165|doi-access=}}
7. If G is the complete bipartite graph K_n,n, and L(G) is its line graph, then $\backslash Psi(L(G))\backslash geq\; \backslash lfloor\; 2n/3\backslash rfloor$.{{Cite journal|last1=Björner|first1=A.|last2=Lovász|first2=L.|last3=Vrećica|first3=S. T.|last4=Živaljević|first4=R. T.|date=1994|title=Chessboard Complexes and Matching Complexes|journal=Journal of the London Mathematical Society|language=en|volume=49|issue=1|pages=25–39|doi=10.1112/jlms/49.1.25|issn=1469-7750}}{{Cite journal|last1=Shareshian|first1=John|last2=Wachs|first2=Michelle L.|date=2009-10-01|title=Top homology of hypergraph matching complexes, p-cycle complexes and Quillen complexes of symmetric groups|url=http://www.sciencedirect.com/science/article/pii/S0021869308006315|journal=Journal of Algebra|language=en|volume=322|issue=7|pages=2253–2271|arxiv=0808.3114|doi=10.1016/j.jalgebra.2008.11.042|s2cid=5259429|issn=0021-8693}} 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 $\backslash lfloor\; 2n/3\backslash rfloor$ explosions are required to remove all vertices.
8. * Note: this result was generalized later: if F is any subgraph of K_n,n, then $\backslash Psi(L(G))\backslash geq\; \backslash frac$

   F

   {n} - \frac{n}{3} - \frac{1}{2}.{{Rp|Thm.3.10}}

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

$\backslash 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 $\backslash eta\_H(I(G))>\; \backslash Psi(G)$.

• Hall-type theorems for hypergraphs

{{Reflist}}

Category:Combinatorial game theory

Category:Homology theory

Category:Graph theory