A structure theorem for Boolean functions with small total influences

We show that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem in particular describes the structure of monotone set properties that do not exhibit sha...

Full description

Saved in:
Bibliographic Details
Published in:Annals of mathematics 2012-07, Vol.176 (1), p.509-533
Main Author: Hatami, Hamed
Format: Article
Language:English
Subjects:
Boolean functions
Combinatorics
Coordinate systems
Economic theory
Increasing functions
Mathematical functions
Mathematical theorems
Mathematics
Probabilities
Random variables
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We show that on every product probability space, Boolean functions with small total influences are essentially the ones that are almost measurable with respect to certain natural sub-sigma algebras. This theorem in particular describes the structure of monotone set properties that do not exhibit sharp thresholds. Our result generalizes the core of Friedgut's seminal work on properties of random graphs to the setting of arbitrary Boolean functions on general product probability spaces and improves the result of Bourgain in his appendix to Friedgut's paper.
ISSN:0003-486X
DOI:10.4007/annals.2012.176.1.9