wu :: forums « wu :: forums - Monotone Paths in Graphs » Welcome, Guest. Please Login or Register. Sep 21st, 2018, 8:13pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Grimbal, towr, william wu, ThudnBlunder, Eigenray, Icarus, SMQ)    Monotone Paths in Graphs « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Monotone Paths in Graphs  (Read 8404 times)
william wu

Gender:
Posts: 1291
 Monotone Paths in Graphs   « on: Nov 8th, 2011, 1:45pm » Quote Modify

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.
 « Last Edit: Nov 10th, 2011, 11:39am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Michael Dagg
Senior Riddler

Gender:
Posts: 497
 Re: Monotone Paths in Graphs   « Reply #1 on: Nov 9th, 2011, 8:40am » Quote Modify

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

Regards,
Michael Dagg
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7408
 Re: Monotone Paths in Graphs   « Reply #2 on: Nov 10th, 2011, 6:58am » Quote Modify

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.
 « Last Edit: Nov 10th, 2011, 1:25pm by Grimbal » IP Logged
william wu

Gender:
Posts: 1291
 Re: Monotone Paths in Graphs   montone_paths.png « Reply #3 on: Nov 10th, 2011, 11:15am » Quote Modify

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.

 « Last Edit: Nov 10th, 2011, 11:16am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu

Gender:
Posts: 1291
 Re: Monotone Paths in Graphs   « Reply #4 on: Nov 10th, 2011, 11:19am » Quote Modify

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

Hint:
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.
 « Last Edit: Nov 10th, 2011, 11:19am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7408
 Re: Monotone Paths in Graphs   « Reply #5 on: Nov 10th, 2011, 1:24pm » Quote Modify

on Nov 10th, 2011, 11:15am, 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.
 « Last Edit: Nov 10th, 2011, 1:30pm by Grimbal » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: Monotone Paths in Graphs   « Reply #6 on: Nov 11th, 2011, 4:43am » Quote Modify

on Nov 10th, 2011, 11:19am, william wu wrote:
 This problem may be too difficult without a hint, as I was simply told of the result:   Hint: 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.

Well, that hint makes it obvious:

 hidden: 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.
 IP Logged
Michael Dagg
Senior Riddler

Gender:
Posts: 497
 Re: Monotone Paths in Graphs   « Reply #7 on: Nov 11th, 2011, 7:41am » Quote Modify

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.
 IP Logged

Regards,
Michael Dagg
Grimbal
wu::riddles Moderator
Uberpuzzler

Gender:
Posts: 7408
 Re: Monotone Paths in Graphs   « Reply #8 on: Nov 11th, 2011, 9:49am » Quote Modify

Very elegant proof, indeed!
 IP Logged
mgccl
Newbie

Posts: 1
 Re: Monotone Paths in Graphs   « Reply #9 on: Feb 4th, 2013, 5:37pm » Quote Modify

on Nov 11th, 2011, 4:43am, rmsgrey wrote:

 hidden: At the end of the process, each pile has followed a monotone path, of length equal to the number of counters in that pile.

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.
 « Last Edit: Feb 4th, 2013, 5:39pm by mgccl » IP Logged
rmsgrey
Uberpuzzler

Gender:
Posts: 2818
 Re: Monotone Paths in Graphs   « Reply #10 on: Feb 5th, 2013, 4:34am » Quote Modify

on Feb 4th, 2013, 5:37pm, 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.
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »