Meshulam game
From HandWiki
In combinatorics and graph theory, the Meshulam game is a game used to explain a theorem of Roy Meshulam[1] related to connectivity of graphs. The formulation of this theorem as a game is due to Aharoni, Berger and Ziv.[2][3]
The 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 G has a high connectivity.
At his turn, CON chooses an edge e from the remaining graph. NON then chooses one of two options:
- Deletion – 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[1] proved that, for every graph G, the connectivity of I(G) (the complex of independent sets of G) is at least Ψ(G).
References
- ↑ 1.0 1.1 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. http://dx.doi.org/10.1016/s0097-3165(03)00045-1.
- ↑ 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. http://dx.doi.org/10.1007/s00493-007-2086-y.
- ↑ 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. http://dx.doi.org/10.1007/s12188-016-0160-3.
 |
