Given a set of non-self-intersecting curves C in the plane, we say that C is a collection of pseudosegments if any two members in C have at most one point in common, and no three members in C have a point in common. The intersection graph of a collection C of sets has vertex set C and two sets in C are adjacent if and only if they have a nonempty intersection.
A partition of a set is an equipartition if each pair of parts in the partition differ in size by at most one. Szemerédi's celebrated regularity lemma roughly says that the vertex set of any graph has an equipartition such that the bipartite graph between almost all pairs of parts is random-like.
Our main result is a strengthening of Szemerédi's regularity lemma for intersection graphs of pseudosegments. It replaces the condition that the bipartite graphs between almost all pairs of parts are random-like to being homogeneous, either complete or empty.
Theorem 1.1. For each ε > 0 there is K = K(ε) ≥ 2 such that for every finite collection C of pseudosegments in the plane, there is an equipartition of C into K parts C 1 , . . . , C K such that for all but at most εK 2 pairs C i , C j of parts, either every curve in C i crosses every curve in C j , or every curve in C i is disjoint from every curve in C j .
Pach and Solymosi [37] proved the special case of Theorem 1.1 where C is a collection of segments in the plane, and this result was later extended to semi-algebraic graphs [3] and hypergraphs [16] of bounded description complexity. However, the techniques used to prove these results heavily rely on the algebraic structure. In fact, while it follows from the Milnor-Thom theorem that there are only 2 O(n log n) graphs on n vertices which are semialgebraic of bounded description complexity (see [38,3,43]), there are many more (namely 2 Ω(n 4/3 ) ) graphs on n vertices which are intersection graphs of pseudosegments [18].
Theorem 1.1 does not hold if we do not allow to have exceptional pairs of parts. Indeed, the so-called half-graph (i.e., the graph on the vertex set {u i , v i : 1 ≤ i ≤ n} with u i v j ∈ E(G) if and only if i < j) can be represented as the intersection graph of segments, and it is easy to see that it has no equipartition without exceptional pairs [33].
Next, we discuss an application of Theorem 1.1 in graph drawing.
Disjoint edges in simple topological graphs. A topological graph is a graph drawn in the plane such that its vertices are represented by points and its edges are represented by nonself-intersecting arcs connecting the corresponding points. The edges are allowed to intersect, but they may not intersect vertices apart from their endpoints. Furthermore, no two edges are tangent, i.e., if two edges share an interior point, then they must properly cross at that point in common. A topological graph is simple if every pair of its edges intersect at most once. Two edges of a topological graph cross if their interiors share a point, and are disjoint if they neither share a common vertex nor cross.
A thrackle is a simple topological graph with no two disjoint edges. A famous conjecture due to Conway states that every n-vertex thrackle has at most n edges. In fact, Conway offered a $1000 reward for a proof or disproof of this conjecture. The first linear upper bound was established by Lovász, Pach, and Szegedy in [32], who showed that every n-vertex thrackle has at most 2n edges. This bound was subsequently improved in [6,24,25].
Determining the maximum number of edges in a simple topological graph with no k pairwise disjoint edges seems to be a difficult task. In [40], Pach and Tóth showed that every n-vertex simple topological graph with no k ≥ 3 pairwise disjoint edges has at most O(n log 4k-8 n) edges. They conjectured that for every fixed k, the number of edges in such graphs is at most O k (n). Our next result substantially improves the upper bound for large k.
Theorem 1.2. If G = (V, E) is an n-vertex simple topological graph with no k pairwise disjoint edges, then |E(G)| ≤ n(log n) O(log k) .
In [23], Fox and Sudakov showed that every dense n-vertex simple topological graph contains Ω(log 1+δ n) pairwise disjoint edges, where δ ≈ 1/40. As an immediate Corollary to Theorem 1.2, we improve this bound to nearly polynomial under a much weaker assumption.
Corollary 1.3. Let ε > 0, and let G = (V, E) be an n-vertex simple topological graph with at least 2n 1+ε edges. Then G has n Ω(ε/ log log n) pairwise disjoint edges.
For complete n-vertex simple topological graphs, Aichholzer et al. [2] showed that one can always find Ω(n 1/2 ) pairwise disjoint edges. Whether or not this can be improved to Ω(n) is an open problem.
The proofs of the above theorems heavily rely on a bipartite Ramsey-type result for intersection graphs of pseudosegments (Theorem 2.8), as will be explained in Section 2. At the end of Section 2, using a variant of Szemerédi's regularity lemma originally proposed by Komlós and Sós [29,34,35], we show how this Ramsey-type result implies two "density-type" theorems (Theorems 2.12 and 2.11). Roughly speaking, we prove that if there are many (resp., few) crossings between two families of pseudosegments, then they have two large subfamilies such that every member of the first subfamily crosses every member of the second (resp., no member of the first subfamily crosses any member of the second). In Subsection 2.3, we show with polynomial-type bounds that any finite collection of pseudosegments in the plane contains a linear-sized subset with the property that only a small fraction of pairs in the subset are crossing, or nearly all of them cross. In Section 3, we prove Theorem 2.8 in the special case where one of the families is double grounded (defined in Section 3). Building on these results, in Section 4, we establish our bipartite Ramsey-type theorem (Theorem 2.8) for any two families of pseudosegments with the property that for each family, only a small fraction of pairs are crossing, or nearly all of them cross. Finally, in Section 5, we prove Theorem 2.8 in its full generality. We conclude our paper with a number of remarks and with an application of our results to an old problem in graph drawing (Theorem 1.2).
For the sake of clarity of presentation, we sometimes omit floor and ceiling signs when they are not crucial.
A family of graphs is hereditary if it is closed under taking induced subgraphs. In this section, we show that the property that in a hereditary family of graphs, a homogeneous regularity lemma holds, is equivalent to some seemingly weaker Ramsey-type properties. See Definition 2.1 and Theorem 2.2 below for precise definitions. It will imply that in order to prove Theorem 1.1, it is enough to establish that the family of intersection graphs of pseudosegments satisfies some bipartite Ramsey-type condition (Theorem 2.8).
We say that a graph G is ε-homogeneous if the edge density in G is less than ε or greater than 1ε. We will also need the following definitions. Definition 2.1. Let F be a family of graphs.
1. F has the Erdős-Hajnal property if there is ε = ε(F) > 0 such that every graph in F with n vertices contains a clique or independent set of size n ε . 2. F has the polynomial Rödl property if there is C = C(F) such that for every ε > 0, every n-vertex graph in F has an induced subgraph on at least ε C(F ) n vertices that is ε-homogeneous. 3. F has the strong Erdős-Hajnal property if there is a constant ε = ε(F) > 0 such that the vertex set of every n-vertex graph in F with n ≥ 2 has two disjoint subsets, each of size at least εn, such that the bipartite graph between them is complete or empty. 4. F has the mighty Erdős-Hajnal property if there is a constant ε = ε(F) > 0 such that for every graph G in F and every pair of disjoint subsets A, B ⊂ V (G) with |A| = |B|, there are A ⊂ A and B ⊂ B with |A | ≥ ε|A| and |B | ≥ ε|B| such that the bipartite graph between A and B in G is complete or empty. 5. F has the homogeneous regularity property if for every ε > 0 there is
into K parts such that for all but at most εK 2 pairs of parts (V i , V j ), the bipartite graph between them is complete or empty (i.e., V i ×V j ⊂ E(G) or V i ×V j ∩E(G) = ∅). 6. F has the homogeneous density property if there is C = C(F) such that for every ε > 0 and every graph G ∈ F and every pair A, B ⊂ V (G) of disjoint subsets of the same size with at least ε|A||B| edges between them, there are
For any family of graphs, F, let F be the family consisting of the complements of the elements of F. In the sequel, we will heavily use the following. Before proving Theorem 2.2, we make some remarks on the relative strengths of the properties defined in Definition 2.1.
A classical result of Erdős and Szekeres [11] states that every graph on n vertices has a clique or independent set on 1 2 log 2 n vertices. The first improvement on the constant 1 2 was found recently by Campos, Griffiths, Morris, and Sahasrabudhe [7]. From the other direction, Erdős [9] showed that for every integer n > 2, there is a graph on n vertices that contains no clique or independent set on 2 log 2 n vertices.
It is known that this result can be substantially improved in several restricted settings; see, e.g., [8,15,17]. According to the famous Erdős-Hajnal conjecture [10], which has been established only in some special cases, every hereditary family of graphs that is not the family of all graphs, satisfies the Erdős-Hajnal property.
Rödl [42] proved that for any hereditary family F of graphs that is missing a graph and any ε > 0, there is δ = δ F (ε) > 0 such that any graph in F on n vertices contains an induced subgraph on at least δn vertices which is ε-homogeneous. Rödl's proof used Szemerédi's regularity lemma and consequently gives a weak quantitative bound. Better quantitative bounds were obtained more recently in [22,5].
Fox and Sudakov [22] conjectured that a polynomial dependence holds in Rödl's theorem. That is, every hereditary family of graphs that is not the family of all graphs, satisfies the polynomial Rödl property. It is a simple exercise that any family having the polynomial Rödl property also has the Erdős-Hajnal property. On the other hand, Bucić, Fox, and Pham [4] showed that the converse is also true. Thus, a family of graphs has the polynomial Rödl property if and only if it has the Erdős-Hajnal property.
One way to prove that a family of graphs satisfies the Erdős-Hajnal property is to show that it has the strong Erdős-Hajnal property. However, this technique is limited, as the strong Erdős-Hajnal property is strictly stronger than the Erdős-Hajnal property. For example, it was proved by Tomon [44] that the family of intersection graphs of curves in the plane (the family of "string graphs") has the Erdős-Hajnal property, yet, as was shown by Pach and G. Tóth [41], based on a result of Fox [12], it does not have the strong Erdős-Hajnal property. Interestingly, the family of intersection graphs of curves in the plane, each pair of which have a bounded number of intersections, has the strong Erdős-Hajnal property [21], as does the family of intersection graphs of convex sets in the plane [20].
In Lemma 2.13 below, we prove that every hereditary family of graphs that has the strong Erdős-Hajnal property must also have the polynomial Rödl property. The strong Erdős-Hajnal property is strictly stronger than the polynomial Rödl property, as it is a simple exercise to show that the family of triangle-free graphs has the polynomial Rödl property but does not have the strong Erdős-Hajnal property.
However, for some applications, even the strong Erdős-Hajnal property is not sufficient, and one needs to introduce a stronger property: the mighty Erdős-Hajnal property, which is a bipartite version of the strong Erdős-Hajnal property. The simplest example of a class of graphs that has the strong property, but not the mighty one, is the family of bipartite graphs. A more interesting example is the family of intersection graphs of convex sets in the plane, which as already noted has the strong Erdős-Hajnal property by [20], but does not satisfy the mighty Erdős-Hajnal property as it contains the complement of every bipartite graph. On the other hand, it was proved by Pach and Solymosi [38,37] that intersection graphs of segments have the mighty Erdős-Hajnal property. This was generalized by Alon et al. [3], who proved that families of semialgebraic graphs of bounded description complexity have the mighty Erdős-Hajnal property.
We split the proof of the equivalences in Theorem 2.2 into four smaller lemmas. We start with the following lemma, which is a special case of the main result in [4].
Lemma 2.3. Suppose that a hereditary family F of graphs has the homogeneous regularity property. Then F also has the mighty Erdős-Hajnal property.
Proof. By the homogeneous regularity property of F applied with ε = 1/17, there is a constant K such that every graph in F has an equitable partition into K parts such that the bipartite graph between all but at most εK 2 pairs of parts are complete or empty.
Let G ∈ F and A, B ⊂ V (G) be disjoint with |A| = |B| = n. We may assume n ≥ K as otherwise trivially a singleton subset of A is complete or empty to a singleton subset of B. Let G be the induced subgraph of G with vertex set A ∪ B. Since F is hereditary and G is an induced subgraph of G ∈ F, then G ∈ F. Hence, there is an equipartition of A ∪ B into K parts V 1 , . . . , V K such that all but εK 2 pairs of parts (V i , V j ) are complete or empty. Note that the parts V i that have at most n/(2K) elements in A together have at most K • n/(2K) = n/2 elements from A. Each part V i has at most n/K ≤ 2n/K elements. So there at least (n/2)/(2n/K) = K/4 parts V i that have at least n/(2K) elements from A. Similarly, at least K/4 parts have at least n/(2K) elements from B. So there are K 2 /16 pairs of parts (V i , V j ) such that V i has at least n/(2K) elements from A and V j has at least n/(2K) elements from B. Since we chose ε = 1/17, there are at least K 2 /16 -K 2 /17 > 0 pairs of parts (V i , V j ) that are complete or empty to each other, V i contains at least n/(2K) elements from A and V j contains at least n/(2K) elements of B. Fixing such a pair (V i , V j ) and letting A = V i ∩ A and B = V j ∩ B, we have A and B are complete or empty to each other and are of the desired size. So F has the mighty Erdős-Hajnal property.
Lemma 2.4. Suppose that a hereditary family F of graphs has the mighty Erdős-Hajnal property. Then F also has the homogeneous regularity property.
Proof. Since F has the mighty Erdős-Hajnal property, there is c > 0 such that for every graph G 0 in F and for all disjoint vertex subsets A, B ⊂ V (G 0 ) with |A| = |B|, there is A ⊂ A and B ⊂ B with |A | ≥ c|A| and |B | ≥ c|B| such that the pair (A , B ) is homogeneous.
We will show that F also has the homogeneous regularity property. Let G ∈ F have n vertices. We will show that for ε > 0, G has an equipartition into K = K(ε) parts such that the bipartite graph between all but at most εK 2 pairs of parts are complete or empty. If n ≤ K, then partition V (G) into K sets which have size at most one. Then every pair of parts is complete or empty between them. So we may assume n > K.
Arbitrarily equipartition
ε sets, so at most a fraction ε/4 of the pairs of vertices are in the same part in the partition. Delete one vertex from each part V i that has size n/t +1 so all parts have the same size. Still, as we may assume n > K and K is large enough as a function of ε, all but at most an ε/3 fraction of the pairs of vertices go between these pairs of sets of the same.
Let ε = c 2 ε/100. At each step i of a process we will have a family B i of pairs of disjoint vertex subsets all of the same size satisfying the following four properties:
Each pair of vertices of G go between at most one pair of vertex subsets of B i . 3. All but a fraction (1 -2ε ) 2i of the pairs of vertices that go between a pair of vertex subsets in B 0 go between a pair of vertex subsets in B i . 4. At most a (1c 2 ) i fraction of the pairs of vertices of the graph go between a pair of vertex subsets in B i that are not homogeneous.
Note that the above properties hold for i = 0. Suppose we have already found B i . For each pair (A, B) ∈ B i , by the mighty Erdős-Hajnal property, there are subsets A ⊂ A and B ⊂ B with |A | ≥ c|A| and |B | ≥ c|B| and the bipartite graph between A and B is complete or empty. Partition each of the four sets A , A \ A , B and B \ B into parts of size ε |A| with one possible remaining set. For each pair of these subsets of A and B of size ε |A| such that one is a subset of A and the other is a subset of B, we place the pair of subsets in B i+1 .
We next observe that each of the four properties listed hold. For each pair (A, B) ∈ B i , we get at most (1/ε ) 2 pairs in B i+1 , so |B i+1 | ≤ (1/ε ) 2 |B i |, which inductively gives the first claimed property. The second claimed property holds since every pair of vertices that go between a pair of vertex subsets in B i+1 also go between a pair of vertex subsets in B i . At least a (1-2ε ) 2 -fraction of the pairs of vertices in A×B go between pairs of vertices in B i+1 , which inductively gives the third claimed property. Finally, for each (A, B) ∈ B i , since at least a c 2 -fraction of the pairs of vertices go between the homogeneous pair (A , B ), the last claimed property holds.
After i 0 = c -2 log(4/ε) steps, all but a fraction (1c 2 ) i 0 < e -c 2 i 0 = ε/4 of the pairs of vertices in G go between a pair of vertex subsets in B i 0 that are not homogeneous. The fraction of pairs of vertices in G that do not go between a pair of vertex subsets in
For each pair (A, B) ∈ B i 0 , we obtain two bipartitions
We next obtain an equipartition P of V (G) into K parts. For every equipartition into K parts, we have parts of size n/K or n/K , with the number of parts of size n/K being the remainder when n is divided by K. Partition each part of Q into parts of size n/K or n/K , with additional one part of size at most n/K. We partition the union of the |Q| additional parts into sets of size n/K or n/K so that to obtain an equipartition P of V (G) into K parts. The fraction of pairs of vertices in G not going between a homogeneous pair in partition P is at most ε/2 + ε/4 + 2|Q|/K ≤ ε. Thus, P is the desired equipartition. Lemma 2.6. Suppose that a hereditary family F has the mighty Erdős-Hajnal property. Then F and F both have the homogeneous density property.
The proof of Lemma 2.6 is now a standard application of a weak bipartite version of Szemerédi's regularity lemma. The version we use is due to Komlós and Sós (see [29,35] or Theorem 9.4.1 on page 223 of [34]). Lemma 2.7 ( [29,35]). Let G = (A, B, E) be a bipartite graph with parts A and B such that
Proof of Lemma 2.6. Since F has the mighty Erdős-Hajnal property, there is a constant 0 < c ≤ 1/2 such that for every G ∈ F and disjoint vertex subsets A, B of G of the same size, there are A ⊂ A and B ⊂ B with |A |, |B | ≥ c|A| such that the bipartite graph between A and B is either complete or empty.
By symmetry, it suffices to show that F has the homogeneous density property. Let G ∈ F and A, B be disjoint vertex subsets of equal size such that the edge density between A and B is at least ε. By Lemma 2.7, there are that are complete or empty to each other. However, the above condition that there is at least one edge between A and B implies that A and B are complete to each other, completing the proof.
By Theorem 2.2, the main result in this paper (Theorem 1.1) is equivalent to saying that the family of intersection graphs of pseudosegments has the mighty Erdős-Hajnal property. Therefore, to prove Theorem 1.1, it suffices to prove the following result. A similar statement for double grounded x-monotone curves was proved in [30]. As mentioned earlier, a weaker result, that the family of intersection graphs of pseudosegments has the strong Erdős-Hajnal property, was proved earlier by Fox, Pach, and Tóth [21]. We repeat it below for convenience. Theorem 2.9 ( [21]). Let C be a collection on n pseudosegments in the plane. Then there are subsets
By Theorem 2.2, Theorem 2.8 is equivalent to the following two theorems holding.
Theorem 2.10. There is an absolute constant c > 0 such that the following holds. Let R be a collection of n red curves, and B be a collection of n blue curves in the plane such that R ∪ B is a collection of pseudosegments.
If there are at least εn 2 crossing pairs in R×B, then there are subsets
Theorem 2.11. There is an absolute constant c > 0 such that the following holds. Let R be a collection of n red curves, and B be a collection of n blue curves in the plane such that R ∪ B is a collection of pseudosegments.
If there are at least εn 2 disjoint pairs in R×B, then there are subsets
Theorem 2.11 is the first density-type result for disjointness graphs of pseudosegments, and is the key ingredient in the proof of Theorem 1.2. For the proof of Theorem 2.8, we need the following non-bipartite version of Theorem 2.10 established by the first two authors in [14].
). There is an absolute constant c > 0 such that the following holds. Let C be a collection of n pseudosegments in the plane with at least εn 2 crossing pairs. Then there are subsets C 1 , C 2 ⊂ C, each of size c εn, such that every curve in C 1 crosses every curve in C 2 .
The goal of this subsection is to prove the following lemma, and deduce that the family of intersection graphs of pseudosegments has the polynomial Rödl property.
In proving Lemma 2.13, given a graph G in a hereditary family of graphs satisfying the strong Erdős-Hajnal property, we find a large subgraph of G or its complement that is a balanced complete multipartite graph with many parts. Such a subgraph must have density close to one, giving the desired ε-homogeneous induced subgraph.
Proof of Lemma 2.13. Since F has the strong Erdős-Hajnal property, there is a constant
and V 2 is complete or empty. We repeatedly apply this to the induced subgraph of each of the vertex subsets of G we obtain. After t levels of iteration, we obtain 2 t disjoint vertex subsets, each of size c t n, that are complete or empty between each pair of them, and the induced subgraph H of G formed by taking one vertex from each of these 2 t subsets is a cograph. Since cographs are perfect graphs, and any perfect graph with m vertices contains a clique or independent set of size at least m 1/2 , H contains a clique or independent set with at least 2 t/2 vertices. Let U 1 , . . . , U s be the vertex subsets that the vertices from this clique or independent set belong to. Then the edge density of the induced subgraph on the union
Given a collection C of curves in the plane, let G(C) denote the intersection graph of C. According to Theorem 2.9, the family of intersection graphs of pseudosegments has the strong Erdős-Hajnal property. Applying Lemma 2.13, we obtain Corollary 2.14. The family of intersection graphs of pseudosegments has the polynomial Rödl property. That is, there is an absolute constant c 1 > 0 such that the following holds. Let ε > 0 and C be a collection of n pseudosegments in the plane. Then there is a subset
We will frequently use the following simple lemma in this paper.
Lemma 2.15. Let G = (V, E) be a graph on n vertices. If the edge density of G is at most ε, then any induced subgraph on δn vertices has edge density at most 2ε/δ 2 . Likewise, if the edge density of G is at least 1ε, then any induced subgraph on δn vertices has edge density at least 1 -2ε/δ 2 .
Proof. Suppose the edge density of G is at most εn 2 edges. Hence, any induced subgraph on δn vertices will have at most (2ε/δ 2 )(δn) 2 /2 edges, which implies that the edge density of the induced subgraph is at most 2ε/δ 2 . A symmetric argument follows in the case when the edge density of G is at least 1ε.
Given a collection of curves C in the plane, we say that C is double grounded if there are two distinct curves γ 1 and γ 2 such that for each curve α ∈ C, α has one endpoint on γ 1 and the other on γ 2 , and the interior of α is disjoint from γ 1 and γ 2 . Throughout this paper, for simplicity, we will always assume that both endpoints of each of our curves have distinct x-coordinates. We refer to the endpoint of a curve with the smaller (larger) x-coordinate as its left (right) endpoint. The aim of this section is to prove Theorem 2.8 in the special case where one of the color classes (the red one, say) consists of double grounded curves.
A curve in the plane is called x-monotone if every vertical line intersects it in at most one point. We start by considering double grounded x-monotone curves, and at the end of this section, we will remove the x-monotone condition. We will need the following result, known as the cutting lemma for x-monotone curves. See, for example, Proposition 2.11 in [28].
Lemma 3.1 (The cutting lemma). Let C be a collection of n double grounded x-monotone curves, whose grounds are disjoint vertical segments γ 1 and γ 2 , and let r > 1 be a parameter. Then R 2 \ (γ 1 ∪ γ 2 ) can be subdivided into t connected regions Δ 1 , . . . , Δ t , such that the interior of each Δ i is intersected by at most n/r curves from C, and we have t = O(r 2 ).
In the proof of the following lemma and throughout the paper, we will implicitly use the Jordan curve theorem. Lemma 3.2. Let R be a set of n red double grounded x-monotone curves, whose grounds are disjoint vertical segments γ 1 and γ 2 . Let B be a set of n blue curves (not necessarily x-monotone) such that every blue curve in B is disjoint from grounds γ 1 and γ 2 , and suppose that R ∪ B is a collection of pseudosegments.
Then there are subsets R ⊂ R and B ⊂ B such that |R |, |B | ≥ Ω(n), and either every curve in R crosses every curve in B , or every curve in R is disjoint from every curve in B .
Proof. Let P be the set of left-endpoints of the curves in B. We apply Lemma 3.1 to R with parameter r = 4 to obtain a subdivision
such that for each Δ i , the interior of Δ i intersects at most n/4 members in R, and t ≤ c 0 4 2 where c 0 is an absolute constant from Lemma 3.1. By the pigeonhole principle, there is a region Δ i such that Δ i contains at least n/c 0 4 2 points from P . Let B 0 ⊂ B be the set of blue curves whose left endpoints are in Δ i . Hence
Let Q be the right endpoints of the curves in B 0 . Using the same subdivision described above, there is a region Δ j such that Δ j contains at least |Q|/(c 0 4 2 ) ≥ n/(c 0 4 2 ) 2 points from Q. Let B 1 ⊂ B 0 be the set of blue curves with their left endpoint in Δ i and right endpoint in Δ j . Let R 1 ⊂ R consist of all red curves that do not intersect the interior of Δ i and Δ j . Lemma 3.1 implies that
and
Recall that each blue curve in B 1 does not intersect the grounds γ 1 nor γ 2 . Fix an arbitrary curve α 0 ∈ R 1 . The proof now falls into the following cases.
consists of two connected components, one bounded and the other unbounded.
Case 1.a. Suppose for at least
the collection of such red curves. Then for each α ∈ R 3 , each blue curve β ∈ B 1 crosses α if and only if β crosses α 0 . Hence, there is a subset B 2 ⊂ B 1 of size at least Ω(n), such that either every blue curve in B 2 crosses every red curve in R 3 , or every blue curve in B 2 is disjoint from every red curve in R 3 . Moreover, |R 3 | = Ω(n) and we are done. Fig. 2. Case 2, α 0 and α cross.
Case 1.b. Suppose for at least
. 1(b). Similar to above, let R 3 ⊂ R 2 be the collection of such red curves. By the pseudosegment condition, for each α ∈ R 3 , each blue curve β ∈ B 1 crosses α if and only if β is disjoint from α 0 . Hence, there is a subset B 2 ⊂ B 1 of size Ω r (n), such that either every blue curve in B 2 crosses every red curve in R 3 , or every blue curve in B 2 is disjoint from every red curve in R 3 . Moreover, |R 3 | = Ω(n) and we are done. Case 2. Suppose at least |R 1 Case 2.a. Suppose for at least
the collection of such red curves. By the pseudosegment condition, for each α ∈ R 3 , each blue curve β ∈ B 1 crosses α if and only if β crosses α 0 . Hence, there is a subset B 2 ⊂ B 1 of size at least Ω(n), such that either every blue curve in B 2 crosses every red curve in R 3 , or every blue curve in B 2 is disjoint from every red curve in R 3 . Moreover,
one of which is bounded and the other unbounded. See Fig. 2(b). Let R 3 ⊂ R 2 be the collection of such red curves. By the pseudosegment condition, for each α ∈ R 3 , each blue curve β ∈ B 1 crosses α if and only if β is disjoint from α 0 . Hence, there is a subset B 2 ⊂ B 1 of size Ω(n), such that either every blue curve in B 2 crosses every red curve in R 3 , or every blue curve in B 2 is disjoint from every red curve in R 3 . Moreover, |R 3 | = Ω(n), and we are done.
Recall that a pseudoline is an unbounded arc in R 2 , whose complement is disconnected. An arrangement of pseudolines is a set of pseudolines such that every pair meets exactly once, and no three members have a point in common. A classic result of Goodman [26] states that every arrangement of pseudolines is isomorphic to an arrangement of wiring diagram (bi-infinite x-monotone curves). Moreover, Goodman and Pollack showed the following.
We also need the following simple lemma. Lemma 3.4. Given a finite linearly ordered set whose elements are colored red or blue, we can select half of the red elements and half of the blue elements such that all of the selected elements of one color come before all of the selected elements of the other color.
We are now ready to establish the main result of this section: Theorem 3.5. Let R be a set of n red double grounded curves with grounds γ 1 and γ 2 , where γ 1 and γ 2 cross each other. Let B be a set of n blue curves such that R∪B∪{γ 1 , γ 2 } is a collection of pseudosegments.
Then there are subsets R ⊂ R and B ⊂ B such that |R |, |B | ≥ Ω(n), and either every curve in R crosses every curve in B , or every curve in R is disjoint from every curve in B .
Proof. By passing to linear-sized subsets of R and B and subcurves of γ 1 and γ 2 , we will reduce the problem to the setting of Lemma 3.2. Let us assume that γ 1 and γ 2 cross at point p. Hence, (γ 1 \ γ 2 ) ∪ (γ 2 \ γ 1 ) consists of four connected components. By the pigeonhole principle, there is a subset R 1 ⊂ R of size n/4 such that every curve in R 1 has an endpoint on one of the connected components of γ 1 \ γ 2 , and all of the other endpoints lie on one of the connected components of γ 2 \ γ 1 . Let γ i ⊂ γ i , for i = 1, 2, be these connected components so that they have a common endpoint at p and their interiors are disjoint.
For each α ∈ R 1 , the sequence of curves (γ 1 , γ 2 , α) appear either in clockwise or counterclockwise order along the unique simple closed curve that lies in γ 1 ∪ γ 2 ∪ α.
Without loss of generality, we can assume that there is a subset R 2 ⊂ R 1 , where |R 2 | = Ω(n), such that for every curve α ∈ R 2 , the sequence (γ 1 , γ 2 , α) appears in clockwise order, since a symmetric argument would follow otherwise.
We define the orientation of each curve α ∈ R 2 as the sequence of turns, either leftleft, left-right, right-left, or right-right, made by starting at p and moving along γ 1 in the arrangement γ 1 ∪ γ 2 ∪ α, until we return back to p. More precisely, starting at p we move along γ 1 until we reach the endpoint of α. We then turn either left or right to move along α towards γ 2 . Once we've reached γ 2 , we either turn left or right in order to move along γ 2 and reach p again. By the pigeonhole principle, there is a subset R 3 ⊂ R 2 of size at least Ω(n) such that all curves in R 3 have the same orientation. Without loss of generality, we can assume that the orientation is left-left, since a symmetric argument would follow otherwise.
Starting at p and moving along γ 1 towards its other endpoint, let us consider the sequence of curves from R 3 ∪ B intersecting γ 1 . Then, by Lemma 3.4, there are subsets
such that either all of the curves in R 4 appear before all of the curves in B 1 that intersect γ 1 in this sequence, or all of the curves in R 4 appear after all of the curves in B 1 in this sequence. Note that B 1 consists of the blue curves in B that are disjoint from γ 1 and at least half of the curves in B that intersect γ 1 found by the application of Lemma 3.4. Hence, there is a subcurve γ 1 ⊂ γ 1 such that γ 1 is one of the grounds for R 4 , and is disjoint from every curve in B 1 . We apply the same argument to R 4 ∪ B 1 and γ 2 , and obtain subsets R 5 ⊂ R 4 , B 2 ⊂ B 1 , and a subcurve γ 2 ⊂ γ 2 , such that |R 5 |, |B 2 | = Ω(n), and R 5 is double grounded with disjoint grounds γ 1 and γ 2 , and every curve in B 2 is disjoint from γ 1 and γ 2 .
For i ∈ {1, 2}, let p i be the endpoint of γ i that lies closest to p along γ i . Starting at p i and moving along γ i , let π i be the sequence of curves in R 5 that appear on γ i . Since every curve in R 5 has the same left-left orientation, and appears clockwise order with respect to γ 1 and γ 2 , two curves α, α ∈ R 5 cross if and only if the order in which they appear in π 1 and π 2 changes. Let γ 3 be a curve very close to γ 2 such that γ 3 has the same endpoints as γ 2 , and is disjoint from all curves in R 5 ∪ B 2 . Hence, γ 2 ∪ γ 3 makes an empty lens in the arrangement R 5 ∪ B 2 . We slightly extend each curve α ∈ R 5 through this lens to γ 3 so that the resulting curve, α properly crosses γ 2 and has its new endpoint on γ 3 . Moreover, the extension will be made in such a way that the sequence π 3 of curves in R 5 appearing along γ 3 starting from p 2 will appear in the opposite order of π 1 . Let
Thus, every pair of curves in R 5 will cross exactly once.
For each curve α ∈ R 5 , we further extend α by moving both endpoints towards p along γ 1 and γ 2 , so that we do not create any additional crossings within R 5 . Let α be the resulting extension, where both endpoints of α lie arbitrarily close to p. Set R5 = {α : α ∈ R 5 }. See Fig. 3. Furthermore, we can assume that p lies in the unbounded face of the arrangement R5 , since otherwise we could project the arrangement R5 onto a sphere, and then project it back to the plane so that p lies in the unbounded face, without creating or removing any crossing. Therefore, R5 can be extended to a family of pseudolines. By Theorem 3.3, we can apply a continuous deformation of the plane so that R5 becomes a collection of unbounded x-monotone curves. Hence, after the deformation, the original set R 5 becomes a collection of double grounded x-monotone curves, with grounds γ 1 , γ 2 , such that every curve in B 2 is disjoint from the grounds γ 1 and γ 2 , the crossing pattern in the arrangement R 5 ∪ B 2 is the same as before. Moreover, γ 1 and γ 2 will be disjoint vertical segments. We apply Lemma 3.2 to R 5 and B 2 and obtain subsets R 6 ⊂ R 5 and B 3 ⊂ B 2 , each of size Ω(n), such that either every curve in R 6 crosses every curve in B 3 , or every curve in R 6 is disjoint from every curve in B 3 . This completes the proof.
By combining Theorem 3.5 with Lemma 2.7, as shown in Section 2, we obtain the following density theorems. Theorem 3.6. There is an absolute constant c > 0 such that the following holds. Let R be a collection of n red double grounded curves with grounds γ 1 and γ 2 , such that γ 1 and γ 2 cross. Let B be a collection of n blue curves such that R ∪ B ∪ {γ 1 , γ 2 } is a collection of pseudosegments.
If there are at least εn 2 crossing pairs in R×B, then there are subsets R ⊂ R, B ⊂ B, where |R |, |B | ≥ ε c n, such that every curve in R crosses every curve in B .
There is an absolute constant c > 0 such that the following holds. Let R be a collection of n red double grounded curves with grounds γ 1 and γ 2 , such that γ 1 and γ 2 cross. Let B be a collection of n blue curves such that R ∪ B is a collection of pseudosegments.
If there are at least εn 2 disjoint pairs in R×B, then there are subsets R ⊂ R, B ⊂ B, where |R |, |B | ≥ ε c n, such that every curve in R is disjoint from every curve in B .
We will apply Theorems 3.5 and 3.6 in the next section.
The aim of this section is to prove Theorem 2.8, the main result of this paper, in the special case where the edge density of the intersection graph of the red curves is nearly 0 or nearly 1, and the same is true for the intersection graph of the blue curves. This will easily imply Theorem 2.8 in its full generality, as shown in the next section.
By Corollary 2.14, it is sufficient to establish Theorem 2.8 in the special case where the intersection graphs G(R) and G(B) are both ε-homogeneous, where ε > 0 is a small absolute constant. Below, we first consider the cases when the edge densities of both G(R) and G(B) are smaller than ε. Recall that a separator for a graph
|V |, and no vertex in V 1 is adjacent to any vertex in V 2 . The celebrated Lipton-Tarjan separator theorem states that every planar graph with n vertices has a separator of size O( √ n). We will need the following result due to the first two authors. For a strengthening, see [31].
We now prove the following.
There is an absolute constant ε 0 > 0 such that the following holds. Let R be a set of n red curves in the plane and let B be a set of n blue curves such that R ∪ B is a collection of pseudosegments.
If the edge densities of the intersection graphs G(R) and G(B) are both less than ε 0 , and there are at most ε 0 n 2 crossing pairs in R × B, then there are subsets R ⊂ R and B ⊂ B, each of size Ω(n), such that every red curve in R is disjoint from every blue curve in B .
Proof. Let ε 0 be a small constant that will be determined later. Set C = R∪B. We apply Lemma 4.1 to C and obtain a partition
and every curve in C 1 is disjoint from every curve in C 2 . Let c be the constant from Lemma 4.1. By setting ε 0 < 1 (2c) 2 16 , we have
4. Without loss of generality, we can assume that at least half of the curves in C 1 are red, since a symmetric argument would follow otherwise. Since |C 1 | ≥ (2n)/3 -|C 0 |, there are at least 2n/3n/4 2 = 5n/24 red curves in C 1 . Moreover, there are at most 2n/3 blue curves in C 1 , which implies that there are at least n -2n 3 -n 4 ≥ n 12 , blue curves in C 2 . By setting R to be the red curves in C 1 and B to be the blue curves in C 2 , we obtain the desired subsets. Theorem 4.3. There is an absolute constant ε 1 > 0 such that the following holds. Let R be a set of n red curves and B be a set of n blue curves in the plane such that R ∪ B is a collection of pseudosegments. If the edge densities of the intersection graphs G(R) and G(B) are both less than ε 1 , then there are subsets R ⊂ R and B ⊂ B, each of size Ω(n), such that every red curve in R crosses every blue curve in B , every red curve in R is disjoint from every blue curve in B .
Proof. Let ε 1 be a small constant that will be determined later. Suppose there are at most ε 0 n 2 crossing pairs in R × B, where ε 0 is defined in Lemma 4.2. Since the edge density of the intersection graphs G(R) and G(B) are both less than ε 1 , by setting ε 1 < ε 0 , Lemma 4.2 implies that there are subsets R ⊂ R and B ⊂ B, each of size Ω(n), such that every red curve in R is disjoint from every blue curve in B and we are done.
If there are at least ε 0 n 2 crossing pairs in R × B, then, by Theorem 2.12, there are subsets C 1 , C 2 ⊂ R ∪ B, each of size c ε 0 n, where c > 0 is an absolute constant from Theorem 2.12, such that each curve in C 1 crosses each curve in C 2 . Without loss of generality, we can assume that at least c ε 0 n/2 curves in C 1 are red and we call the set of these curves R . Since G(R) has edge density at most ε 1 , by setting ε 1 < (c ε 0 ) 2 /4, at most c ε 0 n/2 curves in C 2 are red. Hence, at least c ε 0 n/2 curves in C 2 are blue. Denoting the set of these curves B , we are done.
In this subsection, we consider the case when the intersection graph G(R) has edge density at least 1ε, and G(B) has edge density less than ε. Since the edge density in the intersection graph G(R) is at least 1ε, we can further reduce to the case when there is a red curve γ 1 that crosses every member in R exactly once.
Let us give a brief description of the argument, as this is the most difficult case. Since each curve in R crosses γ 1 exactly once, each red curve will have an upper part and a lower part. See Fig. 4. The proof starts by showing that we can obtain large subsets of the red and blue curves, say R and B , such that either the lower parts of all of the red curves in R cross all blue curves in B , or the lower parts of all of the red curves in R are disjoint from all of the blue curves in B . In the first case, we are done. Hence, we can assume that we are in the latter. As the lower part of every remaining red curve is disjoint from all of the remaining blue curves, we can now focus on the upper part of each red curve.
We then find another red curve γ 2 that crosses the upper part of many red curves, giving us a new partition on each remaining red curve. Hence, each remaining red curve now has a (new) lower part and a (new) upper part. By applying some of the same arguments as before, we will either conclude that many red curves cross many blue curves (in which case we are done), or we will obtain two large subsets of red curves, say R 1 and R 2 , and a large subset of blue curves, B , such that all of the blue curves in B are disjoint from the (new) lower parts of all of the red curves in R 1 ∪ R 2 . Moreover, the (new) upper part of each red curve in R 1 will be disjoint from the (new) upper part of every red curve in R 2 . See Fig. 5. Hence, the edge density of the intersection graph of the (new) upper parts of the red curves in R 1 ∪ R 2 is at most 1/2.
After several iterations of the above argument, we will either find many red curves that cross many blue curves (in which case we are done), or we will find large subsets of red curves, R 1 , . . . , R 2 t , and a large subset of blue curves, B , such that every blue curve in B is disjoint from the (new) lower part of every red curve in
and the edge density of the (new) upper part of the red curves in R 1 ∪ • • • ∪ R 2 t is at most 1/2 t . As we proceed with the (new) upper parts of red curves in R 1 ∪ • • • ∪ R 2 t , and with the blue curves B , if t is a sufficiently large constant, we will fall into the low versus low density case. Hence, by applying Theorem 4.3, we conclude the proof. The details of this argument are given in the following lemma. Lemma 4.4. For each integer t ≥ 1, there is a constant ε t > 0 such that the following holds. Let R be a set of n red curves in the plane, all crossed by a curve γ 1 exactly once, and B be a set of n blue curves in the plane such that R ∪ B ∪ {γ 1 } is a collection of pseudosegments. Suppose that the intersection graph G(B) has edge density less than ε t , and G(R) has edge density at least 1ε t .
Then there are subsets R ⊂ R, B ⊂ B, each of size Ω ε t (n), such that either every red curve in R crosses every blue curve in B, or every red curve in R is disjoint from every blue curve in B, or each curve α ∈ R has a partition into two connected parts α = αu ∪ αℓ , such that for
every curve in L is disjoint from every curve in B, and the edge density of G( Û) is less that 2 -t .
Proof. Each curve α ∈ R is partitioned into two connected parts by γ 1 , say an upper and lower part. More precisely, we have the partition α = α u ∪ α ℓ , where the parts α u and α ℓ are defined, as follows. We start at the left endpoint of γ 1 and move along γ 1 until we reach α ∩ γ 1 . At this point, we turn left along α to obtain α u and right to obtain α ℓ . See Fig. 4. Let U (L) be the upper (lower) part of each curve in R, that is,
In what follows, for every integer t ≥ 1, we will obtain subsets R (t) ⊂ R, B (t) ⊂ B, each of size Ω ε t (n), such that either every red curve in R (t) crosses every blue curve in B (t) , or every red curve in R (t) is disjoint from every blue curve in B (t) , or each curve α ∈ R (t) has a new partition into two connected parts α = α u ∪ α ℓ , upper and lower, such that the following holds.
1. We have α u ⊂ α u , that is, the upper part α u is a subcurve of the previous upper part α u . 2. The lower part α ℓ of each curve in R (t) is disjoint from each blue curve in B (t) . 3. There is an equipartition
Hence, the lemma follows from the statement above by setting B = B (t) , R = R (t) .
We proceed by induction on t. The bulk of the argument below is actually for the base case t = 1, since we will just repeat the entire argument for the inductive step with parameter ε t . Let ε 1 be a small positive constant that will be determined later such that ε 1 < ε 1 , where ε 1 is from Theorem 4.3. Thus, G(R) has edge density at least 1ε 1 and G(B) has edge density less than ε 1 .
Let δ > 0 also be a sufficiently small constant determined later, such that ε 1 < δ < ε 1 . We apply Corollary 2.14 to L with parameter δ and obtain a subset L 1 ⊂ L such that L 1 is δ-homogeneous and |L 1 | = Ω δ (n). Let R 1 ⊂ R be the red curves in R corresponding to the curves in L 1 , and let U 1 ⊂ U be the curves in U that correspond to the red curves in R 1 . (Here and in what follows, we say that a curve corresponds to another curve if one of them is a subcurve of the other.) Without loss of generality, we can assume that the intersection graph G(L 1 ) has edge density less than δ. Indeed, otherwise if G(L 1 ) has edge density greater than 1δ, by the pseudosegment condition, the intersection graph G(U 1 ) must have edge density less than δ and a symmetric argument would follow. In order to apply Theorem 4.3, we need two subsets of equal size. By averaging, there is a subset B ⊂ B with |B | = |L 1 | such that the edge density of G(B ) is at most that of G(B). Since G(L 1 ) has edge density less than δ and G(B ) has edge density less than ε 1 , by setting ε 1 < δ < ε 1 , we can apply Theorem 4.3 to L 1 and B and obtain subsets L 2 ⊂ L 1 and B 1 ⊂ B , each of size Ω δ (n), such that every curve in L 2 crosses every blue curve in B 1 , or every curve in L 2 is disjoint from every blue curve in B 1 . If we are in the former case, then we are done. Hence, we can assume that we are in the latter case. Let R 2 ⊂ R 1 be the red curves that correspond to L 2 , and let U 2 ⊂ U 1 be the curves in U 1 that correspond to R 2 . We apply Corollary 2.14 to U 2 with parameter δ and obtain a subset U 3 ⊂ U 2 such that U 3 is δ-homogeneous and |U 3 | = Ω δ (n). Let R 3 be the red curves in R corresponding to U 3 , and let L 3 be the curves in L 2 that correspond to R 3 .
Suppose that the intersection graph G(U 3 ) has edge density less than δ. Since |B 1 | = δ 0 n, where δ 0 = δ 0 (δ, ε 1 ), by Lemma 2.15, the intersection graph G(B 1 ) has edge density at most 2ε 1 /δ 2 0 . Thus, we set δ and ε 1 sufficiently small so that δ < ε 1 and 2ε 1 /δ 2 0 < ε 1 . By averaging, we can find subsets of U 3 and B 1 , each of size min(|U 3 |, |B 1 |) and with densities less than ε 1 , and apply Theorem 4.3 to these subsets and obtain subsets U 4 ⊂ U 3 and B 2 ⊂ B 1 , each of size Ω δ (n), such that every curve in U 4 crosses every blue curve in B 2 , or every curve in U 4 is disjoint from every blue curve in B 2 . In both cases, we are done since every curve in L 3 is disjoint from every curve in B 2 . Therefore, we can assume that G(U 3 ) has edge density greater than 1δ.
For each curve α ∈ U 3 , let N (α) denote the set of curves in U 3 that intersects α, and let d(α) = |N (α)|. We label the curves β ∈ N (α) with integers 0 to d(α) -1 according to their closest intersection point to the ground γ 1 along α, that is, the label f α (β) of β ∈ N (α) is the number of curves in U 3 that intersects the portion of α strictly between γ 1 and α ∩ β. Since
by Jensen's inequality, we have
Let the weight w(β) of a curve β ∈ U 3 be the sum of its labels, that is,
f α (β). Hence, the weight w(β) is the total number of crossing points along curves α strictly between γ 1 and β, where α crosses both γ 1 and β. By averaging, there is a curve γ 2 ∈ U 3 whose weight is at least
Using γ 2 , we partition each curve α ∈ U 3 \ {γ 2 } that crosses γ 2 into two connected parts, α = α w ∪ α m , where α m is the connected subcurve with endpoints on γ 1 and γ 2 , and α w is the other connected part. Set
Since γ 2 has weight at least |U 3 | 2 /4, by the pigeonhole principle, there are at least
Case 1. Suppose there are at least |U 3 | 2 /8 pairs in M 3 × W 3 that cross. The set M 3 is double grounded with grounds γ 1 and γ 2 that cross exactly once, and every curve in W 3 is disjoint from γ 1 and γ 2 . As |M 3 |, |W 3 | ≤ |U 3 |, the density of edges in the bipartite intersection graph of M 3 and W 3 is at least 1/8. By averaging, we can find subsets of M 3 and W 3 each of size min(|M 3 |, |W 3 |) such that the density of edges in the bipartite intersection graph of these subsets is at least 1/8. By setting δ > 0 sufficiently small, we can apply Theorem 3.6 to these subsets of M 3 and W 3 and obtain subsets M 4 ⊂ M 3 and W 4 ⊂ W 3 , each of size Ω δ (n), such that each curve in M 4 crosses each curve in W 4 . Moreover, by the pseudosegment condition, each curve in M 4 ∪ W 4 corresponds to a unique curve in U 3 . Let U 4 ⊂ U 3 be the set of curves that correspond to M 4 , and let U 4 ⊂ U 3 be the set of curves that correspond to W 4 . Hence, we set
See Fig. 5(a).
We apply Theorem 3.5 to arbitrary subsets of M 4 and B 2 , each of size min(|M 4 |, |B 2 |), and obtain subsets M 5 ⊂ M 4 and B 3 ⊂ B 2 , each of size Ω δ (n), such that either every red curve in M 5 crosses every blue curve in B 3 , or every red curve in M 5 is disjoint from every blue curve in B 3 . In the former case, we are done. Hence, we can assume that we are in the latter case.
We again apply Theorem 3.5 to arbitrary subsets of M 4 and B 3 , each of size min(|M 4 |, |B 3 |), to obtain subsets M 5 ⊂ M 4 and B 4 ⊂ B 3 , each of size Ω δ (n), such that either every red curve in M 5 crosses every blue curve in B 4 , or every red curve in M 5 is disjoint from every blue curve in B 4 . Again, if we are in the former case, we are done. Hence, we can assume that we are in the latter case. Let
Recall that every element in M 5 crosses every element in W 5 . By the pseudosegment condition, every element in W 5 is disjoint from every element in W 5 .
Let R 5 be the set of red curves in R that correspond to W 5 , and let R 5 be the set of red curves in R that correspond to W 5 . We have
For each curve α ∈ R 5 ∪ R 5 , and its original partition α = α u ∪ α ℓ defined by γ 1 , we have a new partition α = α u ∪ α ℓ defined by γ 2 , where α u = α w and α ℓ = α m ∪ α ℓ . By setting R (1) = R 5 ∪ R 5 , and B (1) = B 4 , where each curve α ∈ R (1) is equipped with the partition α = α u ∪ α ℓ , we satisfy the base case of the statement.
Case 2. The argument is essentially the same as in Case 1. Suppose we have at least |U 3 | 2 /8 crossing pairs in M 3 × M 3 . Then, by Theorem 2.9, there are subsets M 4 , M 4 ⊂ M 3 , each of size Ω δ (n), such that every curve in M 4 crosses every curve in M 4 . Let U 4 ⊂ U be the set of curves that correspond to M 4 and let U 4 ⊂ U be the set of curves that correspond to M 4 . Set
See Fig. 5(b).
Hence, by the pseudosegment condition, every curve in W 4 is disjoint from every curve in W 4 . By taking arbitrary subsets of M 4 and B 2 of size min(|M 4 |, |B 2 |), we can apply Theorem 3.5 to these subsets and obtain subsets M 5 ⊂ M 4 and B 3 ⊂ B 2 , each of size Ω δ (n), such that either every red curve in M 5 crosses every blue curve in B 3 , or every red curve in M 5 is disjoint from every blue curve in B 3 . In the former case, we are done. Hence, we can assume that we are in the latter case.
Again, we take an arbitrary subset of M 4 and B 3 of size min(|M 4 |, |B 3 |) and apply Theorem 3.5 to M 4 and B 3 , to obtain subsets M 5 ⊂ M 4 and B 4 ⊂ B 3 , each of size Ω δ (n), such that either every red curve in M 5 crosses every blue curve in B 4 , or every red curve in M 5 is disjoint from every blue curve in B 4 . Again, if we are in the former case, we are done. Hence, we can assume that we are in the latter case. Let R 5 be the set of red curves in R that corresponds to M 5 , and let R 5 be the set of red curves in R that corresponds to M 5 .
We have |R 5 |, |R 5 | = Ω δ (n), and we can assume that |R 5 | = |R 5 |. For each curve α ∈ R 5 ∪ R 5 , and its original partition α = α u ∪ α ℓ defined by γ 1 , we have a new partition α = α u ∪ α ℓ defined by γ 2 , where α u = α w and α ℓ = α m ∪ α ℓ . By setting R (1) = R 5 ∪ R 5 , and B (1) = B 4 , where each curve α ∈ R (1) is equipped with the partition α = α u ∪ α ℓ , we satisfy the base case of the statement.
For the inductive step, suppose we have obtained constants ε t-1 < • • • < ε 1 such that the statement follows. Let ε t be a small constant that will be determined later such that ε t < ε t-1 . Let R be a set of n red curves in the plane, all crossed by a curve γ 1 exactly once, and B be a set of n blue curves in the plane such that R ∪ B ∪ {γ 1 } is a collection of pseudosegments. Moreover, G(R) has edge density at least 1ε t and G(B) has edge density less than ε t . We set δ < 0 to be a small constant such that ε t < δ < ε t-1 . We repeat the entire argument above, replacing ε 1 with ε t and δ with δ . If we find linear-sized subsets of R and B whose curves are disjoint from each other or cross each other, then we are done. Otherwise, we obtain subsets R 5 , R 5 ⊂ R and B 4 ⊂ B, each of size Ω δ (n), such that each α ∈ R 5 ∪ R 5 is equipped with the partition α = α u ∪ α ℓ , and α ℓ is disjoint from every blue curve in B 4 . Moreover, for α ∈ R 5 and β ∈ R 5 , where
where δ 1 depends only on δ , by Theorem 2.15, G(R 5 ) has edge density at least 1 -2ε t /δ 2 1 and G(B 4 ) has edge density less than 2ε t /δ 2 1 . By setting ε t sufficiently small, G(R 5 ) has edge density at least 1ε t-1 , and G(B 4 ) has edge density less than ε t-1 . By averaging, we can find subsets of R 5 and B 4 , each of size min(|R 5 |, |B 4 |) and with densities at least 1ε t-1 and less than ε t-1 respectively, and apply induction to these subsets with parameter t = t -1, and obtain subsets R (t-1) ⊂ R 5 , B (t-1) ⊂ B 4 , each of size Ω ε t-1 (n), with the desired properties. If every red curve in R (t-1) is disjoint from every blue curve in B (t-1) , or if every red curve in R (t-1) crosses every blue curve in B (t-1) , then we are done. Hence, we can assume that each curve α ∈ R (t-1) has a partition α = α u ∪ α ℓ such that α u is a subcurve of α u , α ℓ is disjoint from every blue curve in B (t-1) , and there is an equipartition
, where δ 2 depends only on δ , by Theorem 2.15, G(R 5 ) has edge density at least 1 -2ε t /δ 2 2 , and G(B (t-1) ) has edge density less than 2ε t /δ 2 2 . By setting ε t sufficiently small, G(R 5 ) has edge density at least 1ε t-1 , and G(B (t-1) ) has edge density less than ε t-1 . By averaging, we can find subsets of R 5 and B (t-1) , each of size min(|R 5 |, |B (t-1) |) and with densities at least 1ε t-1 and less than ε t-1 respectively, and apply induction to these subsets with parameter t = t -1, and obtain subsets S (t-1) ⊂ R 5 , B (t) ⊂ B (t-1) , each of size Ω ε t-1 (n), with the desired properties. If every red curve in S (t-1) is disjoint from every blue curve in B (t) , or if every red curve in S (t-1) crosses every blue curve in B (t) , then we are done. Hence, we can assume that each curve α ∈ S (t-1) has a partition α = α u ∪α ℓ such that α u is a subcurve of α u , α ℓ is disjoint from every blue curve in B (t-1) , and there is an equipartition
such that for 1 ≤ i < j ≤ 2 t-1 , the upper part α u of each curve α ∈ S (t-1) i is disjoint from the upper part β u of each curve β ∈ S (t-1) j . We then (arbitrarily) remove curves from each part in R (t-1) i and S (t-1) j such that the resulting parts all have the same size and for
Then R (t) and B (t) has the desired properties.
We now prove the following. Theorem 4.5. There is an absolute constant ε 3 > 0 such that the following holds. Let R be a set of n red curves in the plane and B be a set of n blue curves in the plane such that R ∪ B is a collection of pseudosegments, and the intersection graph G(B) has edge density less than ε 3 , and G(R) has edge density at least 1ε 3 .
Then there are subsets R ⊂ R, B ⊂ B, each of size Ω(n), such that either every red curve in R crosses every blue curve in B, or every red curve in R is disjoint from every blue curve in B.
Proof. Let t be a fixed large integer such that 2 -t < ε 1 , where ε 1 is defined in Theorem 4.3. Let ε 3 be a small constant determined later such that ε 3 < ε t , where ε t is defined in Lemma 4.4. Recall that ε t < ε 1 . Since G(R) has edge density at least 1ε 3 , there is a curve γ 1 ∈ R such that γ 1 crosses at least n/2 red curves in R. Let R 0 ⊂ R be the red curves that crosses γ 1 . By Lemma 2.15, G(R 0 ) has edge density at least 1 -8ε 3 . By averaging, we can find a subset B ⊂ B of size |R 0 | whose edge density is less than ε 3 . By setting ε 3 sufficiently small so that 8ε 3 < ε t , we can apply Lemma 4.4 to R 0 and B with parameter t, and obtain subsets R ⊂ R 0 , B ⊂ B, each of size Ω ε t (n), with the desired properties. If every red curve in R crosses every blue curve in B, or every red curve in R is disjoint from every blue curve in B, then we are done. Therefore, we can assume that each curve α ∈ R has a partition into two parts α = α u ∪ α ℓ with the properties described in Lemma 4.4. Set
Hence, every curve in L is disjoint from every curve in B, and G(U) has edge density at most 2 -t < ε 1 . Since | B| ≥ δn, where δ depends only on ε t , by Lemma 2.15, G( B) has edge density at most 2ε 3 /δ 2 . By setting ε 3 sufficiently small so that 2ε 3 /δ 2 0 < ε 1 , G( B) has edge density at most ε 1 . By averaging, we can find subsets of U and B, each of size min(|U|, | B|) and with densities at most ε 1 , and apply Theorem 4.3 to these subsets to obtain subsets U ⊂ U and B ⊂ B, each of size Ω ε 3 (n), such that every curve in U is disjoint from every curve in B , or every curve in U crosses every curve in B . By setting R to be the red curves in R corresponding to U , every red curve in R is disjoint from every blue curve in B , or every red curve in R crosses every blue curve in B , and both have size Ω ε 3 (n).
Finally, we consider the case when the intersection graphs G(R) and G(B) both have edge densities at least 1ε. By copying the entire proof of Theorem 4.5 and Lemma 4.4 almost verbatim, with the exception that the intersection graphs of the blue curves will maintain high density, and replacing the application of Theorem 4.3 (low versus low density) with Theorem 4.5 (high versus low density), we obtain the following. Theorem 4.6. There is an absolute constant ε 4 > 0 such that the following holds. Let R be a set of n red curves in the plane and B be a set of n blue curves in the plane such that R∪B is a collection of pseudosegments, and the intersection graphs G(B) and G(R) both have edge density at least 1ε 4 .
Then there are subsets R ⊂ R, B ⊂ B, each of size Ω(n), such that either every red curve in R crosses every blue curve in B, or every red curve in R is disjoint from every blue curve in B.
Let R be a set of n red curves in the plane, and B be a set of n blue curves in the plane such that R ∪ B is a collection of pseudosegments. Let ε be a sufficiently small constant such that ε < ε 4 < ε 3 < ε 1 , where ε 1 is from Theorem 4.3, ε 3 is from Theorem 4.5, and ε 4 is from Theorem 4.6. We apply Corollary 2.14 to both R and B and obtain subsets R 1 ⊂ R and B 1 ⊂ B such that both G(R 1 ) and G(B 1 ) are ε-homogeneous. Moreover, we can assume that
If both G(R 1 ) and G(B 1 ) have edge densities less than ε, then, since ε is sufficiently small, we can apply Theorem 4.3 to obtain subsets R 2 ⊂ R 1 and B 2 ⊂ B 1 , each of size Ω ε (n), such that either every red curve in R 2 is disjoint from every blue curve in B 2 , or every red curve in R 2 crosses every blue curve in B 2 .
If one of the graphs G(R 1 ) or G(B 1 ) has edge density less than ε, and the other has edge density greater than 1ε, then we apply Theorem 4.5 to R 1 and B 1 to obtain subsets R 2 ⊂ R 1 and B 2 ⊂ B 1 , each of size Ω ε (n), such that either every red curve in R 2 is disjoint from every blue curve in B 2 , or every red curve in R 2 crosses every blue curve in B 2 .
Finally, if both G(R 1 ) and G(B 1 ) have edge densities at least 1ε, then, since ε is sufficiently small, we can apply Theorem 4.6 to obtain subsets R 2 ⊂ R 1 and B 2 ⊂ B 1 , each of size Ω ε (n), such that either every red curve in R 2 is disjoint from every blue curve in B 2 , or every red curve in R 2 crosses every blue curve in B 2 .
In this section, we prove Theorem 1.2. Recall that the odd-crossing number of G, denoted by odd-cr(G), is the minimum possible number of pairs of edges that cross an odd number of times, over all drawings of G. The bisection width of a graph G is defined as
where the minimum is take over all partitions
The following lemma, due to Pach and Tóth [39], relates the odd-crossing number of a graph to its bisection width. Since all graphs contain a bipartite subgraph with at least half of its edges, Theorem 1.2 immediately follows from the following theorem. Proof. Let c > 0 and c 1 > 0 be the absolute constants from Theorem 2.11 and Lemma 6.1 respectively, and let c 2 > 0 be a sufficiently large constant that will be determined later. We define f (n, k) to be the maximum number of edges in an n-vertex simple topological bipartite graph with no k pairwise disjoint edges. We will prove by induction on n and k that
Clearly, we have f (2, k) ≤ 1, and by the results on thrackles imply that f (n, 2) ≤ 1.4n. Assume the statement holds for n < n and k < k, and let G be an n-vertex simple topological bipartite graph with no k pairwise disjoint edges. The proof falls into two cases. G does not contain k pairwise disjoint edges, this implies that either E 1 or E 2 does not contain k/2 pairwise disjoint edges. Without loss of generality, suppose E 1 does not contain k/2 pairwise disjoint edges. Hence
By the induction hypothesis, we have
Hence, for c 2 sufficiently large, we have |E(G)| ≤ n(log n) c 2 log(k) . In what follows, we will apply a redrawing technique due to Pach and Tóth in [40]
We can redraw G such that the vertices in V 1 lie above the line y = 1, the vertices in V 2 lie below the line y = 0, the edges in the strip 0 ≤ y ≤ 1 are vertical segments, and we have neither created nor removed any crossings. We then "flip" the upper half-plane bounded by the y = 1 line from left to right about the y-axis, and replace the edges in the strip 0 ≤ y ≤ 1 with straight line segments that reconnect the corresponding pairs on the line y = 0 and y = 1. See Fig. 6.
Notice that if any two edges crossed in the original drawing, then they must cross an even number of times in the new drawing. Indeed, suppose the edges e 1 and e 2 crossed in the original drawing. Due to the drawing being simple, they share exactly 1 point in common. Let k i denote the number of times edge e i crosses the strip for i ∈ {1, 2}, and note that k i must be odd since V 1 lies above the line y = 1 and v 2 lies below the line y = 0. After we have redrawn our graph, these k 1 + k 2 segments inside the strip will now pairwise cross, creating k 1 +k 2 2 crossing points. Since edge e i will now cross itself k i 2 times, this implies that there are now
crossing points between edges e 1 and e 2 inside the strip 0 ≤ y ≤ 1. One can easily check that (1) is odd when k 1 and k 2 are odd. Since e 1 and e 2 had 1 point in common outside of the strip, this implies that e 1 and e 2 cross each other an even number of times in the new drawing. Moreover, we can easily get rid of self-intersections by making modifications in a small ball at these crossing points. Hence, the odd-crossing number in our new drawing is at most the number of disjoint pair of edges in the original drawing of G, plus the number of pair of edges that share a common vertex. Since there are at most
By Lemma 6.1, there is a partition of the vertex set
, where i = 1, 2, and
Since n 1 , n 2 < n, by the induction hypothesis, we have
A graph is said to be a cograph if it consists of a single-vertex or if it can be obtained from two smaller cographs by either taking their disjoint union or their join. We next define the depth of a cograph. The graph on one vertex has depth 0. The depth of a cograph G is the minimum integer i such that G is the disjoint union or join of two smaller cographs, and the larger of the depths of the two smaller cographs is i -1. For example, the depth of a complete or empty graph on k vertices is log 2 k .
The proof of Theorem 1.2 can be generalized as follows.
Theorem 7.1. Let F be a cograph with depth d.
Proof sketch. The proof is very similar to the proof of Theorem 6.2. We proceed by induction on the depth d and n. When d = 0 or n = 1, the statement is trivial. For the inductive step, let F be the disjoint union or the join of two cographs F 1 , F 2 of smaller depth. If F is the disjoint union of F 1 and F 2 , then we follow the proof of Theorem 6.2, using the induction hypothesis on d.
If F is the join of F 1 and F 2 , then the proof is again similar to the proof of Theorem 6.2 and follows an argument used to bound the number of edges of k-quasiplanar topological graphs (see, e.g., [19]). Let ε = c/(log 6 n), where c > 0 is a small constant. We consider the two cases whether or not G has at least ε|E(G)| 2 crossing edges.
In the former case, we apply Theorem 2.12 to the edges of G and obtain two subsets E 1 , E 2 ⊂ E(G), each of size at least c ε|E(G)| such that every edge in E 1 crosses every edge in E 2 and c > 0 is an absolute constant. Hence, for some i ∈ {1, 2}, the subgraph G i = (V, E i ) does not have a matching whose intersection graph is F i . We can apply induction to get an upper bound on |E i |. Together with the lower bound |E i | ≥ c ε|E(G)|, we obtain the desired upper bound on |E(G)|.
In the latter case, the drawing of G shows that it has crossing number less than |E(G)| 2 . In this case, we apply the bisection width/crossing number inequality due to Pach, Shahrokhi, and Szegedy [36] and apply induction on n.
A natural k-grid in a topological graph is a pair of edge sets E 1 , E 2 , such that E i consists of k pairwise disjoint edges, and every edge in E 1 crosses every edge in E 2 . In [1], Ackerman and the authors showed that every n-vertex simple topological graph with no natural k-grid has at most O(n log 4k-6 n) edges. As a corollary to Theorem 7.1, noting that the balanced complete bipartite graph with k vertices in each part is a cograph with depth log 2 k + 1, we have the following.
In Section 2, we proved several properties of hereditary families of graphs are equivalent. Here we extend on these equivalences with some natural variants of these properties.
It is natural to drop the assumption that the vertex subsets have the same size in the definition of the mighty Erdős-Hajnal property. So we say a family F of graphs has the unbalanced mighty Erdős-Hajnal property if there is a constant c > 0 such that for every graph G ∈ F and for all disjoint vertex subsets A and B of G, there are subsets A ⊂ A and B ⊂ B with |A | ≥ c|A| and |B | ≥ c|B| and the bipartite graph between A and B is complete or empty. Trivially, if F has the unbalanced mighty Erdős-Hajnal property, then it also has the mighty Erdős-Hajnal property. The following proposition shows that something close to a converse also holds. that are complete between them. Trivially, if a family of graphs has the unbalanced homogeneous density property, then it also has the homogeneous density property. In the other direction, just as in the proof of Lemma 7.3, if a hereditary family of graphs has the homogeneous density property and is closed under cloning vertices, then it also has the unbalanced homogeneous density property. In particular, the family of intersection graphs of pseudosegments has the unbalanced homogeneous density property.
In the definition of the homogeneous density property, we require a polynomial dependence on the density ε. It turns out that for a hereditary family F and the family F of complements of graphs in F, having this property is equivalent to the seemingly weaker property that the there is just some dependence on the density ε. We formalize this now. A family F of graphs has the weak homogeneous density property if We can add to the list of equivalent properties in Theorem 2.2 that F and F have the weak homogeneous density property. The "only if" direction of Theorem 7.5 is trivial. To see the "if" direction, observe that the proof of Lemma 2.5 implies that F and F have the homogeneous density property implies that F has the mighty Erdős-Hajnal property extends to show that F and F have the weak homogeneous density property implies that F has the mighty Erdős-Hajnal property. Further, Lemma 2.6 implies hereditary F has the mighty Erdős-Hajnal property implies that F and F have the homogeneous density property. Thus, the "if" direction holds as well.