Georgian Mathematical Journal Volume 9 (2002), Number 2, 303–307

A NOTE ON CONVEXLY INDEPENDENT SUBSETS OF AN INFINITE SET OF POINTS

A. KHARAZISHVILI

Abstract. We consider convexly independent subsets of a given infinite set of points in the plane (Euclidean space) and evaluate the cardinality of such subsets. It is demonstrated, in particular, that situations are essentially different for countable and uncountable point sets.

2000 Mathematics Subject Classification: 52A10, 52A20.

Key words and phrases: Convexly independent points, points in general position, convex curve.

Let E be a vector space (over R) and let X be a subset of E. We recall that X is said to be convexly independent in E if, for each point x ∈ X, the relation x ∉ conv(X \ {x}) is valid, where conv(·) denotes, as usual, the operation of taking convex hulls of subsets of E.

In their famous paper [1] Erdös and Szekeres proved that, for any natural number n ≥ 3, there exists a smallest natural number N(n) possessing the following property: every set of at least N(n) points in general position in the plane contains a subset of n points which are convexly independent, i.e. are the vertices of a convex polygon (n-gon). In addition, Erdös and Szekeres posed the problem to determine the precise value of N(n) and, in connection with this problem, conjectured that N(n) = 2^{n−2} + 1.

The above-mentioned intriguing problem was then investigated by many mathematicians. However, it is still far from being solved. An extensive survey about this problem and closely related questions of combinatorial geometry can be found in [2] where a large list of references is also presented. Here we would like to discuss some infinite version of the Erdös–Szekeres problem. The main attention will be paid to infinite sets of points which are either countable or of cardinality continuum.

Recall that the basic technical tool utilized by Erdös and Szekeres in [1] is the classical combinatorial theorem of Ramsey [3]. By applying this theorem, one easily gets an upper bound for N(n). The same method successfully works for point sets lying in Euclidean spaces of higher dimension (see, e.g., [2]).

We need here only an infinite version of the Ramsey theorem, which is formulated as follows. Let i be a nonzero natural number, A be an arbitrary infinite set, F_{i}(A) denote the family of all i-element subsets of A and let

ISSN 1072-947X / $8.00 / \begin{matrix}c \\ ◯ \end{matrix} Heldermann Verlag www.heldermann.de

{F_{1}, F_{2}, …, F_{k}} be a finite covering of F_{i}(A). Then there exist a natural number r ≤ k and an infinite subset B of A, such that F_{i}(B) ⊂ F_{r}.

It is well known that this infinite version of the Ramsey theorem implies its finite version (e.g., with the aid of the existence of a nontrivial ultrafilter on the set ω of all natural numbers). By applying the above-mentioned infinite version of the Ramsey theorem, the following result can easily be obtained.

Theorem 1. Let m ≥ 2 be a natural number and let A be an infinite subset of the Euclidean space R^{m}, such that card(A ∩ l) < ω for all straight lines l lying in R^{m}. Then there exists an infinite convexly independent set B ⊂ A. In particular, if card(A) = ω, then we have card(B) = card(A).

Proof. The assumptions of the theorem imply that there are affine linear manifolds L in R^{m} satisfying the relation card(A∩L) ≥ ω. Let L′ be such a manifold whose dimension is minimal. Observe that dim(L′) > 1 and every hyperplane H ⊂ L′ has the property that card(H ∩ A) < ω. By using an easy induction, one can define an infinite set A′ ⊂ A ∩ L′ of points in general position in L′. Now, applying to A′ the above-mentioned infinite version of the Ramsey theorem (namely, for i = dim(L′) + 2 and k = 2), we get the required infinite convexly independent set B ⊂ A′ ⊂ A.

Remark 1. It should be noticed that the use of the Ramsey theorem for obtaining the assertion of Theorem 1 is not necessary. Indeed, let us first consider the case of the Euclidean plane R^{2}. Suppose that A is an infinite subset of R^{2} such that card(A ∩ l) < ω for any straight line l lying in R^{2}. Then A contains an infinite countable subset A′ of points in general position. Only three cases are possible:

