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

Abstract:

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