James Martin: Minimax games, and locality of maximum-size matchings on random graphs

Speaker: James Martin

Title: Minimax games, and locality of maximum-size matchings on random graphs

Abstract: Take a regular $d$-ary tree of depth $n$, and put independent U[0,1] values at the leaves. Consider the following two-player game: a token starts at the root, and the two players alternate turns, at each turn moving the token from the current vertex to one of its children. The game terminates at some leaf; the first player tries to maximise the terminal value, the second player to minimise it. Pearl (1980) showed that as $n$ goes to infinity, the terminal value arising from optimal play converges to a constant. Ali Khan, Devroye and Neininger (2005) obtained a distributional limit for the terminal value under an appropriate rescaling.

If instead of a regular tree, we take some Galton-Watson tree truncated at depth $n$, there is a surprisingly rich range of behaviour. The terminal value (without rescaling) may converge to a constant, or to a distribution supported on finitely many values, or to a continuous distribution. I'll present various results (joint work with Roman Stasinski).

Now consider a large random graph, from the configuration model with a given degree distribution. Consider the set of maximum-size matchings of the graph. How large is the set of vertices that are contained in _every_ such maximum-size matching? For a given vertex, can we determine locally whether the vertex is "essential" in this way, or do we need more general information about the whole graph? These questions turn out to be closely related to the minimax game above, considered on the unimodular Galton-Watson tree which is the local limit of the random graph. Again, one observes a surprisingly rich variety of regimes, with some interesting examples of symmetry breaking (but very little is proved). I'll present various conjectures and simulations.