Pigeonhole with Disjoint Intervals

Given any nm + 1 intervals, there exist n + 1 pairwise disjoint intervals or m + 1 intervals with a nonempty intersection.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

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.

Reference

  1. V. K. Balakrishnan, Theory and Problems of Combinatorics, Schaum's Outline Series, McGraw-Hill, 1995

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]