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

DOI10.1007/S11856-009-0076-ZzbMATH Open1178.52013arXiv0707.0311OpenAlexW1983962689MaRDI QIDQ731372FDOQ731372

Authors: Rom Pinchasi, Günter Rote 

Publication date: 2 October 2009

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

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.

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

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

zbMATH Keywords

antichainlinearly separable sets

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Long monotone paths in line arrangements
• Improved bounds for planar \(k\)-sets and related problems
• Combinatorial representation and convex dimension of convex geometries
• Title not available (Why is that?)
• On the decomposition ofkn into complete bipartite graphs
• Point sets with many \(k\)-sets

Cited In (3)

• Separation by convex pseudo-circles (extended abstract)
• Separation by convex pseudo-circles
• 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)