# Ramsey-type theorems for lines in 3-space.

We prove geometric Ramsey-type statements on collections of lines in 3-space. These statements give guarantees on the size of a clique or an independent set in (hyper)graphs induced by incidence relations between lines, points, and reguli in 3-space. Among other things, we prove the following:

* The intersection graph of n lines in [[??].sup.3] has a clique or independent set of size [OMEGA]([n.sup.1/3]).

* Every set of n lines in [[??].sup.3] has a subset of [square root of 48] lines that are all stabbed by one line, or a subset of [OMEGA] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that no 6-subset is stabbed by one line.

* Every set of n lines in general position in [[??].sup.3] has a subset of [OMEGA]([n.sup.2/3]) lines that all lie on a regulus, or a subset of [OMEGA]([n.sup.1/3]) lines such that no 4-subset is contained in a regulus.

The proofs of these statements all follow from geometric incidence bounds--such as the Guth-Katz bound on point-line incidences in [[??].sup.3]--combined with Turan-type results on independent sets in sparse graphs and hypergraphs. As an intermediate step towards the third result, we also show that for a fixed family of plane algebraic curves with s degrees of freedom, every set of n points in the plane has a subset of [OMEGA]([n.sup.1-1/s]) points incident to a single curve, or a subset of [OMEGA]([n.sup.1/s]) points such that at most s of them lie on a curve. Although similar Ramsey-type statements can be proved using existing generic algebraic frameworks, the lower bounds we get are much larger than what can be obtained with these methods. The proofs directly yield polynomial-time algorithms for finding subsets of the claimed size.

Keywords: Geometric Ramsey theory, Erdos-Hajnal property, incidence bounds

1 Introduction

Ramsey theory studies the conditions under which particular discrete structures must contain certain substructures. Ramsey's theorem says that for every n, every sufficiently large graph has either a clique or an independent set of size n. Early geometric Ramsey-type statements include the Happy Ending Problem on convex quadrilaterals in planar point sets, and the Erdos-Szekeres Theorem on subsets in convex position [9].

We prove a number of Ramsey-type statements involving lines in [[??].sup.3]. The combinatorics of lines in space is a widely studied topic which arises in many applications such as computer graphics, motion planning, and solid modeling [4]. Our proofs combine two main ingredients: geometric information in the form of bounds on the number of incidences among the objects, and a Turan-type theorem that converts this information into a Ramsey-type statement. We establish a general lemma that allows us to streamline the proofs.

Ramsey's Theorem for graphs and hypergraphs only guarantees the existence of rather small cliques or independent sets. However, as discussed below, for the geometric relations we study the bounds are known to be much larger. Therefore we are interested in finding the correct asymptotics. In particular, we are interested in the Erdos-Hajnal property. A class of graphs has this property if each member with n vertices has either a clique or an independent set of size [n.sup.[delta]] for some constant [delta] > 0. This comes from the Erdos-Hajnal conjecture which states that, for each graph H, the family of graphs excluding H as an induced subgraph has this property. Our results yield new Erdos-Hajnal exponents for each of the classes of (hyper)graphs studied.

The results presented here make use of important recent advances in combinatorial geometry. The key example is the bound on the number of incidences between points and lines in [[??].sup.3] given by Guth and Katz [12] in their recent solution of the Erdos distinct distances problem. Such results have sparked a lot of interest in the field, and it can be expected that further progress will yield further Ramsey-type results.

1.1 A general framework

In general we consider two classes of geometric objects P and Q in [[??].sup.3] and a binary incidence relation contained in P XQ For a finite set P [??] P and a fixed integer t [greater than or equal to] 2, we say that a t-subset [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is degenerate whenever there exists q [member of] Q such that every p [member of] S is incident to q. Hence the incidence relation together with the integer t induces a t-uniform hypergraph H = (P, E), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is the set of all degenerate t-subsets of P. A clique in this hypergraph is a subset S [??] P such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Similarly, an independent set is a subset S [??] P such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

In what follows, the families P and Q will mostly consist of lines or points in 3-space. We are interested in Ramsey-type statements stating that the t-uniform hypergraph H induced by a set P [member of] P of size n has either a clique of size w(n) or an independent set of size [alpha](n).

1.2 Previous results

We first briefly survey some known results that fit into this framework. In many cases, either P or Q is a set of points. When P is a set of points, finding a large independent set amounts to finding a large subset of points in some kind of general position defined with respect to Q. When Q is the set of points, we are dealing with intersections between the objects in P. In particular, the case t = 2 corresponds to the study of geometric intersection graphs.

General position subset problems

A set in [[??].sup.3] is usually said to be in general position whenever no d + 1 points lie on a hyperplane. For points and lines in the plane, Payne and Wood proved that the Erdos-Hajnal property essentially holds with exponent 1/2 [19]. Cardinal et al. proved an analogous result in [[??].sup.3] [3].

Theorem 1.1 ([19, 3]). Fix d [greater than of equal to] 2. Every set of n points in [[??].sup.3] contains [square root of n] cohyperplanar points or [OMEGA]([(n/ log n).sup.1/d]) points in general position.

In both cases, the proofs rely on incidence bounds, in particular the Szemeredi-Trotter Theorem [24] in the plane, and the point-hyperplane incidence bounds due to Elekes and Toth [8] in [[??].sup.3]. In this paper we formalise the technique used in those proofs in order to easily apply it to other incidence relations.

Erdos-Hajnal properties for geometric intersection graphs

A survey of Erdos-Hajnal properties for geometric intersection graphs was producedby Fox and Pach [10]. A general Ramsey-type statement for the case where P is the set of plane convex sets has been known for a long time. In what follows, a vertically convex set is a set whose intersection with any vertical line is a line segment.

Theorem 1.2 (Larman et al. [16]). Any family of n compact, connected and vertically convex sets in the plane contains at least [n.sup.1/5] members that are either pairwise disjoint or pairwise intersecting.

Larman et al. also showed that there exist arrangements of [k.sup.2.3219] line segments with at most k pairwise crossing and at most k pairwise disjoint segments. This lower bound was improved successively by Karolyi et al. [14], and Kyncl [15].

More recently Fox and Pach studied intersection graphs of a large variety of other geometric objects [11]. For example they proved the following about families of s-intersecting curves in the plane--families such that no two curves cross more than s times.

Theorem 1.3 (Fox-Pach [11]). For each [memeber of] > 0 and positive integer s, there is [delta] = [delta]([member of], s) > 0 such that if G is an intersection graph of a s-intersecting family of n curves in the plane, then G has a clique of size at least [n.sup.[delta]] or an independent set of size at least [n.sup.1-[member of]].

Erdos-Hajnal properties for hypergraphs have been proved by Conlon, Fox, and Sudakov [6].

Semi-algebraic sets and relations

A very general version of the problem for the case t = 2 has been studied by Alon et al. [1]. Here Ramsey-type results are provided for intersection relations between semialgebraic sets of constant description complexity in [[??].sup.3]. It was shown that intersection graphs of such objects always have the Erdos-Hajnal property. The proof combines a linearisation technique with a space decomposition theorem due to Yao and Yao [27]. The following general statement can be extracted from their proof.

Theorem 1.4. Consider a relation R on elements of a family F of semi-algebraic sets of constant description complexity. Suppose that each element f [member of] F can be parameterized by a point f * [member of] [[??].sup.3], and that the relation R can be mapped into a semi-algebraic set R* in [[??].sup.2d]. For each g [member of] F, let [[summation].sub.g] = {f * [member of] [[??].sup.3] : (f *, g*) [member of] R*}. Let Q be the smallest dimension of a space [[??].sup.Q] in which the description of [[summation].sub.g] becomes linear, and let k be the number of bilinear inequalities in the deSnition of R* in [[??].sup.Q]. Then the graph of the relation R satisSes the Erdos-Hajnal property with exponent 1 / (2k(Q +1)).

A similar result is given for the so-called strong version of the Erdos-Hajnal property: for every such intersection relation, there exists a constant [member of] and a pair of subfamilies [F.sub.1], [F.sub.2] [??] F, each of size at least [member of]|F|, such that either every element of [F.sub.1] intersects every element of [F.sub.2], or no element of [F.sub.1], intersects any element of [F.sub.2]. The exponent for the usual Erdos-Hajnal statement is a function of this [member of].

As an example, Alon et al. applied their machinery to prove the following result on arrangement of lines in [[??].sup.3].

Theorem 1.5 (Alon et al. [1]). Every family of n pairwise skew lines in [[??].sup.3] contains at least k [greater than or equal to] [n.sub.1/6] elements [l.sub.1], [l.sub.2],..., [l.sub.k] such that [l.sub.i] passes above [l.sub.j] for all i < j.

for the problems we consider, however, the exponents we obtain are significantly larger than what can be obtained from Theorem 1.4.

A general version of this problem in which degenerate t-tuples are defined by a finite number of polynomial equations and inequalities of bounded description complexity has recently been studied by Conlon et al. [5]. They show that the Ramsey numbers in this general setting grow like towers of height t - 1, and that this is asymptotically tight. Such a setting is relevant here, since we also consider Erdos-Hajnal statements for some geometric hypergraphs.

1.3 Summary of our results

In Section 2 we give a simple lemma that allows to convert geometric incidence bounds into bounds on the number of degenerate subsets, hence on the number of hyperedges of the hypergraphs of interest. We also recall the statements of the Turan bound for hypergraphs due to Spencer.

Section 3 deals with the case where P and Q are lines and points in [[??].sup.3]. A natural object to consider is the intersection graph of lines in [[??].sup.3], for which we prove the Erdos-Hajnal property with exponent 1/3.

Theorem 3.7. The intersection graph of n lines in [[??].sup.3] has a clique or independent set of size [OMEGA]([n.sup.1/3]).

This makes use of the Guth-Katz incidence bound between points and lines in [[??].sup.3] [13]. We further show that this exponent can be raised to 1/2 if we consider lines in the projective 3-space. We also show how to obtain bounds on the size of independent sets for t = 3, in which a subset of lines in general position is defined as a set of lines with no three intersecting in the same point.

Section 4 deals with the setting where both P and Q are lines in [[??].sup.3]. We prove the following theorem.

Theorem 4.1. Let L be a set of n lines in [[??].sup.3]. Then either there is a subset of -[square root of n] lines of L that are all stabbed by one line, or there is a subset of [OMEGA] ([(n/ log n).sup.1/5]) lines of L such that no 6-subset is stabbed by one line.

The proof involves lifting the set of lines to a set of points and hyperplanes in [[??].sup.5], and applying the Ramsey-type result on points and hyperplanes due to Cardinal et al. [3]. The latter in turn relies on a point-hyperplane incidence bound due to Elekes and Toth [8].

Finally, in Section 5 we introduce the notion of a subset of lines in general position in [[??].sup.3] with respect to reguli, defined as loci of lines intersecting three pairwise skew lines. We use the Pach-Sharir bound on incidences between points and curves in the plane [18] to obtain the following result.

Theorem 5.5. Let L be a set of n pairwise skew lines in [[??].sup.3]. Then there are [OMEGA][(n.sup.2/3]) lines on a regulus, or [OMEGA][(n.sup.1/3]) lines, no 4-subset of which lie on a regulus.

We also explain how to use a line-regulus incidence bound due to Aronov et al. [2] for an alternative proof of this result.

The large subsets whose existence our results guarantee can be found in polynomial time. In each case, a degenerate t-subset is incident to only one element of Q (for example, three collinear points lie on only one line). Furthermore, the cliques given by our results are of a particular type: all the elements intersect a single element of Q (for example, a collinear set of points). Thus the largest such clique in the hypergraph H can be found in polynomial time by checking all the elements of Q that determine a degenerate t-subset (for example, all lines determined by the point set). If the clique size is small, Turan-type theorems yield an independent set of a guaranteed minimum size. These theorems are constructive, hence the large independent set can be found efficiently.

2 Preliminaries

In order to prove the existence of large independent sets in hypergraphs with no large clique, we proceed in two steps. First, we use incidence bounds to get upper bounds on the density of the (hyper)graph. Then we apply Turan's Theorem or its hypergraph analogue to find a lower bound on the size of the independent set. This is an extension of the method used to prove Theorem 1.1 in [19, 3]. The use of incidence bounds is also reminiscent from the technique used by Pach and Sharir for the repeated angle problem [17].

The following lemma will allow us to quickly convert incidence bounds into density conditions. Recall that we consider two families P and Q with an incidence relation in P X Q, and that a t-subset S of P is said to be degenerate whenever there exists q [member of] Q such that every p [member of] S is incident to q.

Lemma 2.1. Let P be a subset of P with |P| = n, such that no element of Q is incident to more than l elements of P. Let us denote by [P.sub.[greater than or equal to]k] the number of elements of Q incident to at least k elements of P, and suppose [P.sub.[greater than or equal to]k] [??] g(n) / [k.sup.a] for some function g and some real number a. Then the number of degenerate t-subsets induced by P is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Let [P.sub.j] be the number of elements of Q incident to exactly j elements of P. then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where we use that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and t = O(1). The final sum simplifies differently depending on the relative values of t and a.

We recall the statement of Turan's Theorem.

Theorem 2.2 (Turan [25]). Let G be a graph with n vertices and m edges. Then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Thus if m < n/2 then [delta](G) > n/2. Otherwise [delta](G) [greater than or equal to] [n.sup.2]/4m.

The hypergraph version of this result was proved by Spencer.

Theorem 2.3 (Spencer [23]). Let H be a t-uniform hypergraph with n vertices and m edges. If m < n/t then [delta](H) > n/2. Otherwise

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

3 Points and lines in [[??].sup.3]

The recent resolution of Erdos' distinct distance problem by Guth and Katz involves new bounds on the number of incidences between points and lines in [[??].sup.3] [12]. This breakthrough has fostered research on point-line incidence bounds in space. In this section and the next, we exploit those recent results to obtain various new Ramsey-type statements on point-line incidence relations in space.

3.1 General position with respect to lines

Theorem 1.1 for d = 2 states that in a set P of n points in the plane there exist either [square root of n] collinear points, or [OMEGA]([square root of n/ log n]) points with no three collinear. Payne and Wood [19] conjectured that the true size should be [OMEGA]([square root of n]), but this small improvement has proven elusive.

Here we consider the same question but with P = [[??].sup.3], Q defined as the set of lines in [[??].sup.3], and t = 3. Hence we consider that a set P [subset] [[??].sup.3] is in general position when no three points are collinear. So far this is the same question as in the planar case, since a point set in higher dimensional space can always be projected to the plane in a way that maintains the collinearity relation. However, under a small extra assumption, namely that among the n points in [[??].sup.3], at most n/ log n are coplanar, we are able to remove the log n factor in the independent set. This sheds some light on the nature of potential counterexamples to the conjecture of Payne and Wood.

We will use the following result of Dvir and Gopi [7], which is deduced from Guth and Katz [13].

Theorem 3.1. Given a set P of n points in [[??].sup.3], such that at most s points are contained in a plane, the number [P.sub.[greater than or equal to]k] of lines containing at least k points is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 3.2. Any set of n points in [[??].sup.3] such that at most n/ log n ofthe points lie in a plane contains either [square root of n] collinear points or [OMEGA]([square root of n]) with no three collinear

Proof: We apply Lemma 2.1 on each term of the bound in Theorem 3.1. We obtain that the number of degenerate 3-subsets of points is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where l = [square root of n] and s = n/ log n. Hence the dominating term is [n.sup.2]. Applying Theorem 2.3 yields an independent set of size [OMEGA]([square root of n]).

In fact, this theorem holds in [[??].sup.3] for d > 3. To see this, we take a generic projection of [[??].sup.d] onto [[??].sup.3]. The condition that at most n/ log n lines are coplanar remains true under a generic projection.

3.2 Line intersection graphs in [[??].sup.3]

We now consider the setting in which the family P is the set of lines in [[??].sup.3] and Q = [[??].sup.3]. The first subcase we consider is t = 2, or in other words, intersection graphs of lines. Note that in an intersection graph of lines in [[??].sup.3], every clique of size k [greater than or equal to] 2 corresponds either to a subset of k lines having a common intersection point, or to a subset of k lines lying in a plane. However, k lines lying in a plane do not form a clique if some of them are parallel.

We consider a set L of n lines in [[??].sup.3], such that no more than l lines intersect in a point, and at most s lines lie in a common plane or a regulus. We recall that a regulus is a degree two algebraic surface, which is the union of all the lines in [[??].sup.3] that intersect three pairwise-skew lines in [[??].sup.3]. It is a doubly-ruled surface; each point on a regulus is incident to precisely two lines fully contained in the regulus. Moreover, there are two rulings for the regulus; every line from one ruling intersects every line from the other ruling, and does not intersect any line from the same ruling.

We first recall two important theorems of Guth and Katz [13]. In what follows, [P.sub.[greater than or equal to]k] denotes the number of points incident to at least k lines in L.

Theorem 3.3 ([13, Theorem 4.5]). If L is a set of n lines, so that no plane contains more than s lines, then for k [greater than or equal to] 3 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 3.4 ([13, Theorem 2.11],[21]). If L is a set of n lines, so that no plane or regulus contains more than s lines, then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Note the difference between the two statements: the assumption that no regulus contains more than s lines is required for the case k = 2 only.

Applying Lemma 2.1 to the bounds in Theorems 3.3 and 3.4 yields the following.

Proposition 3.5. Given a set L of n lines, so that no plane or regulus contains more than s lines, and no point is incident to more than l lines of L, the number of line-line incidences is [OMEGA]([n.sup.3/2] log l + ns + nl).

Lemma 3.6. Consider a set L of n lines in [[??].sup.3], such that no plane contains more than s lines, and no point is incident to more than l lines of L. Let G be the intersection graph L. If s, l [??] [n.sup.1/2], then [alpha](G)[??] [square root of n]/ logl. Moreover, if r := max[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for some [member of] > 0, then [alpha](G) [??] n/r.

Proof: If there is some regulus containing at least [n.sup.1/2] lines, we divide the lines into the two rulings of the regulus. One ruling contains at least half the lines, and as the lines in one ruling do not intersect one another, it follows that [alpha](G) [??] [n.sup.1/2]. We may therefore assume that the number of lines contained in a common regulus is at most [n.sup.1/2].

If s, l [less than or equal to] [n.sup.1/2], the first term in the bound in Proposition 3.5 dominates, and applying Theorem 2.2 gives [alpha](G) [??] [square root of n]/log l. If r [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], one of the latter terms dominates, and we apply Theorem 2.2 to get [alpha](G) [??] n/r. ?

Theorem 3.7. The intersection graph of n lines in [[??].sup.3] has a clique or independent set of size [OMEGA]([n.sup.1/3]).

Proof: Suppose that such a graph G has [alpha](G) [??] [n.sup.1/3]. Then by Lemma 3.6, max{s, l} [??] [n.sup.2/3]. If l [??] [n.sup.2/3] we are done, so s [??] [n.sup.2/3]. Therefore, we may assume that there is a plane containing [n.sup.2/3] lines. Divide these lines into classes of pairwise parallel lines. If some class contains at least [n.sup.1/3] lines, we have [alpha](G) [??] [n.sup.1/3]. Otherwise, there are at least [n.sup.1/3] different parallel classes. Choosing one line from each class yields a clique of size [n.sup.1/3].

Note that the Erdos-Hajnal property for intersection graphs of lines in [[??].sup.3] can be directly established from Theorem 1.4 by Alon et al. [1], but with a much smaller exponent. In their setting, we can represent the intersection relation between lines using Plucker coordinates in [[??].sup.5], and using two inequalities. This yields k = 2 and Q = 5, and an Erdos-Hajnal exponent of 1/24. Although it is likely that it can be improved by shortcutting steps in the general proof, any exponent we would get would still be far from 1/3.

We now make a connection with intersection graphs of lines in space and line graphs. Recall that the line graph of a graph G has the set of edges E(G) as vertex set, and an edge between two edges of G whenever they are incident to the same vertex of G. Observe that for every graph G, the line graph of G can be represented as the intersection graph of lines in [[??].sup.3] by drawing G on a vertex set in general enough position in [[??].sup.3], and extending the edges of the drawing to lines. By applying Vizing's Theorem, which says that the edge chromatic number of every graph is at most [DELTA] + 1, we may see that the class of line graphs has the Erdos-Hajnal property with exponent 1/2. The question of the exact Erdos-Hajnal exponent for intersection graphs of lines in [[??].sup.3] remains open--it lies somewhere between 1/3 and 1/2.

Finally we note that for sets of lines in projective space, coplanar sets of lines always form a clique. The following stronger result can be directly obtained.

Theorem 3.8. For every intersection graph G of n lines in [P.sup.3], either [omega](G) [greater than or equal to] [square root of n] or [alpha](G) = [OMEGA]([square root of n]/ log n).

Hence intersection graphs of lines in the projective plane satisfy the Erdos-Hajnal property with exponent roughly 1 /2.

3.3 Independent Sets of Lines for t = 3

We now consider the case in which P is the set of lines in [[??].sup.3], Q = [[??].sup.3] and t = 3. This can be seen as a kind of three-dimensional version of the dual of the result of Payne and Wood (Theorem 1. 1 with d =2).

Theorem 3.9. Consider a collection L of n lines in [[??].sup.3], such that at most s lie in a plane, with s [less than or equal to] n/ log n. Then there exists a point incident to [square root of n] lines, or a subset of [OMEGA] ( [square root of n]) lines such that at most two intersect in one point.

Proof: We let l be the largest number of lines intersecting in one point, and suppose l < [square root of n]. Applying Lemma 2.1 and Theorem 3.3, we get that the number of triples sharing a point is at most

m [??] [ln.sup.3/2] + ns log l + [nl.sup.2] [??] [n.sup.2].

Then by Theorem 2.3 we have an independent set of size [OMEGA]([square root of n]).

If the above theorem is stated with dependence on l, we get OMEGA([n.sup.3/4]/[square root of l]). If s is allowed to be as large as n, we are back in the dual of general position subset selection, and we get [OMEGA]([square root of n/ log n]), the same as Theorem 1.1.

4 Stabbing lines in [[??].sup.3]

Three lines in [[??].sup.3] are typically intersected by a fourth line, except in certain degenerate cases. Thus it makes sense to study configurations of lines in [[??].sup.3], and to consider a set of 4 or more lines degenerate if all its elements are intersected by another line. Here we provide a result for 6-tupLes of lines.

We define a 6-tuple of lines to be degenerate if all six lines are intersected (or "stabbed") by a single line in [[??].sup.3]. We call this line a stabbing line for the 6-tuple of lines. So in our framework this is the setting in which both P and Q are the set of lines in [[??].sup.3], and t = 6.

We make use of the Plucker coordinates and coefficients for lines in [[??].sup.3], which are a common tool for dealing with incidences between lines, see e.g. Sharir [20]. Let a = ([a.sub.0] : [a.sub.1] : [a.sub.2] : [a.sub.3]), b = ([b.sub.0] : [b.sub.1] : [b.sub.2] : [b.sub.3]) be two points on a line l, given in projective coordinates. By definition, the Plucker coordinates of l are given by

([[pi].sub.01] : [[pi].sub.02] : [[pi].sub.12] : [[pi].sub.03] : [[pi].sub.13] : [[pi].sub.23]) [member of] [[??].sup.5],

where [[pi].sub.ij] = [a.sub.i][b.sub.j] - [a.sub.j][b.sub.i] for 0 [less than or equal to] i < j [less than or equal to] 3. Similarly, the Plucker coefficients of l are given by

([[pi].sub.23] : - [[pi].sub.13] : [[pi].sub.03] : [[pi].sub.12] : -[[pi].sub.02] : [[pi].sub.01]) [member of] [[??].sup.5],

i.e., these are the Plucker coordinates written in reverse order with two signs flipped. The important property is that two lines l1 and l2 are incident if and only if the Plucker coordinates of l1 lie on the hyperplane defined by the Plucker coefficients of l2 and vice versa. Therefore, we define P and Q to be the points in [P.sup.5] defined by the Plucker coordinates of the lines in L, and the hyperplanes defined by the Plucker coefficients of the lines in [[??].sup.3], respectively. The incidence relation between points in P and hyperplanes in Q is the standard incidence relation between points and hyperplanes. The integer t is set to 6, and a 6-tuple of points in P is degenerate whenever there is a hyperplane in Q which is incident to all six points in the 6-tuple. We prove the following Ramsey-type result for stabbing lines in [[??].sup.3].

Theorem 4.1. Let L be a set of n lines in [[??].sup.3]. Then either there is a subset of [square root of n] lines of L that are all stabbed by one line, or there is a subset of [OMEGA] ([(n/ log n).sup.1/5]) lines of L such that no 6-subset is stabbed by one line.

Theorem 4.1 is an immediate consequence of the following generalisation of Theorem 1.1. The difference is that the set of hyperplanes H is arbitrary instead of being the set of all hyperplanes in [[??].sup.d].

Theorem 4.2. Let H be a set of hyperplanes in [[??].sup.d]. Then, every set of n points in [[??].sup.d] with at most l points on any hyperplane in H, where l = O([n.sup.1/2]), contains a subset of [OMEGA]([n/ log l).sup.1/d]) points so that every hyperplane in H contains at most d of these points.

Theorem 4.2, with d =5, applied to the points and hyperplanes given by the Plucker coordinates and coefficients, implies Theorem 4.1. Theorem 4.2 follows from the following generalized version of Lemma 4.5 of Cardinal et al. [3].

Lemma 4.3. Fix d [greater than or equal to] 2 and a set H ofhyperplanes in [[??].sup.d]. Let P be a set of n points in [[??].sup.d] with no more than l points in a hyperplane in H, for some l = O([n.sup.1/2]). Then, the number of (d + 1)-tuples in P that lie in a hyperplane in H is O([n.sup.d] log l).

The difference between this lemma and the original version in [3] is that the set of hyperplanes H is arbitrary, rather than being the set of all hyperplanes. The proof is similar to that of Cardinal et al., and is given in Appendix A.

The following result provides a simple upper bound.

Theorem 4.4. For every constant integer t [greater than or equal to] 4, there exists an arrangement L of n lines in [[??].sup.3] such that there is no subset of more than O([square root of n]) lines that are all stabbed by one line, nor any subset of more than O([square root of n]) lines with no t stabbed by one line.

Proof: Construct L as follows: pick [square root of n] parallel planes, each containing [square root of n] lines, with no three intersecting and no two parallel. Consider a subset stabbed by one line. Either it has three coplanar lines; then it must be fully contained in one of the planes and contains at most [square root of n] lines; or it has no three coplanar lines, hence contains at most two lines from each plane, and has at most 2[square root of n] lines. Now consider a subset such that no t lines are stabbed by one. Then it contains at most t - 1 lines from each plane, and has at most (t - 1)[square root of n] lines.

5 Lines and reguli in [[??].sup.3]

Consider the case in which P is the class of lines in [[??].sup.3], Q is the class of reguli, and t = 4. Let P be a set of n lines, and assume that the lines in P are pairwise skew. Every triple of lines in P therefore determines a single regulus, and we may consider the set of all reguli determined by P. We consider the containment relation rather than intersection--we are interested in 4-tuples that all lie in the same regulus. In order to prove our result, we first reformulate previously known incidence bounds between points and curves in the plane.

5.1 General position with respect to algebraic curves

We first consider the case where P = [R.sup.2] and Q is a family of algebraic curves of bounded degree. We define the number of degrees of freedom of a family of algebraic curves C to be the minimum value s such that for any s points in [R.sup.2] there are at most c curves passing through all of them, for some constant c. Moreover, C has multiplicity type r if any two curves in C intersect in at most r points. We consider a set of points to be in general position with respect to C when no s + 1 points lie on a curve in C.

It is possible to extract Ramsey-type statements for this situation directly from Theorem 1.1 via linearisation. For example, let us consider the special case of circles, where s = 3. Given a set of points in the plane, we can lift it onto a paraboloid in [R.sup.3] in such a way that a subset of the original set lies on a circle (possibly degenerated into a line) if and only if the corresponding lifted points lie on a hyperplane in [R.sup.3]. By applying Theorem 1.1 on the lifted set, we can show that there exists a subset of [square root of n] points incident to a circle, or a subset of [OMEGA]([(n/ log n).sup.1/3]) points such that at most three of them lie on a circle. We show how we can improve on this.

In order to apply our technique, we need Szemeredi-Trotter-type bounds on the number of incidences between points and curves. This has been studied by Pach and Sharir [18].

Theorem 5.1 ([18]). Let P be a set of n points in the plane and let C be a set of m bounded degree plane algebraic curves with s degrees of freedom and multiplicity type r. Then the number of point-curve incidences is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where C (r, s) is a constant depending only on r and s.

Pach and Sharir proved Theorem 5.1 for simple curves with s degrees of freedom and multiplicity type r. It is well known that one may replace simple curves with bounded degree algebraic curves, since such curves may be cut into a constant number of simple pieces. Note that a set of bounded degree algebraic curves has constant multiplicity type if no two curves share a common component. Wang et al. [26] recently proved another result for incidences between points and algebraic curves, though for our purposes Theorem 5.1 is stronger.

Theorem 5.2. Consider a family C of bounded degree algebraic curves in [R.sup.2] with constant multiplicity type and s degrees of freedom, for some s > 2. Then in any set of n points in [R.sup.2] , there exists a subset of [OMEGA]([n.sup.1-1/s]) points incident to a single curve of C, or a subset of [OMEGA]([n.sup.1/s]) points such that at most s of them lie on a curve of C.

Proof: Set t = s + 1 and count the number of degenerate t-subsets. We denote by [P.sub.[greater than or equal to]k] the number of curves of C containing at least k points of P. A direct corollary of Theorem 5.1 is that, for values of k larger than some constant,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

On the other hand, for smaller values of k, the trivial bound [P.sub.[??]k] [??] [n.sup.s] holds since for any s points, there are at most a constant number of curves passing through all of them. Suppose now that no curve contains more than l [??] [n.sup.1-1/s] points of P. Since s > 2, it follows that t < 2s - 1. Using Lemma 2.1, we deduce that the number of degenerate t-subsets is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus by Theorem 2.3 there exists an independent set of size at least

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As an example, we can instantiate the result as follows for circles in the plane.

Corollary 5.3. Inanysetof n points in [R.sup.2], there exists a subset of [OMEGA]([n.sup.2/3]) points incident to a circle, or a subset of [OMEGA]([n.sup.1/3]) points such that no four of them lie on a circle.

Using the standard point-line duality, Theorem 1.1 states that for every arrangement of n lines in [R.sup.2], either there exists a point contained in [square root of n] lines, or there exists a set of [OMEGA]([(n/logn).sup.1/2]) lines inducing a simple arrangement, that is, such that no point belongs to more than two lines. We provide a similar dual version of Theorem 5.2. This corresponds to the case where P is a family of algebraic curves with s degrees of freedom, Q = [R.sup.2], and t = 3. As mentioned before, the case t = 2, or intersection graphs, has been studied previously [10, 11]. The proof is very similar to that of Theorem 5.2 and omitted.

Theorem 5.4. Consider a family C of bounded degree algebraic curves in [[??].sup.2] with constant multiplicity type and s degrees offreedom, for some s > 2. Then in any arrangement C of m such curves, there exists a subset of [OMEGA]([m.sup.1-1/s]) curves intersecting in one point, or a subset of [OMEGA]([m.sup.1/s]) curves inducing a simple subarrangement, that is, such that at most two intersect in one point.

5.2 Ramsey-type results for lines and reguli in [R.sup.3]

We now come back to our original problem in which P is the class of lines in [[??].sup.3], Q is the class of reguli, and t = 4. Here we restrict the finite arrangement P [subset] P to be pairwise skew, that is, pairwise nonintersecting and nonparallel. We also consider the containment relation, that is, l [member of] P is incident to R [member of] Q if it is fully contained in it.

Recall that a regulus can be defined as a quadratic ruled surface which is the locus of all lines that are incident to three lines in general position. This surface is a doubly ruled surface, that is, every point on a regulus is incident to precisely two lines fully contained in it. There are only two kinds of reguli, both of which are quadrics--hyperbolic paraboloids and hyperboloids of one sheet; see for instance Sharir and Solomon [22] for more details.

Theorem 5.5. Let L be a set of n pairwise skew lines in [R.sup.3]. Then there are [OMEGA]([n.sup.2/3]) lines on a regulus, or [OMEGA]([n.sup.1/3]) lines, no 4-subset of which lie on a regulus.

Proof: We map the lines in L to a set P of points in [R.sup.4]. This can be done for instance by associating with each line the x- and y-coordinates of the two points of intersection with the planes z = 0 and z =1. (We may assume no line is parallel to these planes). Under this mapping, a ruling of a regulus corresponds to an algebraic curve in [R.sup.4]. Let C be the finite set of all curves corresponding to a ruling of a regulus determined by three lines in L. Note that any triple of points in [R.sup.4] is contained in at most one such curve, because three lines in [R.sup.3] lie in at most one ruling of one regulus. (A pair of parallel or intersecting lines are not contained in a ruling of any regulus, even though they are contained in many reguli).

Apply a generic projection [pi] from [R.sup.4] to [R.sup.2], and consider the arrangement of points P' = [pi](P) together with the set of projected curves C' = [pi](C). Such a projection preserves the incidences between points and curves in [R.sup.4], and only creates new intersections between pairs of curves (i.e. 'simple' crossings). Three or more curves in C' intersect in a point if and only if their preimages in C intersect in a point.

The set of curves C' has three degrees of freedom, since for any three points in [[??].sup.2] there are at most two curves passing through all of them. Otherwise, if three curves pass through three points, the corresponding curves in C also intersect in three points in [R.sup.4], a contradiction.

Moreover, the curves in C' are algebraic of bounded degree, do not share common components, and thus have constant multiplicity type. Applying Theorem 5.2 with s = 3, we obtain that there are [OMEGA]([n.sup.2/3]) points of [pi](P) on one curve, or [OMEGA]([n.sup.1/3]) points of [pi](P), no four of which lie on a curve. The result follows.

The bounds can be shown to be tight in the following sense.

Theorem 5.6. There exists a set P of n pairwise skew lines in [[??].sup.3] such that there is no subset of more than O([n.sup.2/3]) lines on a regulus, and no more than O([n.sup.1/3]) lines such that no 4-subset lie on a regulus.

Proof: The set P is constructed as follows: take a set of [n.sup.1/3] distinct reguli, and for each regulus take [n.sup.2/3] lines in one of its rulings, giving n pairwise skew lines. Consider a subset of P contained in a regulus. Either it is one of the chosen reguli, and it contains at most [n.sup.2/3] lines, or it contains at most two lines from each regulus, and has size at most 2[n.sup.1/3]. On the other hand, consider a subset of lines with no four on a regulus. It can contain at most three lines from each chosen regulus, and therefore has size at most 3[n.sup.1/3].

Alternative proof. Aronov et al. [2] proved the following bound on the number of incidences between lines and reguli in 3-space.

Theorem 5.7 (Aronov et al. [2]). Let L be a set of n lines in [[??].sup.3], and let R be a set of m reguli in [[??].sup.3]. Then the number of incidences between the lines of L and the reguli of R is O([n.sup.4/7] [m.sup.17/21]+[n.sup.2/3][m.sup.2/3]+m+n).

From this bound, one may derive an alternative proof of Theorem 5.5, of which we now give a brief sketch. First bound [P.sub.[greater than or equal to]k], defined as the number of reguli containing at least k lines. From the above Theorem, we get [P.sub.[greater than or equal to]k] [??] [n.sup.3]/[k.sup.21/4] + [n.sup.2]/[k.sup.3] + n/k. Then from Lemma 2.1 we know that if no regulus contains more than l lines, then the number of degenerate 4-tuples of lines is m [??] [n.sup.3] + [n.sup.2]l + [nl.sup.3]. Hence either l is larger than [n.sup.2/3], or m [??] [n.sup.3] and from Theorem 2.3 there exists an independent set of lines of size [OMEGA]([n.sup.1/3]).

Acknowledgments

The authors wish to thank the reviewers for their comments, including those on earlier, preliminary versions of this paper.

References

[1] Noga Alon, Janos Pach, Rom Pinchasi, Rados Radoicic, and Micha Sharir. Crossing patterns of semi-algebraic sets. J. Comb. Theory, Ser. A, 111(2):310-326, 2005.

[2] Boris Aronov, Vladlen Koltun, and Micha Sharir. Incidences between points and circles in three and higher dimensions. Discrete & Computational Geometry, 33(2):185-206, 2005.

[3] Jean Cardinal, Csaba D. Toth, and David R. Wood. General Position Subsets and Independent Hyperplanes in d-Space. ArXiv e-prints, 2014, 1410.3637. To appear in Journal of Geometry.

[4] Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas, Micha Sharir, and Jorge Stolfi. Lines in space: Combinatorics and algorithms. Algorithmica, 15(5):428-447, 1996.

[5] David Conlon, Jacob Fox, Janos Pach, Benny Sudakov, and Andrew Suk. Ramsey-type results for semi-algebraic relations. In Proc. Symposium on Computational Geometry (SoCG), pages 309-318, 2013.

[6] David Conlon, Jacob Fox, and Benny Sudakov. Erdos-Hajnal-type theorems in hypergraphs. J. Comb. Theory, Ser. B, 102(5):1142-1154, 2012.

[7] Zeev Dvir and Sivakanth Gopi. On the number of rich lines in truly high dimensional sets. In Proc. 31st International Symposium on Computational Geometry (SoCG), 2015.

[8] Gyorgy Elekes and Csaba D. Toth. Incidences of not-too-degenerate hyperplanes. In Proceedings of the 21st ACM Symposium on Computational Geometry (SoCG), pages 16-21, 2005.

[9] Paul Erdos and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935.

[10] Jacob Fox and Janos Pach. Erdos-Hajnal-type results on intersection patterns of geometric objects. Bolyai Society Mathematical Studies GHorizon of Combinatorics, 17:79-103, 2008.

[11] Jacob Fox and Janos Pach. Coloring [K.sub.k]-free intersection graphs of geometric objects in the plane. Eur. J. Comb., 33(5):853-866, 2012.

[12] Larry Guth and Nets H. Katz. Algebraic methods in discrete analogs of the Kakeya problem. Advances Math., 225:2828-2839, 2010.

[13] Larry Guth and Nets H. Katz. On the Erdos distinct distances problem in the plane. Annals Math., 181:155-190, 2015.

[14] Gyula Karolyi, Janos Pach, and Geza Toth. Ramsey-type results for geometric graphs, I. Discrete & Computational Geometry, 18(3):247-255, 1997.

[15] Jan Kyncl. Ramsey-type constructions for arrangements of segments. Eur. J. Comb., 33(3):336-339, 2012.

[16] David Larman, Jiri Matousek, Janos Pach, and Jeno Torocsik. A Ramsey-type result for convex sets. Bull. London Math. Soc., 26(2):132-136, 1994.

[17] Janos Pach and Micha Sharir. Repeated angles in the plane and related problems. J. Comb. Theory, Ser. A, 59(1):12-22, 1992.

[18] Janos Pach and Micha Sharir. On the number of incidences between points and curves. Combinatorics, Probability & Computing, 7(1):121-127, 1998.

[19] Michael S. Payne and David R. Wood. On the general position subset selection problem. SIAM J. Discrete Math., 27(4):1727-1733, 2013.

[20] Micha Sharir. On joints in arrangements of lines in space and related problems. J. Comb. Theory, Ser. A, 67.1:89-99, 1994.

[21] Micha Sharir and Noam Solomon. Incidences between points and lines in three dimensions. ArXiv e-prints, 2015, 1501.02544.

[22] Micha Sharir and Noam Solomon. Incidences between points and lines on a two-dimensional variety. ArXiv e-prints, 2015, 1502.01670.

[23] Joel Spencer. Turan's theorem for k-graphs. Discrete Mathematics, 2(2):183 - 186, 1972.

[24] Endre Szemeredi and William T. Trotter. Extremal problems in discrete geometry. Combinatorica, 3(3):381-392, 1983.

[25] Paul Turan. On an extremal problem in graph theory. Mat. Fiz. Lapok, 48:436-452, 1941.

[26] Hong Wang, Ben Yang, and Ruixiang Zhang. Bounds of incidences between points and algebraic curves. ArXiv e-prints, 2013, 1308.0861.

[27] Andrew Chi-Chih Yao and F. Frances Yao. A general approach to d-dimensional geometric queries (extended abstract). In Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC), pages 163-168, 1985.

