Share This Article:

On Some Numbers Related to the Erdös-Szekeres Theorem

Abstract Full-Text HTML Download Download as PDF (Size:481KB) PP. 167-173
DOI: 10.4236/ojdm.2013.33030    3,400 Downloads   5,624 Views   Citations

ABSTRACT

A crossing family of segments is a collection of segments each pair of which crosses. Given positive integers j and k,a(j,k) grid is the union of two pairwise-disjoint collections of segments (with j and k members, respectively) such that each segment in the first collection crosses all members of the other. Let c(k) be the least integer such that any planar set of c(k) points in general position generates a crossing family of k segments. Also let #(j,k) be the least integer such that any planar set of #(j,k) points in general position generates a (j,k)-grid. We establish here the facts 9≤c(3)≤16 and #(1,2)=8.


Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

M. Nielsen and W. Webb, "On Some Numbers Related to the Erdös-Szekeres Theorem," Open Journal of Discrete Mathematics, Vol. 3 No. 3, 2013, pp. 167-173. doi: 10.4236/ojdm.2013.33030.

References

[1] P. Erdös and G. Szekeres, “A Combinatorial Problem in Geometry,” Compositio Mathematica, Vol. 2, 1935, pp. 463-470. (Reprinted in: J. Spenceer, Ed., Paul Erdös: Selected Writings, MIT Press, Cambridge, 1973, pp. 3-12. Also Reprinted in: I. Gessel and G.-C. Rota, Eds., Classic Papers in Combinatorics, Birkhauser, Basel, 1987, pp. 49-56.)
[2] P. Erdös and G. Szekeres, “On Some Extremum Problems in Elementary Geometry,” Annales Universitatis Scientarium Budapestinensis de Rolando Eötvös Nominatae Sectio Mathematica, Vol. 3-4, No. 1, 1961, pp. 53-62. (Reprinted in: J. Spencer, Ed., Paul Erdös: The Art of Counting. Selected Writings, MIT Press, Cambridge, 1973, pp. 680-689.)
[3] F. R. L. Chung and R. L. Graham, “Forced Convex n-Gons in the Plane,” Discrete & Computational Geometry, Vol. 19, No. 3, 1998, pp. 367-371. doi:10.1007/PL00009353
[4] D. Kleitman and L. Pachter, “Finding Convex Sets among Points in the Plane,” Discrete & Computational Geometry, Vol. 19, No. 3, 1998, pp. 405-410. doi:10.1007/PL00009358
[5] G. Tóth and P. Valtr, “Note on the Erdös-Szekeres Theorem,” Discrete & Computational Geometry, Vol. 19, No. 3, 1998, pp. 457-459. doi:10.1007/PL00009363
[6] W. Morris and V. Soltan, “The Erdös-Szekeres Problem on Points in Convex Position—A Survey,” Bulletin of the American Mathematical Society, Vol. 37, No. 4, 2000, pp. 437-458.
[7] B. Aronov, P. Erdös, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach and L. J. Schulman, “Crossing Families,” Combinatorica, Vol. 14, No. 2, 1994, pp. 127-134. doi:10.1007/BF01215345
[8] M. J. Nielsen and D. E. Sabo, “Transverse Families of Matchings in the Plane,” ARS Combinatoria, Vol. 55, No. 55, 2000, pp. 193-199.

  
comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.