1
$\begingroup$

Take a bracelet with colored beads on it. Normally two bracelets belong to the same equivalence class under rotations and reflections. For an example, consider the bracelet denoted by the word abcdec:

cabcde ecabcd decabc cdecab ... (rotations) cedcba dcbace ... (reflections) 

Consider the larger class where two bracelets are equivalent if all local bead pairings are preserved. From our example we have the multiset {ab, bc, cd, de, ec, ca}. The right-left ordering, ba vs ab doesn't matter. Clearly rotations and reflections preserve bead pairings, but so does:

abcedc 

where we've transposed the e and the d. How do you describe this symmetry?

  • 2
    If it helps, your bead pairings are the edges of a multi-graph, and a word in the equivalence class is the same thing as a Euler circuit of the graph.2012-06-10

1 Answers 1

3

We can interpret the bead pairings as the edges in a multi-graph whose vertices are the bead labels. Each words in the corresponding equivalence class corresponds to the sequence of vertices in a Euler circuit of the graph, and vice versa.

We get a one-to-one correspondence if we consider multiple edges between a pair of vertices to be indistinguishable, so that a Euler circuit is completely determined by its vertices.

  • 0
    Nothing deep; a graph is just one way to gather a collection of pairs together. Adjacency graphs are a typical application of graphs, and you had even mentioned graphs in a previous version your question. So with that on my mind, I speculatively considered how the problem would look phrased in those terms, and it happened to turn out rather nicely.2012-06-13