Scientific Research

An Academic Publisher

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

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

Share and Cite:

*Open Journal of Discrete Mathematics*, Vol. 3 No. 3, 2013, pp. 167-173. doi: 10.4236/ojdm.2013.33030.

Conflicts of Interest

The authors declare no conflicts of interest.

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

Copyright © 2020 by authors and Scientific Research Publishing Inc.

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