Invariance principle on the slice

DOI10.4230/LIPICS.CCC.2016.15MaRDI QIDQ5368749zbMATH OpenFDO

Authors Yuval Filmus, Guy Kindler, Elchanan Mossel, Karl Wimmer

Publication date 10 October 2017

Full work available at URL https://arxiv.org/abs/1504.01689

zbMATH Keywords

invariance principlesliceJohnson association schemeanalysis of Boolean functions

Mathematics Subject Classification ID

Probability measures on topological spaces (60B05) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Combinatorial probability (60C05)

Abstract: We prove an invariance principle for functions on a slice of the Boolean cube, which is the set of all vectors {0,1}^n 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.

Recommendations

• Invariance principle on the slice
• Harmonicity and invariance on slices of the Boolean cube
• Noise stability of functions with low influences: invariance and optimality
• Harmonicity and invariance on slices of the Boolean cube
• A structure theorem for almost low-degree functions on the slice

Cited in

(13)

• Boolean function analysis on high-dimensional expanders
• Combinatorial anti-concentration inequalities, with applications
• Anticoncentration for subgraph statistics
• Harmonicity and invariance on slices of the Boolean cube
• Weightwise perfectly balanced functions with high weightwise nonlinearity profile
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Boolean constant degree functions on the slice are juntas
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• Boolean degree 1 functions on some classical association schemes
• Harmonicity and invariance on slices of the Boolean cube
• On non-optimally expanding sets in Grassmann graphs
• The Okounkov-Vershik approach to the representation theory of \(G\sim S_n\)
• Invariance principle on the slice

This page was built for publication: Invariance principle on the slice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368749)