# Cube

## Definition

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

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

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

The number of fixed indices $|S|$ is called the codimension of the cube, while the number of free indices $n-|S|$ is called the dimension of the cube.

## Properties

• A subcube of dimension $k$ has $2^k / 2^n$ 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 $a_i = 0$ for all $i$ then the subcube function is monotone.
• Subcubes are the only functions for which equality is attained in the isoperimetric inequality. (TODO: reference this)