## 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].
### Abstract

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 *n*^{2}. 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.
Last update: September 1, 2009.