Difference between revisions of "Cube"
m (→Properties) |
m |
||
| Line 14: | Line 14: | ||
* A subcube of dimension <math>k</math> has <math>2^k / 2^n</math> vertices. Thus, subcube functions are [[balanced function | 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. | * A subcube of dimension <math>k</math> has <math>2^k / 2^n</math> vertices. Thus, subcube functions are [[balanced function | 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 function | monotone]]. | * If <math>a_i = 0</math> for all <math>i</math> then the subcube function is [[monotone function | monotone]]. | ||
| − | * Subcubes are the only functions for which equality is attained in the [[Functional_inequalities#An_approximation | isoperimetric inequality]]. | + | * Subcubes are the only functions for which equality is attained in the [[Functional_inequalities#An_approximation | isoperimetric inequality]]. <ref>Introduction of [http://leibniz.cs.huji.ac.il/tr/989.pdf Edge-isoperimetric inequalities and influences] by Falik and Samorodnitksy</ref> |
== References == | == References == | ||
<references/> | <references/> | ||
Latest revision as of 14:04, 5 April 2021
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. [1]
References
- ↑ Introduction of Edge-isoperimetric inequalities and influences by Falik and Samorodnitksy
