Rutgers Discrete Mathematics Seminar

Title: The Littlewood-Offord-Erdos problem in high dimensions

Speaker: Van Vu, Rutgers University

Date: Tuesday, April 5, 2011 2:00pm

Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ


Let v_1,..,v_n be vectors of length at least one in R^d and x_1,..,x_n be iid Bernoulli random variables. Consider the random sum S:= x_1v_1 +...+x_n v_n. Let Delta be a fixed positive constant. We would like to investigate the quantity:

rho:= sup P( S belong to B) where the sup is taken over all balls of radius Delta.

This problem is generally known as the Littlewood-Offord-Erdos problem and has been much studied in combinatorics. The value of rho was computed by Erdos in the 1940s for the case d=1. Higher dimensional cases are much less clear. In this talk, we will give a brief survey and then present a new theorem that settles a conjecture of Frankl and Furedi (posed in 1988), which extends Erdos' result to higher dimensions.

(Joint work with Terence Tao, UCLA)