TITLE:
On Some Numbers Related to the Erdös-Szekeres Theorem
AUTHORS:
Mark J. Nielsen, William Webb
KEYWORDS:
Erdos-Szekeres Theorem; Combinatorial Geometry
JOURNAL NAME:
Open Journal of Discrete Mathematics,
Vol.3 No.3,
July
12,
2013
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.