# Category:Monotone function

## Definition

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

$x \leq y \iff x_i \leq y_i ~~ \forall i = 1\ldots n.$

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

$x \leq y \Rightarrow f(x) \leq f(y)$.

## Properties

• The $i$-th influence of a monotone function is equal to its first level Fourier coefficient: $\mathrm{Inf}_i(f) = \widehat{f}(\{i\})$.
• For monotone functions, the total influence is bounded by the square root of the partition size: $\mathrm{Inf}(f) \leq \sqrt{\log(P(f))}$ [1].
• TODO: Add properties about stability and noise sensitivity. See Mossel and O'Donnell.

## Pages in category "Monotone function"

The following 10 pages are in this category, out of 10 total.