What is … the probabilistic method?

This page hosts information on Anita Liebenau's talk "What is … the probabilistic method?" at the "What is …?" seminar. The talk will take place on Friday, December 3, 12:30pm at the BMS Loft at Urania. This talk will help you better understand the talk by Joel Spencer, which will start at 2pm.

Before the talk by Anita Liebenau, there will be a screening of a movie "N is a Number: A Portrait of Erdös" at 10:30 at Urania.

We will again be ordering delivery pizza. If you would like to order pizza with us, please arrive to the "What is …?" seminar on time.

Abstract

To give an idea of the power of probabilistic arguments in graph theory, I will show two results of different flavour. The first comprises the statement that for an arbitrary graph G there a is partition of the vertices such that the resulting bipartite graph has at least half the number of edges of G. For the second, I will introduce the random graph model G(n,p) and the notion of a threshold function. We will then take a short look at the property of having isolated vertices.

Hopefully, this will pave the way to a better understanding of the talk by Joel Spencer for people from outside the area.

Video

The video for Anita's talk can be found at http://vimeo.com/23045254.

Comments