Hypercube graph

Set

context $ n\in\mathbb N, n\ge 1 $
range $ V\equiv \{0,1\}^n $
definiendum $Q_n\equiv \langle V,E\rangle$
range $ k\in\mathbb N,1\le k\le n $
for all $ v,w\in V $
postulate $ \{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w) $

Discussion

The Hypercube graph, also called n-cube, has vertices all n-tuples of 0's and 1's and two such vertices are connected iff they differ in one coordinate.

Since strings with 0's and 1's of length $n$ encode the subsetsets of an n-element set, we have $|V|=2^n$. And since for each n-tuple there $n$ ways to differ from it by one digit, there are $\frac{1}{2}2^n\cdot n$ vertices.

It is also the Hesse diagram of a Boolean lattice, the powerset with elements connected iff they differ by one element.

Examples

E.g. $V(Q_2)=\{\langle 0,0\rangle,\langle 0,1\rangle,\langle 1,0\rangle,\langle 1,1\rangle\}$ and there are all but the diagonal relations are edges in the graph. Clearly $Q_n$ is just a square.

Parents

Subset of

Context

Link to graph
Log In
Improvements of the human condition