University of Cambridge > > Probability > Percolation games

Percolation games

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Perla Sousi.

Let G be a graph (directed or undirected), and let v be some vertex of G. Two players play the following game. A token starts at v. The players take turns to move, and each move of the game consists of moving the token along an edge of the graph, to a vertex that has not yet been visited. A player who is unable to move loses the game. If the graph is finite, then one player or the other must have a winning strategy. In the case of an infinite graph, it may be that, with optimal play, the game continues for ever.

I’ll focus in particular on games played on the lattice Z^d, directed or undirected, with each vertex deleted independently with some probability p. In the directed case, the question of whether draws occur is closely related to ergodicity for certain probabilistic cellular automata, and to phase transitions for the hard-core model. In the undirected case, I’ll describe connections to bootstrap percolation and to maximum-cardinality matchings and independent sets.

This includes joint work with Alexander Holroyd, Irène Marcovici, Riddhipratim Basu, and Johan Wästlund.

This talk is part of the Probability series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity