Rom Pinchasi and Günter Rote:

On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs

Israel Journal of Mathematics 172 (2009), 337–348. doi:10.1007/s11856-009-0076-z, arXiv:0707.0311 [math.MG].


We show that the maximum cardinality of an anti-chain composed of intersections of a given set of n points in the plane with half-planes is close to n2. We approach this problem by establishing the equivalence with the problem of the maximum monotone path in an arrangement of n lines. For a related problem on antichains in families of convex pseudo-discs we can establish the precise asymptotic bound: it is quadratic in n. The sets in such a family are characterized as intersections of a given set of n points with convex sets, such that the difference between the convex hulls of any two sets is nonempty and connected.

  PostScript file (gzipped)   pdf file (gzipped)   free PDF view@Springer
other papers about this subject
Last update: September 1, 2009.