Category:Monotone function

Definition

For two vectors [math]x,y \in \{-1,1\}^n[/math], define a partial order relation by

[math]x \leq y \iff x_i \leq y_i ~~ \forall i = 1\ldots n.[/math]

A monotone Boolean function is a Boolean function [math]f:\{-1,1\}^n \to \{-1,1\}[/math] which is monotone in its input:

[math]x \leq y \Rightarrow f(x) \leq f(y) [/math].

Properties

• The [math]i[/math]-th influence of a monotone function is equal to its first level Fourier coefficient: [math]\mathrm{Inf}_i(f) = \widehat{f}(\{i\})[/math].
• For monotone functions, the total influence is bounded by the square root of the partition size: [math]\mathrm{Inf}(f) \leq \sqrt{\log(P(f))}[/math] ^[1].

• TODO: Add properties about stability and noise sensitivity. See Mossel and O'Donnell.

References