Discrete Mathematics and Optimization Seminar
Jan 17th, 2011
Graph colouring via the probabilistic method
Bruce Reed
Abstract: The term Probabilistic Method refers to the proof of deterministic statements using probabilistic tools. The method has been successfully applied to a number of problems in the field of graph colouring. We survey some of the results thereby obtained. The talk is intended to be accessible and short on details. We will first define graph colouring, and explain the type of graph colouring problems which tend to attract interest. We then explain the probabilistic tools which are used to solve them, and why we would expect the type of tools that are used to be effective for solving the types of problems typically studied.