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

Show more

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*.

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.