Concentration on the Boolean hypercube via pathwise stochastic analysis

We develop a new technique for proving concentration inequalities which relate between the variance and influences of Boolean functions. Using this technique, we 1. Settle a conjecture of Talagrand [Tal97], proving that

where h f (x) is the number of edges at x along which f changes its value, and Inf i (f ) is the influence of the i-th coordinate. 2. Strengthen several classical inequalities concerning the influences of a Boolean function, showing that near-maximizers must have large vertex boundaries. An inequality due to Talagrand states that for a Boolean function f , Var (f

. We give a lower bound for the size of the vertex boundary of functions saturating this inequality. As a corollary, we show that for sets that satisfy the edge-isoperimetric inequality or the Kahn-Kalai-Linial inequality up to a constant, a constant proportion of the mass is in the inner vertex boundary.