Please see the picture bellow about the definition of the nodes of the d-dimensional Hypercube. Could anyone please tell me what does that notation means. I get confused with the superscript after the curly braces. What does that mean in set theory.

Nodes: $(x_1,\ldots,x_d)\in\{0,1\}^d$

Edges: $\forall i:(x_1,\ldots,x_d)\to(x_1,..,1-x_i,.. ,x_d)$

What does this mean? How are the nodes and the edges defined formally?



Here $\{0,1\}^d = \{0,1\} \times \{0,1\} \times \cdots \{0,1\}$ is just the Cartesian product $d$ copies of the set $\{0,1\}$. Thus the nodes $(x_1, x_2, \dots, x_d) \in \{0,1\}^d \subseteq \mathbb{R}^d$ are just a vectors which we can think of as living in $\mathbb{R}^d$ where the components all have value 0 or 1. Then the edges of your graph just connect nodes that differ in exactly one component.

You can also think of $\{0,1\}^d$ as binary strings of length $d$, there is a clear bijection between the vectors described above and binary string of length $d$. Sometimes $\{0,1\}^d$ used to denote this set of strings, but the rest of your notation suggests the vector interpretation.

Try drawing the cases for $d=2$ and $d=3$ you should get a square and cube respectively.

  • $\begingroup$ so lets see if I understood it correctly: this notation "(x1,x2,…,xd)" represents a single node? @JMac31 $\endgroup$ – Kristof Tak Jun 19 '14 at 13:12
  • $\begingroup$ Yes $(x_1,x_2,\dots,x_d)$ is a single node. $\endgroup$ – John Machacek Jun 19 '14 at 13:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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