Timeline for characterization of trees in terms of products of transpositions
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 13, 2010 at 15:08 | history | edited | darij grinberg | CC BY-SA 2.5 |
ah, that's what you meant
|
| Jul 21, 2010 at 17:43 | vote | accept | user7760 | ||
| Jul 20, 2010 at 22:16 | comment | added | Yuval Filmus | I modified the proof, hopefully now it does work. | |
| Jul 20, 2010 at 22:16 | history | edited | Yuval Filmus | CC BY-SA 2.5 |
Fixed the proof
|
| Jul 20, 2010 at 21:58 | history | edited | Yuval Filmus | CC BY-SA 2.5 |
The proof is broken!
|
| Jul 20, 2010 at 21:30 | comment | added | user7760 | I do not follow your fourth paragraph. Consider the graph with edges $(51)(53)(54)(52)(12)(23)(41)(34)$. It contains a cycle on $\lbrace 1, 2, 3, 4 \rbrace$. In your notation, let $\pi = (51)(53)(54)(52) = (51342)$. Let $i=1$ and $j=4$. Then $\sigma = (12)(23)(41)(34)$ which does indeed equal $(14)(23)$. Thus $\tau = (2 3)$, which does not contain 1 or 4. However $\pi (i j) \tau = (1 2 5 4 3)$, a big cycle. Yet 1 and 4 are in the same cycle of $\pi$. | |
| Jul 20, 2010 at 15:54 | comment | added | Yuval Filmus | If the graph is not connected, then either there are less than n-1 edges or there's a cycle. Less than n-1 transpositions cannot multiply to a big cycle. | |
| Jul 20, 2010 at 7:39 | comment | added | Benoît Kloeckner | You should add the easy case of a non-connected graph. | |
| Jul 20, 2010 at 2:35 | history | answered | Yuval Filmus | CC BY-SA 2.5 |