Time+Place: | Tuesday 12/01/2016 14:30 Room 337-8 Taub Bld. |

Title: | The probabilistic method meets the game of Go |

Speaker: | Graham Farr - COLLOQUIUM LECTURE http://www.csse.monash.edu.au/~gfarr/ |

Affiliation: | Faculty of I.T., Monash University, Clayton, Victoria, Australia |

Host: | Johann Makowsky |

The game of Go --- known as Go or Igo in Japan, Weiqi in China and Baduk in Korea --- is one of the oldest and deepest board games in the world, and has a huge following in east Asia. Traditionally, the game involves placing black and white stones on the vertices of a square grid, usually with 19*19 vertices. But it can in fact be played on any graph G. A position is an assignment of colours from the set {Black, White} to some subset of V(G). So each vertex is Black, White or Uncoloured. A legal position is one in which each monochromatic component is adjacent to some uncoloured vertex. (A monochromatic component, or chromon, is a component of the subgraph induced by the vertices of a specific colour.) Among the most basic questions that can be asked about any game are: * How many legal positions are there? * What is the probability that a random arrangement of game elements (stones/pieces/...) on the board gives a legal position? The author introduced Go polynomials to study these questions for Go (Farr, 2003). Let q \in [0,1/2] be a probability. Suppose each vertex is, randomly and independently, coloured Black with probability q, White with probability q, and is left uncoloured with probability 1-2q. Then Go(G;q) is the probability that the resulting random position is a legal one. The author found links to the chromatic polynomial and proved that it is #P-hard to compute. In this talk, we apply probabilistic methods to study the asymptotic behaviour of Go(G;q) when G is an n*n square grid, and also when G \in G(n;p) is a Gilbert-Erdos-Renyi random graph with edge probability p. References: G E Farr, The Go polynomials of a graph, Theoretical Computer Science 306 (2003) 1--18. G E Farr and J Schmidt, On the number of Go positions on lattice graphs, Information Processing Letters 105 (2008) 124--130. Short Bio: Graham Farr is a Professor in the Faculty of Information Technology at Monash University, Australia, and Co-Convenor of the Discrete Mathematics Research Group. He did his BSc(Hons) in Pure Mathematics at the same university before completing a D.Phil. in Mathematics from the University of Oxford. His interests include graph theory, enumeration (especially Tutte-Whitney polynomials), algorithms, complexity, information theory and computer history. Since 2008 he has led Computer History Tours of Melbourne. In 2011 he received the Vice-Chancellor's Award for Excellence in Postgraduate Supervision at Monash. Refreshments will be served from 14:15 Lecture starts at 14:30