Given any nm+1 intervals, there exist n+1 pairwise disjoint intervals or m+1 intervals with a nonempty intersection.
By W. McWorter
Let S be the given set of intervals. Let I1,... ,Ik be pairwise disjoint intervals in S
with k maximum. If k>n, then we are done. Otherwise, choose I1,...,Ik such that, for each i, Ii is an interval with least upper endpoint among all intervals in S disjoint from each of
I1,...,Ii-1; for i=1, simply choose I1 with least upper endpoint.
Since k is maximal, every interval in S other than one of the Ii meets an Ij, for some j.
Partition the intervals in S into k sets Sj as follows. I belongs to Sj if and only if j is the
least integer such that I=Ij or j is the least integer such that I meets Ij. If Ij is empty, then Sj contains only Ij.
Since k<=n, pigeonhole implies that |Sj|>m, for some j. We claim that any two elements of Sj
meet. Suppose A and B in Sj are disjoint. Then, without loss, the interval A precedes B, whence
its right endpoint is less than that of B. Also, A is disjoint from all It, t<>j. This contradicts
our choice of the Ii. Hence any two elements of Sj meet.
But then the intersection of all the elements of Sj is nonempty. For, every left endpoint of the
intervals in Sj is less or equal every right endpoint of the intervals in Sj. Hence the least
upper bound U of these left endpoints is less or equal the greatest lower bound L of the right
endpoints; and so the intersection of all of the elements of Sj contains the interval [U,L].
Besides supplying the problem and its proof, Prof. McWorter made the following remark: [This is ...] Not the nicest presentation of the proof. This result was given as a consequence of Dilworth's lemma. According to Claudio Buffara, Dilworth's lemma is equivalent to lots of things including the marriage theorem and Sperner's theorem. Claudio says an excellent presentation of all the equivalences is given in one of Schaum's outlines.
