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

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 I₁,... , I_k be pairwise disjoint intervals in S with k maximum. If k > n, then we are done. Otherwise, choose I₁,..., 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₁, ..., I_i-1; for i = 1, simply choose I₁ 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 I = I_j or j is the least integer such that I meets I_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, t ≠ j. This contradicts our choice of the I_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 [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

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

Related material Read more...

	Six integers out of 10: Pigeonhole Principle

	Pigeonhole Principle (Same sum)

	Pigeonhole in a Matrix

	Pigeonhole in Calendar

	A nice puzzle modeled on the Petersen graph

	Proizvolov's identity in a game format


	All antichains

	Euclid via Pigeonhole

	Light Bulbs in a Circle (an Interactive Gizmo)

	Seven integers under 127 and their Ratios

72087610