A Proof of Lemma 4.3

For the proof we need the following observation regarding generic projection maps.

Lemma A.1. Let P be a Snite set of points in [[??].sup.d], and let A be a Snite set of (d - 2)-Bats in [[??].sup.d]. Let [pi] be a generic projection from [[??].sup.d] to a hyperplane. Then a point p [member of] P lies on a (d - 2)-Bat A [member of] A if and only if [pi](p) [member of] [pi](A).

Proof: The forward implication is clear. For the other direction, suppose p [??] A. Then the affine span of {p} [union] A is a hyperplane, that is, it is (d - 1)-dimensional. By the genericity of [pi], the image [pi](span({p} [union] A)) must also be (d. - 1) -dimensional, so [pi](p) [??][pi](A).

We also need the following result of Elekes and Toth [8]. Given a point set P, a hyperplane h is said to be [gamma]-degenerate if at most [gamma]|P [[intersection]] h| points of P [intersection] h lie on a (d - 2)-flat.

Theorem A.2. For every d [greater than or equal to] 3 there exist constants [C.sub.d] > 0 and [[gamma].sub.d] > 0 such that for every set of n points in [[??].sup.d], the number [h.sub.[greater than or equal to]k] of [[gamma].sub.d]-degenerate hyperplanes containing at least k points of P is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For convenience we restate Lemma 4.3.

