Rom Pinchasi and Günter Rote:
On the maximum size of an anti-chain of linearly separable sets and
Israel Journal of
Mathematics 172 (2009), 337–348.
We show that the maximum cardinality of an anti-chain composed of
intersections of a given set of n points in the plane with
is close to n2. We approach this problem by
equivalence with the problem of the maximum monotone path in an
of n lines. For a related problem on antichains in families of
pseudo-discs we can establish the precise asymptotic bound: it is
n. The sets in such a family are characterized as intersections
given set of n points with convex sets, such that the
between the convex hulls of any two sets is nonempty and connected.
Last update: September 1, 2009.