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

Mark J. Nielsen, William Webb

Department of Mathematics, University of Idaho, Moscow City, Moscow.
Department of Mathematics, Washington State University, Pullman, USA.

DOI: 10.4236/ojdm.2013.33030                

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.

Keywords

Erdos-Szekeres Theorem; Combinatorial Geometry

Conflicts of Interest

The authors declare no conflicts of interest.

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.