# Differences

This shows you the differences between two versions of the page.

 hypercube_graph [2014/02/10 23:14]nikolaj hypercube_graph [2014/03/21 11:11] (current) Both sides previous revision Previous revision 2014/02/10 23:22 nikolaj 2014/02/10 23:14 nikolaj 2014/02/10 23:10 nikolaj created Next revision Previous revision 2014/02/10 23:22 nikolaj 2014/02/10 23:14 nikolaj 2014/02/10 23:10 nikolaj created Line 1: Line 1: ===== Hypercube graph ===== ===== Hypercube graph ===== ==== Set ==== ==== Set ==== - | @#88DDEE: $n\in\mathbb N, n\ge 1$ | + | @#55CCEE: context ​    | @#55CCEE: $n\in\mathbb N, n\ge 1$ | - | @#DDDDDD: $V\equiv \{0,1\}^n$ | + | @#DDDDDD: range       | @#DDDDDD: $V\equiv \{0,1\}^n$ | - | @#FFBB00: $Q_n\equiv \langle V,E\rangle$ | + | @#FFBB00: definiendum ​| @#FFBB00: $Q_n\equiv \langle V,E\rangle$ | - | @#DDDDDD: $k\in\mathbb N,1\le k\le n$ | + | @#DDDDDD: range       | @#DDDDDD: $k\in\mathbb N,1\le k\le n$ | - | @#FFFDDD: $v,w\in V$ | + | @#FFFDDD: for all     | @#FFFDDD: $v,w\in V$ | - | @#55EE55: $\{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w)$ | + | @#55EE55: postulate ​  | @#55EE55: $\{v,w\}\in E\leftrightarrow \exists!k.\ \pi_k(v)\neq\pi_k(w)$ | ==== Discussion ==== ==== 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. 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. 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 ==== ==== Parents ==== === Subset of === === Subset of === [[k-regular graph]], [[Bipartite graph]] [[k-regular graph]], [[Bipartite graph]] - === Requirements ​=== + === Context ​=== [[Cartesian product]] [[Cartesian product]]