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

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

2007-07-02

arxiv.org/abs/0707.0311v2

Israel Journal of Mathematics 172 (2009), 337-348

Mathematics

Metric Geometry

10 pages, 3 figures. revised version correctly attributes the idea of Section 3 to Tverberg; and replaced k-sets by "linearly

Scientific paper

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 quadratic in n. 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.

Affiliated with

Also associated with

No associations

Rating

On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178806