Randomness to the rescue: If in doubt, flip a coin
Professor Deryk Osthus
Professor in Graph Theory
School of Mathematics
College of Engineering and Physical Sciences
TIme and place information
Lecture Theatre 7, Arts building (followed by a drinks reception in the Mason Lounge)
Wednesday 26 March, 2014 (5:15pm)
Graphs are very simple objects which can be used to model surprisingly complex structures. For example, this includes internet graphs, social networks, and biological networks such as the brain. However, many of the problems arising from these models are too large to be handled directly and cannot be solved by computers.
This is where coin-flipping comes in: firstly, a very successful approach to understanding the structure of complex networks such as the internet has been to model these networks by random graphs. Secondly, randomized decisions are a surprisingly useful tool to solve problems which have resisted other approaches for decades. I will discuss examples of such problems which are motivated by timetabling and scheduling as well as results on the distribution of prime numbers.
Registration for this event is now closed. Read an article on Professor Osthus' lecture here