wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Monotone Paths in Graphs
        
(Message started by: william wu on Nov 8^th, 2011, 1:45pm)

Title: Monotone Paths in Graphs
Post by william wu on Nov 8^th, 2011, 1:45pm

Given an undirected connected graph with E edges, arbitrarily each edge with a unique number between 1 and E.

Show that there exists a path with monotone labels whose length is at least the average degree of the graph.

Title: Re: Monotone Paths in Graphs
Post by Michael Dagg on Nov 9^th, 2011, 8:40am

Your problem "hints" at a Ramsey theory solution using the Erdos result on increasing
or decreasing sequences of a certain length.

Title: Re: Monotone Paths in Graphs
Post by Grimbal on Nov 10^th, 2011, 6:58am

Hm... I must be missing something.

Is the "average degree" the average number of edges that meet at a vertex?

By saying that the statement is true for a random placement of labels, do you mean it is true for all placements?

Because the way I understand the problem the statement is wrong for the following graph: Take 8 edges, connect each of 1,2,3,4 with each of 5,6,7,8, giving 16 connextions. The longest monotone path is 2, the average degree is 4.

Title: Re: Monotone Paths in Graphs
Post by william wu on Nov 10^th, 2011, 11:15am

Yes, the average degree is the average # of edges that meet at a vertex. Also it is more clear to say arbitrary labeling rather than random labeling, so I will revise that in the problem statement.

The labels are also being assigned to edges, not to vertices. A path is considered monotone if the *edges* in that path are monotone.

Attached is a visualization of the bipartite graph you mentioned, where the vertices {1,2,3,4} are complete to the vertices {5,6,7,8}. We see there are many monotone paths of length >= 4, such as the sequence of edges {1,3,7,9,11}. The sixteen distinct edge labels were assigned randomly without replacement.

Title: Re: Monotone Paths in Graphs
Post by william wu on Nov 10^th, 2011, 11:19am

This problem may be too difficult without a hint, as I was simply told of the result:

Hint: [hide]
Imagine having a person standing on each vertex. A loudspeaker shouts the edges in sequence, and with each shout, the people move along the graph in a certain way.
[/hide]

Title: Re: Monotone Paths in Graphs
Post by Grimbal on Nov 10^th, 2011, 1:24pm

on 11/10/11 at 11:15:41, william wu wrote:

The labels are also being assigned to edges, not to vertices. A path is considered monotone if the *edges* in that path are monotone.

I see. Sorry. I don't know why, I always mix up the words "edge" and "vertex" in english. Really annoying. I must have learnt it wrong the first time.

OK, Now I can start thinking about the problem.

Title: Re: Monotone Paths in Graphs
Post by rmsgrey on Nov 11^th, 2011, 4:43am

on 11/10/11 at 11:19:11, william wu wrote:

Well, that hint makes it obvious:

[hideb]
Start with an empty pile of counters on each node. For each arc in order, swap the two piles at either end of the arc and add a counter to each. At the end of the process, each pile has followed a monotone path, of length equal to the number of counters in that pile.

Since the total number of counters is twice the number of arcs, which is also the sum of the degrees of the individual nodes, and the number of piles is the number of nodes, the average number of counters per pile is exactly equal to the average degree.

By the pigeonhole principle, at least one pile must have at least the average number of counters, so at least one pile must have traversed a path of length at least equal to the average degree.[/hideb]

Title: Re: Monotone Paths in Graphs
Post by Michael Dagg on Nov 11^th, 2011, 7:41am

Excellent rmsgrey!

Ramsey theory generalizes the pigeonhole principle, guaranteeing
the existence of the required monotonic path. There are lots of fruitful
results in graph/group theory similarly derived.

Title: Re: Monotone Paths in Graphs
Post by Grimbal on Nov 11^th, 2011, 9:49am

Very elegant proof, indeed!

Title: Re: Monotone Paths in Graphs
Post by mgccl on Feb 4^th, 2013, 5:37pm

on 11/11/11 at 04:43:24, rmsgrey wrote:

[hideb]
At the end of the process, each pile has followed a monotone path, of length equal to the number of counters in that pile.
[/hideb]

It followed a monotone walk instead of a path. Usually path means a simple path. So it is still unclear if the original statement is true.

Title: Re: Monotone Paths in Graphs
Post by rmsgrey on Feb 5^th, 2013, 4:34am

on 02/04/13 at 17:37:32, mgccl wrote:

It followed a monotone walk instead of a path. Usually path means a simple path. So it is still unclear if the original statement is true.

True, there's no guarantee against loops in that proof.