This is Anita Liebenau's talk "What is ... the probabilistic method?" at the "What is ...?" seminar. The talk was given on Friday, December 3, 12:30pm at the BMS Loft at Urania.

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.

For more "What is ...?" seminar videos, visit

Loading more stuff…

Hmm…it looks like things are taking a while to load. Try again?

Loading videos…