Results 1 to 4 of 4

Math Help - Inversions

  1. #1
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782

    Inversions

    Hello!

    I'm not quite understanding this idea of inversions. I know that if \pi is a permutation, then a pair (i,j) is an inversion if (i-j)(\pi (i)- \pi (j))<0.

    The graph of \pi has i and j as adjacent iff (i,j) is an inversion.

    I think I understand that. I have this big problem though:

    Suppose \pi=(1234). These are the points 1,2,3,4 connected in a square shape. Clearly 1 and 2 are adjacent.

    But, the formula gives for (1,2) (this is just a pair, it isn't permutation notation?), (1-2)(2-3)>0.

    I can't see why this is wrong, \pi(1)=2 and \pi(2)=3 since we're just following the path around the square.

    Can someone explain why this is wrong?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    I think we need to double-check the definitions. This statement looks suspicious:

    The graph of has and as adjacent iff is an inversion.
    What is the graph of a permutation? Is it the directed graph with edges \{(i,j)\mid\pi(i)=j\}? If (i, j) is an inversion according to your definition, it is not required that \pi(i)=j.

    By the way, how do you write permutations? E.g., is (1234) the identity permutation or a cycle 1->2->3->4->1?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Showcase_22's Avatar
    Joined
    Sep 2006
    From
    The raggedy edge.
    Posts
    782
    I normally write permutations as cycles. It was how I first learnt how to do them, and I think they usually show cycles better (or at least I think so anyway!).

    I have the definition in front of me:

    "The graph of permutation \pi, denoted G[\pi], has \{1,2, \ldots , n \} as it's vertex set with i and j being adjacent iff (i,j) is an inversion.

    So if i'm calculating inversions properly, the graph (1,2,3,4) (as a cycle) wouldn't be a permutation graph. Maybe that's what's going wrong? =S
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    the graph (1,2,3,4) (as a cycle) wouldn't be a permutation graph.
    Yes, according to this definition, the graph of the permutation (1234) has edges (1,4), (2,4) and (3,4).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of inversions
    Posted in the Advanced Algebra Forum
    Replies: 6
    Last Post: November 14th 2010, 12:04 PM
  2. Proof regarding inversions
    Posted in the Geometry Forum
    Replies: 0
    Last Post: March 11th 2010, 02:12 PM
  3. Another IRV question... Inversions
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: February 25th 2009, 03:49 PM
  4. Inversions of a permutation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2008, 01:22 PM
  5. Using MergeSort to count Inversions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 17th 2007, 03:18 PM

Search Tags


/mathhelpforum @mathhelpforum