Back
 OJDM  Vol.3 No.3 , July 2013
On Some Numbers Related to the Erdös-Szekeres Theorem
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.
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.

 
 
Top