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

DOI10.1007/S11856-009-0076-ZMaRDI QIDQ731372zbMATH OpenOpenAlexFDO

Authors Rom Pinchasi, Günter Rote

Publication date 2 October 2009

Published in Israel Journal of Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.0311

zbMATH Keywords

antichainlinearly separable sets

Mathematics Subject Classification ID

Configuration theorems in linear incidence geometry (51A20) Erd?s problems and related topics of discrete geometry (52C10)

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 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.

Recommendations

• Canonical Antichains on the Circle and Applications
• Extremal configurations and levels in pseudoline arrangements.
• On disjoint concave chains in arrangements of (pseudo) lines
• A Linear Time Approach to the Set Maxima Problem
• Separating convex sets in the plane

Cites work

• Combinatorial representation and convex dimension of convex geometries
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• Improved bounds for planar k-sets and related problems
• Long monotone paths in line arrangements
• On the decomposition ofkn into complete bipartite graphs
• Point sets with many \(k\)-sets

Cited in

(3)

• Separation by convex pseudo-circles
• Separation by convex pseudo-circles (extended abstract)
• A finite family of pseudodiscs must include a ``small pseudodisc

This page was built for publication: On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q731372)