Dictionary of Current Terms

• n-Dimensional Hypercube or n-cube (Q_n) - It is a graph containing 2ⁿ vertices called nodes. The nodes are numbered from 0 to (2ⁿ)-1.  An edge exists between any two nodes whose Hamming distance is 1.  Such nodes are said to be adjacent.  In other words, an n-dimensional hypercube contains 2ⁿ nodes that can be represented by the 2ⁿ binary n-tuples (Boolean vectors).  Therefore, an edge exists between any two nodes where the node numbers, in binary, differ by exactly one bit.

• Snake (also n-snake) - It is an induced, achordal path in an n-dimensional hypercube.  In other words, (1) every two nodes, or vertices, that are consecutive in the path must be adjacent to each other in the hypercube, (2) every two nodes that are not consecutive in the path must not be adjacent to each other in the hypercube, and (3) the beginning node is not adjacent to the ending node (it’s an open path).

• Coil (also, n-coil) - It is a closed path (or cycle) which resembles a snake, but with the beginning node the same as the ending node. 

• Maximal snake - It is a snake that cannot be extended without violating the achordal constraint.  A longest maximal snake (sometimes called an optimal snake) is the longest possible snake that can be formed in a given hypercube.  Maximal is not defined for coils since in order to extend a coil one of its nodes must be removed before others can be added and the original nodes are not necessarily a subset of the extension.  A longest coil is the longest possible coil that can be formed in a given hypercube.

• Transition sequence - To make a transition sequence you must first name the bits in the node numbers.  Typically the bit representing 2^j in a node number is called 'dimension j'.  In general:

1. for non-cyclic paths there are two possible transition sequences: starting from either end write down the order in which the bits change from node to node.

2. for cycles with m nodes there are 2m possible transition sequences: pick a start node and a direction and write down the order in which the bits change.

Each transition identifies the edge from one node to its neighbor based on the dimension change.  Some authors prefer using transitions numbered 1 to n, while other authors prefer transitions numbered 0 to n-1.  The former is slightly more intuitive (an 8-dimension hypercube using transition 8 to move into the 8^th dimension, while the latter corresponds to binary numbering). There is also some variation among publications related to numbering the transition from left to right or from right to left.

• Symmetric Coil - It is identified as having a transition sequence for the first half of the coil that is the same as the transition sequence for the second half. For example, the transition sequence : 1,2,3,1,2,3 represents a symmetric coil in Q₃.

• The State of the Hypercube - a set of 2ⁿ <node-state> pairs.  A node is either ON or OFF.  If all the ON nodes can be touched exactly once by starting at one of them and making moves to adjacent nodes then the hypercube state is a path.  If the end of the path is adjacent to the start then the path is also a cycle.  Paths and cycles that satisfy the achordal constraint are called snakes and coils respectively.  (It isn't really necessary to specify the OFF nodes since they are the ones that aren't ON, and note that even if we jumble up the order in which we list the ON nodes, the path they make is still uniquely defined since we use a fixed adjacency function of Hamming distance 1).
• Some operations on the state of the hypercube preserve the achordal path constraint:
  • Translation - XOR each ON node with a fixed bitmask to produce a new set of ON nodes.  There are 2ⁿ possible translations corresponding to shifting the starting node to each of the 2ⁿ nodes in the hypercube.  Translation preserves the order in which the dimensions are used.
  • Rotation - Consistently reorder the bits in all the ON nodes.  There are n! possible rotations corresponding to the n! possible ways to order the n bits.  Nodes 0 and (2ⁿ)-1 are invariant under all n! rotations.  In general, a node is invariant under (w!)((n-w)!) rotations where w is the number of bits set to 1 in its node number.  (A node's degree of rotation invariance might be an interesting node metric to investigate).

• Equivalence Class - The set of states you get by applying all (2ⁿ)(n!) possible <translation-rotation> pairs to some state of the hypercube.  When we find 2 paths are in the same equivalence class we no longer consider them distinct in any interesting way.  All snakes within the same equivalence class are synonyms of each other.

• The form of a transition sequence - Remove all but the first occurrence of each dimension from the transition sequence.  In other words, the form is the order in which the snake "uses" the dimensions, where the "usage" order of a dimension is determined by the first transition in the snake for that dimension relative to the other dimensions.  Note that there are n! possible orderings in dimension n.

• Canonical Form - A restriction on transition sequences such that dimension x cannot appear before dimension x-1 in its form.  The starting node is assumed to be node 0 so that a path written in canonical form unambiguously describes a single state of the hypercube.  The use of 'canonical' here is really a misnomer: what we would like from our 'canonical' notation is that it admit only one member of each equivalence class.  However, in general this canonical form admits up to c members of each equivalence class where:
  1. for non-cyclic paths: c = 2
  2. for cycles with m nodes: c = 2m

  Canonical snakes will always start {0,1,2} in transition sequence and {0,1,3,7} in node sequence.  Two snakes with the same canonical form are said to be synonyms.

• Rewrite in Canonical Form - Any transition sequence can be rewritten in canonical form as follows: create a map from its form to canonical form.  Use the map to re-encode the transition sequence of the path so that it is in canonical form.  For example, if a path's transition sequence starts with a 9, 9 will map to 0 and you will need to replace every occurrence of "9" with "0".

• s-Fold Symmetry - If canonical form admits k members of an equivalence class, we describe the paths in that equivalence class as having s-fold symmetry where s = c / k.  Each path in the class is invariant under s distinct <translation-rotation> pairs, and so the cardinality of that equivalence class is (2ⁿ)(n!) / s. So, 1-fold symmetry means no symmetry and c-fold symmetry means maximum possible symmetry.

• Palindrome - A non-cyclic path having maximum (2-fold) symmetry.  Why 'palindrome'? because the path's canonical form transition sequence is the same regardless of which end of the path we transcribe it from.  We might say the path is invariant under reversal which is what palindrome means.  Palindrome is not defined for cycles since there is no start or end.

• Reversal - As an operation on the hypercube state, reversal is just one of the possible (2ⁿ)(n!) <translation-rotation> pairs, although which one it is depends on the path being reversed.  For palindrome paths, the hypercube state is invariant under reversal (i.e. you get the same set of ON nodes as you started with).  Reversal is not defined for cycles since there is no start or end.