Navigation

    Voting Theory Forum

    • Register
    • Login
    • Search
    • Recent
    • Categories
    • Tags
    • Popular
    • Users
    • Groups

    A Graph Theoretical Conjecture

    Research
    2
    10
    543
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • ?
      A Former User last edited by A Former User

      Say I have a tournament graph G = (V, E) where every edge has a unique positive weight, and I have a function f: V --> V with the following property:

      • E contains (x, f(x)) for all x

      And, for all y, and z != y, f(y), then either:

      • E contains (f(y), z), or
      • There is a path in G from f(y) to z such that each edge has larger weight than (z, f(y))

      Now let x be such that (x, f(x)) is minimized. Must there be a path in G from f(x) to x where each edge has a larger weight than (x, f(x)) ?

      Any insights, proofs, or counterexamples welcomed. I've been thinking about this problem for a while now.

      Marylander 2 Replies Last reply Reply Quote 0
      • Marylander
        Marylander @Guest last edited by Marylander

        This post is deleted!
        1 Reply Last reply Reply Quote 0
        • Marylander
          Marylander @Guest last edited by Marylander

          @brozai Here is a basic detail. In any counterexample, f cannot be a single cycle, since when we take x such that (x, f(x)) is minimized, we can take the path from f(x) to x, f(x) -> f^2(x) ->... -> f^|V|(x)=x.

          Edit: If we take x such that (x,f(x)) is minimized, we can get a path from f(x) to x by repeatedly applying f and using the edge (f^i(x), f^i+1(x)). Since (x,f(x)) is minimal all of these edges will have weight higher than (x,f(x)). ((x, f(x)) will never have to be used because once x is reached, we're done.)
          We are guaranteed to reach x because f is a permutation and permutations can always be decomposed into disjoint cycles.

          ? 1 Reply Last reply Reply Quote 0
          • ?
            A Former User @Marylander last edited by

            Hi @marylander , thank you for taking the time to think about this problem.

            This is a good observation. You can construct such a graph where f creates a a single cycle by, for example, having a Hamiltonian cycle consisting of all the strongest edges in E.

            Unfortunately, f may not be injective, so it will not necessarily be a permutation. I believe, however, that we can reduce to the case where f(x) (for specifically the x as chosen to minimize (x, f(x)) has a unique preimage

            Marylander 1 Reply Last reply Reply Quote 1
            • Marylander
              Marylander @Guest last edited by Marylander

              @brozai True. Then this only shows that in any counterexample f cannot be a permutation/injective.

              ? 1 Reply Last reply Reply Quote 0
              • ?
                A Former User @Marylander last edited by

                @marylander Here is an example graph which is quite annoying, in that it shows it is possible to construct such a graph where f is not a permutation

                080a6482-2e59-484e-9635-41c69b7dd34f-image.png

                The bottom graph shows the edges selected by f

                Marylander 1 Reply Last reply Reply Quote 0
                • Marylander
                  Marylander @Guest last edited by Marylander

                  @brozai I think I found a counterexample

                  From c1 c2 c3 l0 l1 l2 b1 b2 d1
                  c1 - -98 - - - - - - -
                  c2 - - 4 - - - - LO -
                  c3 LO - - 2 - - 13 12 -
                  l0 -99 1 - - -10 - - 9 -
                  l1 LO LO LO - - -11 -8 LO -
                  l2 LO LO LO -13 - - - 20 -
                  b1 LO 3 - -7 - -9 - - -
                  b2 LO - - - - - 8 - -96
                  d1 LO LO LO -97 LO LO LO - -

                  f(c1)=c2 f(c2)=c3 f(c3)=l0
                  f(l0)=l1 f(l1)=l2 f(l2)=l0
                  f(b1)=l0 f(b2)=d1
                  f(d1)=l0

                  Edit: at the end of the row for l0, changed the last 3 values from 9/-7/- to -/9/-
                  Also changed the edge from l2 to b1 with weight -12 to an edge from b1 to l2 with weight -8.

                  ? 1 Reply Last reply Reply Quote 0
                  • ?
                    A Former User @Marylander last edited by Marylander

                    Hi @marylander ,

                    This is a great find, but remember all the edge weights should be unique! Nonetheless it's interesting to know that the conjecture does not hold in general.

                    Edit: Also, is there both an edge (l0, b1) and (b1, l0) ? I may be misinterpreting

                    Btw if you're curious for context, this is related to a question in https://arxiv.org/abs/2108.00542 that Simple Stable Voting will return a candidate in the Split Cycle set over uniquely weighted tournaments.

                    Marylander 1 Reply Last reply Reply Quote 0
                    • Marylander
                      Marylander @Guest last edited by

                      @brozai Sorry, I made a transcription error. I can upload the sketch I based the matrix on, although it is jank. At first I didn't upload it because I didn't think it would be readable adding the LO edges.

                      counter.png

                      I tweaked the example slightly as well but I don't think it was necessary.

                      ? 1 Reply Last reply Reply Quote 0
                      • ?
                        A Former User @Marylander last edited by A Former User

                        @marylander Thanks yup, this looks like a counterexample.

                        Using some of the ideas in your construction I found a slightly smaller one on 8 nodes

                        cd7a0a63-764a-466c-ab71-8fa9552bf2fb-image.png

                        1 Reply Last reply Reply Quote 0
                        • First post
                          Last post