Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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. –  Hurkyl Jun 10 '12 at 5:42
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
This is perfect, and yet I have a (perhaps unfair) followup: how did you notice this observation in the first place? Is this a well-known fact (which does seem to make sense in hindsight) or did you follow so methodological process to determine the relation between a graph and the symmetry of the problem? –  Hooked Jun 13 '12 at 14:35
    
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. –  Hurkyl Jun 13 '12 at 19:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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