Some geometric applications of Dilworth's theorem (Q1330876)

The authors apply Dilworth's theorem on partially ordered sets to two geometric problems. Answering an old problem of Avital, Hanani, Erdős, Kupitz, and Perles, they show that a graph drawn in the plane with straight line segments, such that the graph has \(n\) vertices, \(m> k^ 4 n\) edges, and no 3 vertices are collinear, must contain \(k+1\) pairwise disjoint edges. The other theorem says that given a set of points \(V\) and a set of axis- parallel rectangles in the plane, then either there are \(k+1\) rectangles such that no point of \(V\) belongs to more than one of them, or there are at most \(2\cdot 10^ 5 k^ 8\) points of \(V\) meeting all rectangles.