Invariance principle on the slice

2015/04/07 by Filmus, Yuval, Kindler, Guy, Mossel, Elchanan +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1504.01689

Abstract

We prove an invariance principle for functions on a slice of the Boolean cube, which is the set of all vectors 0,1ⁿ with Hamming weight k. Our invariance principle shows that a low-degree, low-influence function has similar distributions on the slice, on the entire Boolean cube, and on Gaussian space. Our proof relies on a combination of ideas from analysis and probability, algebra and combinatorics. Our result imply a version of majority is stablest for functions on the slice, a version of Bourgain's tail bound, and a version of the Kindler-Safra theorem. As a corollary of the Kindler-Safra theorem, we prove a stability result of Wilson's theorem for t-intersecting families of sets, improving on a result of Friedgut.

Cited by

• A Near-Optimal Polynomial Distance Lemma Over Boolean Slices

Related

• Harmonicity and invariance on slices of the Boolean cube
• An Invariance Principle for the Multi-slice, with Applications
• Noise stability of functions with low influences: invariance and optimality
• A Dense Model Theorem for the Boolean Slice
• Boolean constant degree functions on the slice are juntas