Jump to content

Meshulam's game

From Wikipedia, the free encyclopedia

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]

Description

[edit]

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

[edit]

Meshulam[1] proved that, for every graph G:

where is the homological connectivity of plus 2.

Examples

[edit]
  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, , then . 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 .
    • Note: this also implies that , where is the line graph of G, and 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).[3]
    • Similarly, when H is an r-partite hypergraph, .[4]
  5. If G is the complete bipartite graph Kn,n, and L(G) is its line graph, then .[5][6] 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 explosions are required to remove all vertices.
    • Note: this result was generalized later: if F is any subgraph of Kn,n, then .[3]: Thm.3.10 

Proof for the case 1

[edit]

To illustrate the connection between Meshulam's game and connectivity, we prove it in the special case in which , which is the smallest possible value of . We prove that, in this case, , i.e., NON can always destroy the entire graph using at most one explosion.

means that is not connected. This means that there are two subsets of vertices, X and Y, where no edge in connects any vertex of X to any vertex of Y. But 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 .

See also

[edit]

References

[edit]
  1. ^ a b Meshulam, Roy (2003-05-01). "Domination numbers and homology". Journal of Combinatorial Theory, Series A. 102 (2): 321–330. doi:10.1016/S0097-3165(03)00045-1. ISSN 0097-3165.
  2. ^ Aharoni, Ron; Berger, Eli; Ziv, Ran (2007-05-01). "Independent systems of representatives in weighted graphs". Combinatorica. 27 (3): 253–267. doi:10.1007/s00493-007-2086-y. ISSN 0209-9683. S2CID 43510417.
  3. ^ a b c Aharoni, Ron; Berger, Eli; Kotlar, Dani; Ziv, Ran (2017-01-04). "On a conjecture of Stein". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. 87 (2): 203–211. doi:10.1007/s12188-016-0160-3. ISSN 0025-5858. S2CID 119139740.
  4. ^ Haxell, Penny; Narins, Lothar; Szabó, Tibor (2018-08-01). "Extremal hypergraphs for Ryser's Conjecture". Journal of Combinatorial Theory, Series A. 158: 492–547. doi:10.1016/j.jcta.2018.04.004. ISSN 0097-3165.
  5. ^ Björner, A.; Lovász, L.; Vrećica, S. T.; Živaljević, R. T. (1994). "Chessboard Complexes and Matching Complexes". Journal of the London Mathematical Society. 49 (1): 25–39. doi:10.1112/jlms/49.1.25. ISSN 1469-7750.
  6. ^ Shareshian, John; Wachs, Michelle L. (2009-10-01). "Top homology of hypergraph matching complexes, p-cycle complexes and Quillen complexes of symmetric groups". Journal of Algebra. 322 (7): 2253–2271. arXiv:0808.3114. doi:10.1016/j.jalgebra.2008.11.042. ISSN 0021-8693. S2CID 5259429.