wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Pigeonholing intervals
        
(Message started by: ecoist on Feb 19^th, 2007, 4:36pm)

Title: Pigeonholing intervals
Post by ecoist on Feb 19^th, 2007, 4:36pm

Show that, given any mn+1 real number intervals of any sort (open, closed, half-open, empty, or nonempty), where m and n are positive integers, some m+1 of them are pairwise disjoint or some n+1 of them have a nonempty intersection.

Title: Re: Pigeonholing intervals
Post by kiochi on Feb 22^nd, 2007, 10:27am

isn't this just a special case of ramsey's theorem?

Title: Re: Pigeonholing intervals
Post by ecoist on Feb 22^nd, 2007, 11:29am

Well, a very special, and well-known, case of Ramsey's Theorem says that, in any group of 6 people, 3 are mutual friends or 3 are mutual strangers. This conclusion is false for a group of 5 people. Taking m=n=2, the posed problem says, given any 5 intervals, either 3 have a nonempty intersection or 3 are pairwise disjoint, which is true.

Title: Re: Pigeonholing intervals
Post by TenaliRaman on Feb 22^nd, 2007, 10:58pm

I have been trying to prove this along the lines of,
http://www.cut-the-knot.org/pigeonhole/seq.shtml

Bleh and i am not getting anywhere.

-- AI

Title: Re: Pigeonholing intervals
Post by Eigenray on Feb 23^rd, 2007, 3:43am

The first thing I thought of is that given mn+1 real numbers, there's either an increasing subsequence of length m+1, or a decreasing subsequence of length n+1. I couldn't get that apply, but then I remembered that it can be proved by [hide]Dilworth's theorem[/hide]:

[hideb]Let P be a poset. Then either P contains an antichain of size m+1, or P is a union of at most m chains.

For intervals I,J, write I < J if I,J are disjoint and I is to the left of J. This is clearly a partial order on our mn+1 intervals. If P contains an antichain of size m+1, then we have m+1 intervals, any two of which intersect. Otherwise, P is a union of at most m chains, and one of these chains must have size at least n+1 by Pigeonhole. This gives n+1 intervals, no two of which intersect.[/hideb]

This can be viewed as providing an improved Ramsey bound R(m+1,n+1) = mn+1 in the case of [hide]comparability[/hide] graphs. (For the lower bound, take m copies of a complete graph on n vertices.)

It remains to show that if any two intervals intersect, then they have a common intersection. If they are all closed, this is clear since

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cap.gif[a_i, b_i] = [ max a_i, min b_i ],

and pairwise intersections show that no a_i > b_j. And if some interval I is not closed, and intersects J₁, ..., J_m, then for each i, we can find a closed interval (a point, even) I_i' http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif I which still intersects J_i, and replace I with convexhull(http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/cup.gifI_i') http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/subset.gif I. And if these new intervals have a common intersection, certainly the old ones do.