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.
Similar content being viewed by others
References
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.
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.
P. H. Edelman and M. E. Saks, Combinatorial representation and convex dimension of convex geometries, Order 5 (1988), 23–32.
H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, Berlin, 1987.
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.
G. Tóth, Point sets with many k-sets, Discrete & Computational Geometry, An International Journal of Mathematics and Computer Science 26 (2001), 187–194.
H. Tverberg, On the decomposition of K ninto complete bipartite graphs, Journal of Graph Theory 6 (1982), 493–494.
Author information
Authors and Affiliations
Corresponding author
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
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
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-009-0076-z