Research ArticleOpen AccessGoogle Scholar indexed
On Some Numbers Related to the Erdös-Szekeres Theorem
Department of Mathematics, University of Idaho, Moscow City, Moscow
Department of Mathematics, Washington State University, Pullman, USA
- 1 Department of Mathematics, University of Idaho, Moscow City, Moscow
- 2 Department of Mathematics, Washington State University, Pullman, USA
Open Journal of Discrete Mathematics·Volume 03 (2013)·Pages 167–173·Published 2 July 2013·DOI10.4236/ojdm.2013.33030
Copy link · social · email
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 .
KeywordsErdos-Szekeres TheoremCombinatorial Geometry
- 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.)
- 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.)
- 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
- 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
- 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
- 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.
- 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
- M. J. Nielsen and D. E. Sabo, “Transverse Families of Matchings in the Plane,” ARS Combinatoria, Vol. 55, No. 55, 2000, pp. 193-199.