<p>The name "Boolean hypercube" is mainly just that &mdash; a name. But in one context it is useful to talk about <em>subcubes</em>. Namely, Harper's isoperimetric inequality shows that the set of measure $2^{-k}$ with least edge boundary is a co-dimension $k$ subcube.</p>

CC BY-SA 3.0
2015-03-09T20:36:56.680Z
2015-03-09T20:36:56.680Z
Yuval Filmus
<p>Strictly speaking, the "Boolean hypercube" is not the same as the set $\{0,1\}^n$. The Boolean hypercube is the <em>graph</em> whose vertices are the set $\{0,1\}^n$, and whose edges are defined as follows: two strings are adjacent if and only if they differ on exactly one bit.</p>

<p>I guess that usually, people refer to $\{0,1\}^n$ as the Boolean hypercube when they really want to think of it as a graph and not as a set of strings.</p>

CC BY-SA 3.0
2015-03-10T00:45:54.897Z
I am not sure this is really the entire picture. I think the Boolean hypercube also evokes the polytope whose vertices are $\{0, 1\}^n$. Then one can talk about the faces of this polytope and identify each face with the vertices that span it (the subcubes Yuval talks about). Or one can talk about the 1-skeleton of the polytope, which is the hypercube graph you mention.
Sasho Nikolov
CC BY-SA 3.0
2015-03-09T22:25:50.657Z
2015-03-09T22:25:50.657Z
Or Meir
<p>I used to view it just as a set of bit strings of length $n$. What does it mean for it to be the Boolean hypercube? Does viewing it from the hypercube perspective give a useful insight in a certain context?</p>

<cc.complexity-theory>
Why is $\{0,1\}^n$ referred to as the Boolean hypercube?
epsfooling
# Why is $\{0,1\}^n$ referred to as the Boolean hypercube?

(Asked by: username_0 on 2015-03-09)

I used to view it just as a set of bit strings of length $n$. What does it mean for it to be the Boolean hypercube? Does viewing it from the hypercube perspective give a useful insight in a certain context?

**Tags:** cc.complexity-theory

---

## 2 answers

### Answer by username_2 on 2015-03-09. Score: 10 | Accepted answer

Strictly speaking, the "Boolean hypercube" is not the same as the set $\{0,1\}^n$. The Boolean hypercube is the *graph* whose vertices are the set $\{0,1\}^n$, and whose edges are defined as follows: two strings are adjacent if and only if they differ on exactly one bit.

I guess that usually, people refer to $\{0,1\}^n$ as the Boolean hypercube when they really want to think of it as a graph and not as a set of strings.

> **Comments:**
> **username_3**: I am not sure this is really the entire picture. I think the Boolean hypercube also evokes the polytope whose vertices are $\{0, 1\}^n$. Then one can talk about the faces of this polytope and identify each face with the vertices that span it (the subcubes Yuval talks about). Or one can talk about the 1-skeleton of the polytope, which is the hypercube graph you mention.  

---

### Answer by username_1 on 2015-03-09. Score: 2

The name "Boolean hypercube" is mainly just that — a name. But in one context it is useful to talk about *subcubes*. Namely, Harper's isoperimetric inequality shows that the set of measure $2^{-k}$ with least edge boundary is a co-dimension $k$ subcube.


---

