On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs (Q731372): Difference between revisions

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.