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 math.fu-berlin.de/w/Math/WhatIsSeminar