Lemma 4.3. Fix d [greater than or equal to] 2 and a set H of hyperplanes in [[??].sup.d]. Let P be a set of n points in [[??].sup.d] with no more than l points in a hyperplane in H, for some l = O([n.sup.1/2]). Then, the number of (d + 1)-tuples in P that lie in a hyperplane in H is O([n.sup.d] log l).

Proof: The proof is an adaptation of the proof of Lemma 4.5 in Cardinal et al. [3]. It proceeds by induction on d [greater than or equal to] 2. The base case is d =2. We wish to bound the number of triples of points of P, lying on a line in H. Let [h.sub.k] (resp., [h.sub.[greater than or equal to]k]) denote the number of lines of H containing exactly (resp., at least) k points of P. The number of triples of points lying on a line of H is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] follows by the Szemeredi-Trotter Theorem [24].

We now consider the general case d [greater than or equal to] 3. Let P be a set of n points in [[??].sup.d], with no more than l points in a hyperplane in H, where H is a given set of hyperplanes in [[??].sup.d], and l = O([n.sup.1/2]). Let [gamma] := [[gamma].sub.d] > 0 be the constant specified in Theorem A.2. We distinguish between the following three types of (d + 1)-tuples: Type 1: (d + 1)-tuples of P contained in a (d - 2)-flat in a hyperplane in H. Let F be the set of (d - 2)-flats that are contained in some hyperplane in H and spanned by the points P. Let [s.sub.k] denote the number of flats in F that contain exactly k points of P. We project P onto a (d - 1)-flat K via a generic projection [pi] to obtain a set of points P' := [pi](P) in [[??].sup.d-1]. Let H' be the set of hyperplanes [pi]([GAMMA]) for each [GAMMA] [member of] F. By Lemma A.1, |P [intersection] [GAMMA]| = |P' [intersection] [pi]([GAMMA])| for each [GAMMA] [member of] F. Thus [s.sub.k] is also the number of hyperplanes in H' containing k points of P'. Moreover, the hyperplanes in H' contain at most l points of P'.