1) there exist a ray p ⊂ R^{2} and an infinite set {a_{n} : n < ω} ⊂ A′, such that {a_{n} : n < ω} ∩ p = ∅, the sequence of points {a_{n} : n < ω} converges to the end-point o of p and the rays oa_{n} (n < ω) converge to p;

2) there exist a ray p ⊂ R^{2} and an infinite set {a_{n} : n < ω} ⊂ A′, such that

{a_{n} : n < ω} ∩ p = ∅, lim_{n→∞} ||a_{n}|| = +∞, lim_{n→∞} dist(a_{n}, p) = 0;

3) there exist a ray p ⊂ R^{2} and an infinite set {a_{n} : n < ω} ⊂ A′, such that

{a_{n} : n < ω} ∩ p = ∅, lim_{n→∞} ||a_{n}|| = +∞, lim_{n→∞} dist(a_{n}, p) = +∞

and the rays oa_{n} (n < ω) converge to p, where o is the end-point of p.

In each of these cases, it is not difficult to define (by induction) a polygonal convex curve P with infinitely many sides, whose all vertices belong to the set {a_{n} : n < ω} (hence to the set A, as well). In the first case, P can be chosen in such a way that the lengths of its sides will tend to zero. In the second and third cases, P can be chosen so that the lengths of its sides will tend to infinity.

Suppose now that A is an infinite subset of the Euclidean space R^{m}, where m > 2, and suppose that card(A ∩ l) < ω for all straight lines l lying in R^{m}. Again, there exists an infinite countable set A′ ⊂ A of points in general position in some affine linear submanifold of R^{m}. Without loss of generality, we may assume that the above-mentioned manifold coincides with R^{m}. Further, since A′ is countable, we can find a plane L in R^{m} such that the orthogonal projection of R^{m} onto L, restricted to A′, is injective and transforms A′ to a set of points in general position in L. As we already know, the latter set contains an infinite convexly independent subset. Now, one can readily verify that the preimage, with respect to the above-mentioned projection, of this subset will be a required infinite convexly independent subset of A′ (hence of A, as well).

It would be interesting to investigate the question whether it is possible to derive the Erdös–Szekeres result directly from Theorem 1 (without using the finite version of the Ramsey theorem).

Let us discuss the case when uncountable point sets in the plane R^{2} are under consideration and examine an analogue of the Erdös-Szekeres problem for those sets. Let A be an uncountable subset of the plane. Assuming that all the points of A are in general position, a natural question arises: does there exist an uncountable convexly independent subset of A? We shall demonstrate below that, in general, the existence of such a subset of A cannot be guaranteed.

Let α denote the least ordinal number of cardinality continuum. Consider the family of all convex curves in R^{2}. Obviously, we can represent this family in the form of a transfinite sequence {C_{ξ} : ξ < α}. By using the method of transfinite induction, let us construct a family {a_{ξ} : ξ < ω} of points in general position in the plane. Suppose that, for an ordinal ξ < α, the partial family of points {a_{ζ} : ζ < ξ} has already been defined. Take the curves {C_{ζ} : ζ < ξ}. Since every C_{ζ} is convex, the family of all those straight lines whose intersection with C_{ζ} contains more than two elements, is at most countable. Hence there exists a straight line l_{ξ} ⊂ R^{2} such that card(l_{ξ} ∩ C_{ζ}) ≤ 2 for all ordinals ζ < ξ. Clearly, we can find a point a_{ξ} ∈ l_{ξ} not belonging to ∪{C_{ζ} : ζ < ξ} ∪ {a_{ζ} : ζ < ξ}. Moreover, slightly modifying the above argument, we can even choose a point a_{ξ} in such a way that the set of points {a_{ζ} : ζ ≤ ξ} is in general position in the plane.

Proceeding in this manner, we are able to construct the required family of points {a_{ξ} : ξ < α}. Finally, we put

A = {a_{ξ} : ξ < α}.

Then the following statement is true for A.

Theorem 2. The set A possesses these three properties:

1) A is in general position in R^{2};

2) A is of cardinality continuum;

3) no subset of A of cardinality continuum is convexly independent.

Proof. The properties 1) and 2) follow immediately from our construction. Let us check the validity of 3). Suppose to the contrary that some set B ⊂ A of cardinality continuum is convexly independent and put

B′ = cl(conv(B)), C′ = bd(B′).

Then B′ is a closed convex subset of R^{2} with nonempty interior and C′, being the boundary of B′, is a convex curve. Notice that all points of B must belong to C′. This fact can easily be deduced e.g. from the well-known Steinitz theorem [4] which says that a point x belongs to the interior of the convex hull of a set X ⊂ R^{m} if and only if there exists a set Y ⊂ X with card(Y) ≤ 2m, such that x ∈ int(conv(Y)). Consequently, we must have

card(A ∩ C′) ≥ card(B) = card(α) = 2^{ω}.

On the other hand, there exists an ordinal ξ < α such that C_{ξ} = C′. Taking into account the definition of A, we may write

A ∩ C_{ξ} ⊂ {a_{ζ} : ζ ≤ ξ}

and, hence,

card(A ∩ C′) = card(A ∩ C_{ξ}) ≤ card(ξ) + ω < 2^{ω}.

The contradiction obtained finishes the proof.

Remark 2. It should be observed that we were able to construct the set A of Theorem 2 because of a nice structure of convex curves lying in the plane R^{2}. More precisely, all convex curves in the plane turn out to be so thin in R^{2} that any family {C_{i} : i ∈ I} of such curves, with card(I) < 2^{ω}, does not form a covering of R^{2}. Indeed, this moment is crucial for the transfinite construction above. Notice that for more general classes of curves (lying in the plane) the situation can be significantly different. Namely, there are models of set theory in which the existence of a family {S_{i} : i ∈ I} of homeomorphic images of [0, 1], satisfying the relations

card(I) < 2^{ω}, ∪{S_{i} : i ∈ I} = R^{2},

is possible (see, e.g., [5]). In this situation, no construction analogous to that above can be carried out.

Remark 3. Theorem 2 admits a direct generalization to the case of the Euclidean space R^{m} where m ≥ 2. In other words, there exists a set A ⊂ R^{m} of cardinality continuum, whose points are in general position in R^{m}, but no subset of A of the same cardinality is convexly independent. The proof of this result is analogous to the argument presented in the proof of Theorem 2 (however, some insignificant technical details occur in the case of R^{m}).

Remark 4. In various questions of measure theory and set-theoretic topology similar constructions are well known for obtaining those sets which almost avoid the members of a given family of sets (cf., e.g., [6]). In most situations, the given family of sets forms an ideal of subsets of an original space (for example, the ideal of all measure zero sets in a measure space or the ideal of all first category sets in a Baire topological space). As a rule, the corresponding transfinite constructions need some additional set-theoretical axioms (in this connection, see [6] where, assuming the Continuum Hypothesis, the classical constructions of so-called Luzin sets and Sierpiński sets are discussed in detail).

References

1. P. Erdös and G. Szekeres, A combinatorial problem in geometry. Compositio Math. 2(1935), 463–470.

2. W. Morris and V. Soltan, The Erdös–Szekeres problem on points in convex position – a survey. Bull. Amer. Math. Soc. 37(2000), No. 4, 437–458.

3. F. P. Ramsey, On a problem of formal logic.Proc. London Math. Soc. 30(1930), 264–286.

4. E. Steinitz, Bedingt konvergente Reihen und konvexe Systeme. J. Reine Angew. Math. 143(1913), 128–175; 144(1914), 1–40; 146(1916), 1–52.

5. A. B. Kharazishvili,On some topological realizations if infinite graphs. (Russian) Soobshch. Akad. Nauk Gruzii 142(1991), No. 3, 485–488.

6. J. C. Oxtoby, Measure and category. Springer-Verlag, Berlin, 1971.

(Received 13.12.2001)

Author’s address:

Institute of Applied Mathematics I. Javakhishvili Tbilisi State University 2, University St., Tbilisi 380043 Georgia