Combinatorial games

点击翻译按钮获取中文摘要

My most successful research so far has been my study, together with Rebekah Herrman, of the `Diffusion Game' on graphs, about which we have written the paper `Uniform Bounds for Non-negativity ofthe Diffusion Game'. The diffusion game is a process in which each vertex of a graph is assigned a numerical label, representing a number of chips. These labels are updated at discrete integer time steps according to the following rule: for every edge whose endpoints have differing numbers of chips, we (simultaneously) transfer one chip from the vertex with more chips to the vertex with fewer chips. This process had previously been introduced by Duffy, Lidbetter, Messinger and Nowakowski, and further studied by Long and Narayanan. In a paper posted to arXiv last year, Long and Narayanan posed the question of whether, for a fixed number of vertics, bounding the initial number of chips on each vertex would give a constant bound on the number of chips on a vertex at any subsequent time step. We answered this question completely, if we start with at least (n - 2) chips on each vertex, then the number of chips on each vertex will remain non- negative. Furthermore, this bound is tight. We also establish a related (partial) bound based on the maximum degree of the graph; we hope to make further progress on this question in the future. These results, and subsequent questions, are discussed in detail in our aforementioned paper.