For any n 2 + 1 closed intervals of R , prove that n + 1 of the intervals share a point or n + 1 of the intervals are disjointStuck on a question from 'Introduction to Combinatorics by Martin J. Erickson'.Q: For any n 2 + 1 closed intervals of R , prove that n + 1 of the intervals share a point or n + 1 of the intervals are disjoint.I think we can use the Erdos-Szekeres Theorem: relating the usual series of integers to the closed intervals, and the decreasing/increasing monotonic sequences somehow to the two outcomes, but I am stuck on how to technically do this.Could we measure the 'distance' between the intervals? Creating a decreasing sequence ensuring they'd be close enough to share a point, and an increasing sequence that would ensure they are far enough away to be disjoint?

Question

For any       n    2    +  1 closed intervals of       R  , prove that   n  +  1 of the intervals share a point or   n  +  1 of the intervals are disjointStuck on a question from &#039;Introduction to Combinatorics by Martin J. Erickson&#039;.Q: For any       n    2    +  1 closed intervals of       R  , prove that   n  +  1 of the intervals share a point or   n  +  1 of the intervals are disjoint.I think we can use the Erdos-Szekeres Theorem: relating the usual series of integers to the closed intervals, and the decreasing/increasing monotonic sequences somehow to the two outcomes, but I am stuck on how to technically do this.Could we measure the &#039;distance&#039; between the intervals? Creating a decreasing sequence ensuring they&#039;d be close enough to share a point, and an increasing sequence that would ensure they are far enough away to be disjoint?

Ronan Rollins · Accepted Answer

Step 1Here’s a sketch of a proof; I’ve left two significant points for you to prove.- First prove that if       I   is a finite collection of closed intervals such that no two intervals in       I   are disjoint, then   ⋂      I    ≠  ∅; this can be done by induction on       |        I        |  . Step 2Now let             J        0   be a family of       n    2    +  1 closed intervals, and suppose that no   n  +  1 members of             J        0   share a point. Given a non-empty             J        k   for some   k  ≥  0, let             I        k   be a maximal subfamily of             J        k   such that no two intervals in             I        k   are disjoint, and let             J              k      +      1        =            J        k    ∖            I        k  . Clearly there is a largest m such that             J        m    ≠  ∅, and   {            I        0    ,  …  ,            I        m    } is therefore a partition of       F   into   m  +  1 parts. The result at the top implies that   ⋂            I        k    ≠  ∅ for   k  =  0  ,  …  ,  m, so by hypothesis       |              I        k        |    ≤  n for   k  =  0  ,  …  ,  m, and it follows that   m  ≥  n.Step 3For   k  =  0  ,  …  ,  m let       C    k    =  ⋂            I        k  ;       C    k   is a closed interval (possibly degenerate), and   {      C    0    ,  …  ,      I    m    } is a pairwise disjoint family. For   k  =  0  ,  …  ,  m there is an       i    k    ∈            I        k   such that   max      I    k    =  max      C    k  .- To complete the argument, show that   {      I    0    ,  …  ,      I    m    } is a family of at least   n  +  1 pairwise disjoint members of             J        0

kakvoglq · Accepted Answer

Step 1This solution is using the Erdos-Szekeres theorem.Let f be an unknown but bijective mapping from the collection of the closed sets (call them       C    i    ,     i  =  1  ,  2  ,  ⋯) to natural numbers. We can make f bijective because we know that the collection of closed sets is countable since each closed set can be written as intersection of countable number of closed sets each of which can be identified with some rational number in (0,1).Step 2Now, Let f be defined in a way such that   f  (      C    i    )  ≤  f  (      C    j    ), iff       C    i    ∩      C    j    ≠  ∅, and   f  (      C    i    )  &amp;gt;  f  (      C    j    ), otherwise. Then, we can use Erdos-Szekeres theorem with   r  =  s  =  n  +  1, which then, using the bijectivity of mapping f gives the result.

For any n^2+1 closed intervals of mathbb{R}, prove that n+1 of the intervals share a point or n+1 of the intervals are disjoint

Answered question

Answer & Explanation

New Questions in Integral Calculus