5
$\begingroup$

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?

$\endgroup$

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ 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. $\endgroup$ Mar 10, 2015 at 0:45
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.