Applying Dilworth's theorem to 50 intervals in R

109 Views Asked by At

Problem : Prove that among any 50 intervals R, one can either find 8 disjoint intervals or 8 intervals having a common point.

I think it is quite obvious I need to apply Dilworth's theorem to my problem.

Let's denote the set of intervals by $I = \{I_1, I_2,... , I_n \}$. Define the partial order $\preceq$ on $I$ so that $I_i \preceq I_j$ if and only if one of the following holds:

  1. $I_i = I_j$
  2. $I_i \cap I_j = \varnothing$ and $I_i$ is to the left of $I_j$, i.e.$\forall x \in I_i$ $\forall y \in I_j $ we have $x < y$.

$(I, \preceq)$ is a poset.

By Dilworth’s theorem, we get that $(I, \preceq)$ has either a chain of size $n$ or an antichain of size $\sqrt n$. In the former case, we get $\sqrt n$ pairwise disjoint intervals. In the latter case, we have a set of $\sqrt n$ intervals $I'$ whose pairwise intersection is non-empty.

From there I don't really know what would be the next logical step.