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.

Review text

The authors look at the problem raised by W. Morris of finding in a configuration of \(n\) points in the plane the maximum size \(g(n)\) of an anti-chain of linearly separable sets (a set of points which can be separated from the rest of the points by a line). This question is a generalization of: what is for a given integer \(k\) the maximum number \(f(k)\) of separable \(k\)-sets in a configuration of \(n\) points? This last question is well known open. The authors give the relation \(g(n)=\Omega(n^{2-d/\sqrt{\log n}})\) which proves that the anti-chain in general can be much larger than the special case of \(k\)-sets (known to be \(O(nk^{1/3})\)). They also discuss a related problem on convex pseudo-discs (the family of linearly separable sets form a family of convex pseudo-discs). They show that a family of non comparable convex pseudo-discs cannot contain more than \(4{n\choose 2}+1\) members.

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)