## Pigeonhole with Disjoint Intervals

Given any nm + 1 intervals, there exist

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

Copyright © 1996-2018 Alexander Bogomolny
Given any nm + 1 intervals, there exist

#### By W. McWorter

Let S be the given set of intervals. Let I_{1},... , I_{k} be pairwise disjoint intervals in S with k maximum. If _{1},..., I_{k} such that, for each i, I_{i} is an interval with least upper endpoint among all intervals in S disjoint from each of I_{1}, ..., I_{i-1}; for _{1} with least upper endpoint.

Since k is maximal, every interval in S other than one of the I_{i} meets an I_{j}, for some j. Partition the intervals in S into k sets S_{j} as follows. I belongs to S_{j} if and only if j is the least integer such that _{j}_{j}. If I_{j} is empty, then S_{j} contains only I_{j}.

Since k ≤ n, pigeonhole implies that |S_{j}| > m, for some j. We claim that any two elements of S_{j} meet. Suppose A and B in S_{j} 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 I_{t}, _{i}. Hence any two elements of S_{j} meet.

But then the intersection of all the elements of S_{j} is nonempty. For, every left endpoint of the intervals in S_{j} is less or equal every right endpoint of the intervals in S_{j}. 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 S_{j} contains the interval

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

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

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

Copyright © 1996-2018 Alexander Bogomolny