Cube

Definition

A subset of the Boolean hypercube [math]A \subseteq \{-1,1\}^n[/math] is a subcube if there exists a set of indices [math]S \subseteq [n][/math] and fixed numbers [math]a_i = \pm 1[/math],[math]i \in S[/math] such that

[math]A = \{x \in \{-1,1\}^n \mid x_i = a_i~ \forall i \in S \}[/math].

In words, [math]A[/math] is the set of all points where some particular coordinates are held fixed, while the other coordinates are free. A function [math]f : \{-1,1\}^n \to \{-1,1\}[/math] is called a subcube if its support is a subcube.

The number of fixed indices [math]|S|[/math] is called the codimension of the cube, while the number of free indices [math]n-|S|[/math] is called the dimension of the cube.

Properties

• A subcube of dimension [math]k[/math] has [math]2^k / 2^n[/math] vertices. Thus, subcube functions are balanced only if they are of codimension 1, i.e there is exactly one fixed index. In this case the function is either a dictator or an anti-dictator.
• If [math]a_i = 0[/math] for all [math]i[/math] then the subcube function is monotone.
• Subcubes are the only functions for which equality is attained in the isoperimetric inequality. (TODO: reference this)