Discrete Mathematics and Optimization Seminar

JACQUES VERSTRAETE
University of Waterloo
Tuesday February 21st at 2.30pm
Burnside 934

Title. Large Martingale Inequalities with Combinatorial Applications.

Abstract. In this talk, we will focus on mathematical problems which may be tackled effectively using probabilistic methods. After giving some
simple examples, we introduce more advanced techniques, including martingale concentration inequalities. An application to counting
sumsets is given - these are sets of the form A + B \subset {1,2,...,N} where A + B = {a + b : a \in A, b \in B} and A,B \subset {1,2,...,N}.
This is related to the Cameron-Erdos Conjecture (1990) on counting sum-free sets, which was recently completely solved by Ben Green.
Using some Fourier analysis and some purely combinatorial theorems, we present a solution to a conjecture of Erdos (1973) on graphs.
Three open problems are given in conclusion.