Timeline for Lower bounds for inversion counting in comparison model?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7, 2015 at 20:44 | vote | accept | Ben Cousins | ||
| Mar 6, 2015 at 17:08 | comment | added | Vsevolod Oparin | @domotorp: I assumed that this was more or less obvious. | |
| Mar 6, 2015 at 17:07 | comment | added | Vsevolod Oparin | @EmilJeřábek: Yes, thank you. I proved this by counting number of inversions, but yours is much simpler. | |
| Mar 6, 2015 at 14:26 | comment | added | domotorp | You are using (without explicitly stating) that in any partial order for any two incomparable elements, $x$ and $y$, there are two possible extensions that differ only in $x$ and $y$ being swapped. This is indeed true; If every element smaller than $x$ or $y$ is smaller than them, every other element bigger, then we can swap $x$ and $y$. | |
| Mar 6, 2015 at 12:35 | comment | added | Emil Jeřábek | The parity of the number of inversions is the sign of the permutation that brings to array to sorted form. The sign of a permutation is also the parity of the length of (some/every) expression of the permutation as a product of transpositions. So, yes, a single swap changes the parity of the number of inversions, and a fortiori the number itself. | |
| Mar 6, 2015 at 5:15 | history | edited | Vsevolod Oparin | CC BY-SA 3.0 |
deleted 1 character in body
|
| Mar 6, 2015 at 5:07 | history | answered | Vsevolod Oparin | CC BY-SA 3.0 |