Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

The probabilistic method, developed by Erdos in 1959 roughly states that given a set A, to prove the existence of a subset B of A with property P, it suffices to prove that a properly chosen "random" subset of A has property P with positive probability. During this talk I will use the probabilistic method to give a proof (by Erdos) that every subset of non-zero integers of size n contains a sum-free subset of size > n/3. I will also say a few words about Erdos' original theorem which led to the invention of the probabilistic method, namely that for any integer k > 0, there exists a graph with chromatic number > k, and girth >k.