|
|
Discrete Mathematics and Optimization Seminar
|
Jan 17th, 2011
|
Graph colouring
via the probabilistic method
Bruce Reed
McGill
|
|
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.
|
|
|
|