Skip to main content
Springer Nature Link
Log in

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

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

We answer a question raised by Walter Morris, and independently by Alon Efrat, about the maximum cardinality of an anti-chain composed of intersections of a given set of n points in the plane with half-planes. We approach this problem by establishing the equivalence with the problem of the maximum monotone path in an arrangement of n lines. A related problem on convex pseudo-discs is also discussed in the paper.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. Balogh, O. Regev, C. Smyth, W. Steiger, and M. Szegedy, Long monotone paths in line arrangements, Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science 32 (2004), 167–176.

    MathSciNet  MATH  Google Scholar 

  2. T. K. Dey, Improved bounds for planar k-sets and related problems, Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science 19 (1998), 373–382.

    MATH  Google Scholar 

  3. P. H. Edelman and M. E. Saks, Combinatorial representation and convex dimension of convex geometries, Order 5 (1988), 23–32.

    Article  MathSciNet  Google Scholar 

  4. H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987.

    Google Scholar 

  5. R. L. Graham and H. O. Pollak, On embedding graphs in squashed cubes, in Graph theory and applications (Proc. Conf.,Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs), Western Michigan Univ., Lecture Notes in Mathematics, vol. 303, Springer-Verlag, Berlin, 1972, pp. 99–110.

    Google Scholar 

  6. G. Tóth, Point sets with many k-sets, Discrete & Computational Geometry, An International Journal of Mathematics and Computer Science 26 (2001), 187–194.

    MathSciNet  MATH  Google Scholar 

  7. H. Tverberg, On the decomposition of K ninto complete bipartite graphs, Journal of Graph Theory 6 (1982), 493–494.

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Mathematics Dept., Technion-Israel Institute of Technology, Haifa, 32000, Israel

    Rom Pinchasi

  2. Institut für Informatik, Freie Universität Berlin, Takustr. 9, 14195, Berlin, Germany

    Günter Rote

Authors
  1. Rom Pinchasi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Günter Rote
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Rom Pinchasi.

Additional information

This research was supported by a Grant from the G.I.F., the German-Israeli Foundation for Scientific Research and Development.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pinchasi, R., Rote, G. On the maximum size of an anti-chain of linearly separable sets and convex pseudo-discs. Isr. J. Math. 172, 337–348 (2009). https://doi.org/10.1007/s11856-009-0076-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11856-009-0076-z

Keywords

Search

Navigation