Applying the induction hypothesis on P' with respect to H' we deduce that the number of d-tuples in P' that lie in a hyperplane in H' is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore, the number of (d + 1)-tuples of P lying on a (d - 2)-flat in F is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Type 2: (d + 1)-tuples of P that span a [gamma]-degenerate hyperplane in H. Let [h.sub.k] denote the number of [gamma]-degenerate hyperplanes in H containing exactly k points of P. Using Theorem A.2, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Type 3: (d + 1)-tuples of P that span a hyperplane in H that is not [gamma]-degenerate. Recall that if a hyperplane H spanned by P is not [gamma]-degenerate, then more than a [gamma] fraction of its points lie in some (d - 2)-flat. Consider a (d - 2)-flat L containing exactly k points of P. A point in P \ L can be on at most one hyperplane containing L. Let [n.sub.r] denote the number of hyperplanes in H containing L and exactly r points of P \ L. Then [[summation].sub.r][n.sub.r]r [less than or equal to] n, and by assumption on the hyperplanes in H, we have r [less than or equal to] l.

We will assign each tuple of Type 3 to a (d - 2)-flat that causes it to be Type 3. Fix a (d - 2)-flat L with k points and consider a hyperplane H [member of] H that is not [gamma]-degenerate because it contains L. That is, suppose H contains r + k points, and k > [gamma](r + k), so r < O(k). All tuples that span H contain at least one point not in L. Hence the number of tuples that span H is O([rk.sup.d]). Assign these tuples to L. The total number of tuples of Type 3 that will be assigned to L in this way is therefore at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let F be the set of (d - 2)-flats that have at least one Type 3 tuple assigned to them. Thus F is a finite set. Let [s.sub.k] denote the number of flats in F that contain exactly k points of P. We project P onto a (d - 1)-flat K via a generic projection [pi] to obtain a set of points P' := [pi](P) in [[??].sup.d-1]. Let H' be the set of hyperplanes [pi]([GAMMA]) for each [GAMMA] [member of] F. By Lemma A.1, |P [intersection] [GAMMA]| = |P' [intersection] [pi]([GAMMA])| for each [GAMMA] [member of] F. Thus [s.sub.k] is also the number of hyperplanes in H' containing k points of P'. Moreover, the hyperplanes in H' contain at most l points of P'. Applying the induction hypothesis on P' with respect to H' we deduce that the number of d-tuples in P' that lie in a hyperplane in H' is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Moreover, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, the number of (d + 1)-tuples of Type 3 is at most

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Summing over all three cases, the proof is complete.

Jean Cardinal (1)

Michael S. Payne (2)

Noam Solomon (3)

(1) Universite libre de Bruxelles (ULB), Belgium

(2) Monash University, Melbourne, Australia

(3) Tel-Aviv University, Israel

received 26th Jan. 2016, revised 20th Aug. 2016, accepted 21st Aug. 2016.